پرش به محتویات

قضیه باقیمانده چینی

قضیه باقیمانده چینی (که در ادامه این مقاله به آن 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.$$

جواب $23$ به پیمانه $105$ را دارد، زیرا $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_1$ و $m_2$ به پیمانه‌های $m_2$ و $m_1$ هستند. داریم $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}$ را با استفاده از دو هم‌نهشتی اول محاسبه می‌کنید، سپس می‌توانید $b_3 := a \pmod{m_1 m_2 m_3}$ را با استفاده از هم‌نهشتی‌های $a \equiv b_2 \pmod{m_1 m_2}$ و $a \equiv a_3 \pmod {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}$$

می‌توانیم با محاسبه $a \bmod{m_i}$ برای تمام $i$ها، بررسی کنیم که این واقعاً یک جواب است. چون $M_j$ برای $i \neq 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$ است.

الگوریتم Garner

یکی دیگر از نتایج CRT این است که می‌توانیم اعداد بزرگ را با استفاده از آرایه‌ای از اعداد صحیح کوچک نمایش دهیم.

به جای انجام محاسبات زیاد با اعداد بسیار بزرگ که ممکن است گران باشد (به تقسیم اعداد ۱۰۰۰ رقمی فکر کنید)، می‌توانید چند پیمانه دو به دو اول انتخاب کرده و عدد بزرگ را به عنوان یک دستگاه هم‌نهشتی نمایش دهید و تمام عملیات را روی این دستگاه معادلات انجام دهید. هر عدد $a$ کمتر از $m_1 m_2 \cdots m_k$ را می‌توان به صورت آرایه‌ای از $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{ با }x_i \in [0, m_i)$$

الگوریتم Garner، که در مقاله اختصاصی الگوریتم Garner مورد بحث قرار گرفته است، ضرایب $x_i$ را محاسبه می‌کند. و با آن ضرایب می‌توانید عدد کامل را بازیابی کنید.

مسائل تمرینی: