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

قضیه باقیمانده چینی (Chinese Remainder Theorem)

قضیه باقیمانده چینی یا همون Chinese Remainder Theorem (که از این به بعد بهش میگیم CRT) رو یه ریاضیدان چینی به اسم سون تزو کشف کرده.

قضیه چی میگه؟

خب، فرض کن یه عدد $m$ داریم که از حاصل‌ضرب چندتا عدد دیگه مثل $m_1, m_2, \dots, 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$ (که همون $3 \times 5 \times 7$ هست). چرا؟ چون $23 \bmod{3} = 2$، $23 \bmod{5} = 3$ و $23 \bmod{7} = 2$ هست. البته هر جوابی رو میشه به شکل $23 + 105\cdot k$ نوشت (که $k$ یه عدد صحیحه).

یه نتیجه‌ی باحال

یکی از نتایج باحال 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$ به پیمانه $m_1 m_2$ پیدا کنیم. اینجا الگوریتم اقلیدسی تعمیم‌یافته به کارمون میاد. با این الگوریتم می‌تونیم دو تا ضریب بزو (Bézout coefficients) به اسم $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 m_2 \equiv 1 \pmod{m_1}$، پس $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}$$

خیلی راحت میشه چک کرد که این فرمول واقعاً جواب میده. کافیه باقیمانده‌اش رو به $m_1$ و $m_2$ حساب کنیم. مثلاً برای $m_1$:

$$ \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$ هم بر $m_1$ و هم بر $m_2$ بخش‌پذیره. چون $m_1$ و $m_2$ نسبت به هم اولن، پس $x-y$ باید بر حاصل‌ضربشون یعنی $m_1 m_2$ هم بخش‌پذیر باشه. این یعنی $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_{j \neq i} m_j$ حاصلضرب همه‌ی پیمانه‌ها به جز $m_i$ باشه. بعد $N_i$ رو هم وارون ضربی پیمانه‌ای $M_i$ به پیمانه $m_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$ رو به هر کدوم از $m_i$ها حساب کنیم. چون برای هر $j$ که مخالف $i$ باشه، $M_j$ یه ضریبی از $m_i$ هست، پس $M_j \pmod{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); // mod_inv وارون ضربی رو حساب می‌کنه
        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}$ رو میشه به یه دستگاه از معادلات هم‌نهشتی دیگه تبدیل کرد. چطوری؟ $m_i$ رو به عوامل اولش تجزیه می‌کنی ($p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$) و برای هر کدوم از این توان‌های اول یه معادله می‌نویسی.

با این کار، می‌تونیم دستگاه اصلی رو به یه دستگاه جدید تبدیل کنیم که پیمانه‌هاش فقط توان‌های اعداد اول هستن. مثلاً، دستگاه بالا معادل این دستگاه میشه:

$$\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}$ هستن. معادله اولی ($a \equiv 1 \pmod{4}$) دومی رو هم نتیجه میده ($a$ اگه به ۴ باقیمانده ۱ بده، حتماً به ۲ هم باقیمانده ۱ میده). پس می‌تونیم دومی رو نادیده بگیریم و این دستگاه جدید رو حل کنیم که پیمانه‌هاش نسبت به هم اولن:

$$\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}$ باشه.

هر وقت هم که لازم شد، می‌تونی با الگوریتم بالا عدد بزرگ اصلی رو دوباره بسازی.

یه راه جایگزین اینه که عدد رو در نمایش مبنای مختلط (mixed radix) نشون بدی:

$$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$ رو حساب می‌کنه. و با داشتن این ضریب‌ها می‌تونی عدد کامل رو دوباره به دست بیاری.

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