চায়নিজ রিমেইন্ডার থিওরেম#
চায়নিজ রিমেইন্ডার থিওরেম (এই আর্টিকেলের বাকি অংশে যাকে CRT হিসেবে উল্লেখ করা হবে) চীনা গণিতবিদ সান জি আবিষ্কার করেছিলেন।
সূত্রায়ন#
ধরি $m = m_1 \cdot m_2 \cdots m_k$, যেখানে $m_i$ জোড়ায় জোড়ায় সহমৌলিক। $m_i$ ছাড়াও, আমাদের একটি সর্বসমতা পদ্ধতি দেওয়া আছে
$$\left\{\begin{array}{rcl} a & \equiv & a_1 \pmod{m_1} \\ a & \equiv & a_2 \pmod{m_2} \\ & \vdots & \\ a & \equiv & a_k \pmod{m_k} \end{array}\right.$$যেখানে $a_i$ কিছু প্রদত্ত ধ্রুবক। CRT-এর মূল রূপ তখন বলে যে প্রদত্ত সর্বসমতা পদ্ধতির সর্বদা একটি এবং ঠিক একটি সমাধান $m$ মডুলোতে থাকে।
যেমন, সর্বসমতা পদ্ধতি
$$\left\{\begin{array}{rcl} a & \equiv & 2 \pmod{3} \\ a & \equiv & 3 \pmod{5} \\ a & \equiv & 2 \pmod{7} \end{array}\right.$$এর সমাধান $105$ মডুলোতে $23$, কারণ $23 \bmod{3} = 2$, $23 \bmod{5} = 3$, এবং $23 \bmod{7} = 2$। আমরা সকল সমাধান $23 + 105\cdot k$ হিসেবে লিখতে পারি, $k \in \mathbb{Z}$-এর জন্য।
উপসিদ্ধান্ত#
CRT-এর একটি পরিণতি হলো সমীকরণ
$$x \equiv a \pmod{m}$$নিম্নলিখিত সমীকরণ পদ্ধতির সমতুল্য
$$\left\{\begin{array}{rcl} x & \equiv & a_1 \pmod{m_1} \\ & \vdots & \\ x & \equiv & a_k \pmod{m_k} \end{array}\right.$$(উপরের মতো, ধরুন $m = m_1 m_2 \cdots m_k$ এবং $m_i$ জোড়ায় জোড়ায় সহমৌলিক)।
দুই মডুলির জন্য সমাধান#
সহমৌলিক $m_1, m_2$-এর জন্য দুটি সমীকরণের পদ্ধতি বিবেচনা করুন:
$$ \left\{\begin{align} a &\equiv a_1 \pmod{m_1} \\ a &\equiv a_2 \pmod{m_2} \\ \end{align}\right. $$আমরা $a \pmod{m_1 m_2}$-এর একটি সমাধান খুঁজতে চাই। এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদম ব্যবহার করে আমরা বেজু সহগ $n_1, n_2$ খুঁজে পেতে পারি যেন
$$n_1 m_1 + n_2 m_2 = 1.$$আসলে $n_1$ এবং $n_2$ হলো যথাক্রমে $m_2$ এবং $m_1$ মডুলোতে $m_1$ এবং $m_2$-এর মডুলার ইনভার্স। আমাদের $n_1 m_1 \equiv 1 \pmod{m_2}$ তাই $n_1 \equiv m_1^{-1} \pmod{m_2}$, এবং বিপরীতভাবে $n_2 \equiv m_2^{-1} \pmod{m_1}$।
এই দুই সহগ দিয়ে আমরা একটি সমাধান সংজ্ঞায়িত করতে পারি:
$$a = a_1 n_2 m_2 + a_2 n_1 m_1 \bmod{m_1 m_2}$$$a \bmod{m_1}$ এবং $a \bmod{m_2}$ গণনা করে এটি যে প্রকৃতপক্ষে একটি সমাধান তা সহজেই যাচাই করা যায়।
$$ \begin{array}{rcll} a & \equiv & a_1 n_2 m_2 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 (1 - n_1 m_1) + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 - a_1 n_1 m_1 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 & \pmod{m_1} \end{array} $$লক্ষ্য করুন, চায়নিজ রিমেইন্ডার থিওরেম এটাও গ্যারান্টি দেয় যে $m_1 m_2$ মডুলোতে শুধুমাত্র ১টি সমাধান বিদ্যমান। এটি প্রমাণ করাও সহজ।
ধরুন আপনার দুটি ভিন্ন সমাধান $x$ এবং $y$ আছে। যেহেতু $x \equiv a_i \pmod{m_i}$ এবং $y \equiv a_i \pmod{m_i}$, তাই $x − y \equiv 0 \pmod{m_i}$ এবং সুতরাং $x − y \equiv 0 \pmod{m_1 m_2}$ অথবা সমতুল্যভাবে $x \equiv y \pmod{m_1 m_2}$। তাই $x$ এবং $y$ আসলে একই সমাধান।
সাধারণ ক্ষেত্রে সমাধান#
আনয়নমূলক সমাধান#
যেহেতু $m_1 m_2$ এবং $m_3$ সহমৌলিক, আমরা আনয়নমূলকভাবে যেকোনো সংখ্যক মডুলির জন্য দুই মডুলির সমাধান বারবার প্রয়োগ করতে পারি। প্রথমে আপনি প্রথম দুটি সর্বসমতা ব্যবহার করে $b_2 := a \pmod{m_1 m_2}$ গণনা করুন, তারপর সর্বসমতা $a \equiv b_2 \pmod{m_1 m_2}$ এবং $a \equiv a_3 \pmod {m_3}$ ব্যবহার করে $b_3 := a \pmod{m_1 m_2 m_3}$ গণনা করতে পারেন, ইত্যাদি।
সরাসরি নির্মাণ#
ল্যাগ্রেঞ্জ ইন্টারপোলেশনের অনুরূপ একটি সরাসরি নির্মাণ সম্ভব।
ধরি $M_i := \prod_{i \neq j} m_j$, $m_i$ ছাড়া সকল মডুলির গুণফল, এবং $N_i$ হলো মডুলার ইনভার্স $N_i := M_i^{-1} \bmod{m_i}$। তাহলে সর্বসমতা পদ্ধতির একটি সমাধান হলো:
$$a \equiv \sum_{i=1}^k a_i M_i N_i \pmod{m_1 m_2 \cdots m_k}$$সকল $i$-এর জন্য $a \bmod{m_i}$ গণনা করে আমরা যাচাই করতে পারি এটি প্রকৃতপক্ষে একটি সমাধান। যেহেতু $i \neq j$-এর জন্য $M_j$ হলো $m_i$-এর গুণিতক, আমরা পাই
$$\begin{array}{rcll} a & \equiv & \sum_{j=1}^k a_j M_j N_j & \pmod{m_i} \\ & \equiv & a_i M_i N_i & \pmod{m_i} \\ & \equiv & a_i M_i M_i^{-1} & \pmod{m_i} \\ & \equiv & a_i & \pmod{m_i} \end{array}$$ইমপ্লিমেন্টেশন#
struct Congruence {
long long a, m;
};
long long chinese_remainder_theorem(vector<Congruence> const& congruences) {
long long M = 1;
for (auto const& congruence : congruences) {
M *= congruence.m;
}
long long solution = 0;
for (auto const& congruence : congruences) {
long long a_i = congruence.a;
long long M_i = M / congruence.m;
long long N_i = mod_inv(M_i, congruence.m);
solution = (solution + a_i * M_i % M * N_i) % M;
}
return solution;
}সহমৌলিক নয় এমন মডুলির জন্য সমাধান#
উপরে উল্লিখিত হিসেবে, অ্যালগরিদমটি শুধুমাত্র সহমৌলিক মডুলি $m_1, m_2, \dots m_k$-এর জন্য কাজ করে।
সহমৌলিক নয় এমন ক্ষেত্রে, একটি সর্বসমতা পদ্ধতির $\text{lcm}(m_1, m_2, \dots, m_k)$ মডুলোতে ঠিক একটি সমাধান আছে, অথবা কোনো সমাধান নেই।
যেমন নিম্নলিখিত পদ্ধতিতে, প্রথম সর্বসমতাটি বোঝায় যে সমাধান বিজোড়, এবং দ্বিতীয় সর্বসমতাটি বোঝায় যে সমাধান জোড়। একটি সংখ্যা একই সাথে জোড় ও বিজোড় হওয়া সম্ভব নয়, তাই স্পষ্টতই কোনো সমাধান নেই।
$$\left\{\begin{align} a & \equiv 1 \pmod{4} \\ a & \equiv 2 \pmod{6} \end{align}\right.$$একটি পদ্ধতির সমাধান আছে কিনা নির্ধারণ করা বেশ সহজ। এবং যদি থাকে, আমরা সামান্য পরিবর্তিত সর্বসমতা পদ্ধতি সমাধান করতে মূল অ্যালগরিদম ব্যবহার করতে পারি।
একটি একক সর্বসমতা $a \equiv a_i \pmod{m_i}$ সর্বসমতা পদ্ধতি $a \equiv a_i \pmod{p_j^{n_j}}$-এর সমতুল্য যেখানে $p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$ হলো $m_i$-এর মৌলিক উৎপাদক বিভাজন।
এই তথ্য দিয়ে, আমরা সর্বসমতা পদ্ধতিটি এমন একটি পদ্ধতিতে পরিবর্তন করতে পারি যেখানে শুধুমাত্র মৌলিক ঘাত মডুলি হিসেবে আছে। যেমন উপরের সর্বসমতা পদ্ধতিটি নিম্নলিখিতটির সমতুল্য:
$$\left\{\begin{array}{ll} a \equiv 1 & \pmod{4} \\ a \equiv 2 \equiv 0 & \pmod{2} \\ a \equiv 2 & \pmod{3} \end{array}\right.$$যেহেতু মূলত কিছু মডুলির সাধারণ গুণনীয়ক ছিল, আমরা একই মৌলিক সংখ্যার উপর ভিত্তি করে কিছু সর্বসমতা মডুলি পাব, তবে সম্ভবত ভিন্ন মৌলিক ঘাত সহ।
আপনি লক্ষ্য করতে পারেন, সর্বোচ্চ মৌলিক ঘাত মডুলিসহ সর্বসমতাটি একই মৌলিক সংখ্যার উপর ভিত্তি করা সকল সর্বসমতার মধ্যে সবচেয়ে শক্তিশালী সর্বসমতা হবে। হয় এটি অন্য কোনো সর্বসমতার সাথে বিরোধ দেবে, অথবা এটি ইতিমধ্যেই অন্য সকল সর্বসমতাকে অন্তর্ভুক্ত করবে।
আমাদের ক্ষেত্রে, প্রথম সর্বসমতা $a \equiv 1 \pmod{4}$ বোঝায় $a \equiv 1 \pmod{2}$, এবং তাই দ্বিতীয় সর্বসমতা $a \equiv 0 \pmod{2}$-এর সাথে বিরোধ করে। তাই এই সর্বসমতা পদ্ধতির কোনো সমাধান নেই।
যদি কোনো বিরোধ না থাকে, তাহলে সমীকরণ পদ্ধতির একটি সমাধান আছে। আমরা সর্বোচ্চ মৌলিক ঘাত মডুলিসহগুলো ছাড়া সকল সর্বসমতা উপেক্ষা করতে পারি। এই মডুলিগুলো এখন সহমৌলিক, এবং তাই আমরা উপরের অনুচ্ছেদে আলোচিত অ্যালগরিদম দিয়ে এটি সমাধান করতে পারি।
যেমন নিম্নলিখিত পদ্ধতির $\text{lcm}(10, 12) = 60$ মডুলোতে একটি সমাধান আছে।
$$\left\{\begin{align} a & \equiv 3 \pmod{10} \\ a & \equiv 5 \pmod{12} \end{align}\right.$$সর্বসমতা পদ্ধতিটি নিম্নলিখিত সর্বসমতা পদ্ধতির সমতুল্য:
$$\left\{\begin{align} a & \equiv 3 \equiv 1 \pmod{2} \\ a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$একই মৌলিক মডুলিসহ একমাত্র সর্বসমতাগুলো হলো $a \equiv 1 \pmod{4}$ এবং $a \equiv 1 \pmod{2}$। প্রথমটি ইতিমধ্যে দ্বিতীয়টিকে অন্তর্ভুক্ত করে, তাই আমরা দ্বিতীয়টি উপেক্ষা করতে পারি, এবং পরিবর্তে সহমৌলিক মডুলিসহ নিম্নলিখিত পদ্ধতি সমাধান করতে পারি:
$$\left\{\begin{align} a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$এর সমাধান $53 \pmod{60}$, এবং প্রকৃতপক্ষে $53 \bmod{10} = 3$ এবং $53 \bmod{12} = 5$।
গার্নার অ্যালগরিদম#
CRT-এর আরেকটি পরিণতি হলো আমরা ছোট ইন্টিজারের একটি অ্যারে ব্যবহার করে বড় সংখ্যা উপস্থাপন করতে পারি।
অত্যন্ত বড় সংখ্যা নিয়ে অনেক গণনা করার পরিবর্তে, যা ব্যয়বহুল হতে পারে (১০০০-ডিজিটের সংখ্যা দিয়ে ভাগ করার কথা ভাবুন), আপনি কয়েকটি সহমৌলিক মডুলি বেছে নিতে পারেন এবং বড় সংখ্যাটিকে একটি সর্বসমতা পদ্ধতি হিসেবে উপস্থাপন করতে পারেন, এবং সমীকরণ পদ্ধতির উপর সকল অপারেশন সম্পাদন করতে পারেন। $m_1 m_2 \cdots m_k$-এর চেয়ে ছোট যেকোনো সংখ্যা $a$-কে একটি অ্যারে $a_1, \ldots, a_k$ হিসেবে উপস্থাপন করা যায়, যেখানে $a \equiv a_i \pmod{m_i}$।
উপরের অ্যালগরিদম ব্যবহার করে, আপনি প্রয়োজন হলে আবার বড় সংখ্যাটি পুনর্গঠন করতে পারেন।
বিকল্পভাবে আপনি সংখ্যাটি মিক্সড র্যাডিক্স রিপ্রেজেন্টেশনে উপস্থাপন করতে পারেন:
$$a = x_1 + x_2 m_1 + x_3 m_1 m_2 + \ldots + x_k m_1 \cdots m_{k-1} \text{ with }x_i \in [0, m_i)$$গার্নার অ্যালগরিদম, যা ডেডিকেটেড আর্টিকেল গার্নার অ্যালগরিদম-এ আলোচিত হয়েছে, সহগ $x_i$ গণনা করে। এবং সেই সহগগুলো দিয়ে আপনি পূর্ণ সংখ্যাটি পুনরুদ্ধার করতে পারেন।