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

قضیه باقی‌مانده چینی ( به انگلیسی: Chinese remainder theorem )

قضیه‌ای در زمینه نظریه اعداد است و تعمیم آن در جبر نظری بیان می‌شود.

شرح قضیه

فرم اولیه قضیه در کتاب سان زی سوآنجینگ(孙子算经)(Sun Zi Suanjing) نوشته ریاضی‌دان چینی سان تزو (Sun Tzu) که بعداً با عنوان ۱۲۴۷ توسط قین جیوشاو (Qin Jiushao) باز نوشت شد گنجانده شده.

فرض کنید n_۱، n_۲، …، n_k اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح a_۱،a_۲، …، a_k عدد صحیح x وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}}\end{aligned}}}$

علاوه بر این تمام جوابهای x به پیمانه N = n_۱n_۲…n_k همنهشتند. در نتیجه برای همه ${\displaystyle 1\leq i\leq k}$ داریم:${\displaystyle x\equiv y{\pmod {n_{i}}}}$ اگر و تنها اگر ${\displaystyle x\equiv y{\pmod {N}}}$. گاهی اوقات این دستگاه حتی زمانی که همه n_iها دوبه دو نسبت به هم اول نیستند هم قابل حل است: جواب x وجود دارد اگر و تنها اگر:

${\displaystyle a_{i}\equiv a_{j}{\pmod {\gcd(n_{i},n_{j})}}\qquad {\mbox{for all }}i{\mbox{ and }}j.\,\!}$

در این حالات تمام جوابهای x به پیمانه کوچک‌ترین مضرب مشترک n_iها همنهشتند. شکلهایی از این قضیه در کتابLiber Abaci از فیبوناچی(Fibonacci) در سال ۱۲۰۲ آمده‌است.

الگوریتمی ساختاری برای یافتن جواب

این الگوریتم قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند.

این الگوریتم تنها زمانی که ${\displaystyle n_{i}}$ها دوبه دو نسبت به هم اولند جواب می‌دهد. در حالی که روش تفریق‌های متوالی معمولاً حتی زمانی که پیمانه‌ها دو به دو نسبت به هم اول نیستند هم کاربرد دارد.

فرض کنید جوابی برای دستگاه معادلات زیر وجود دارد.

${\displaystyle x\equiv a_{i}{\pmod {n_{i}}}\quad \mathrm {for} \;i=1,\ldots ,k.}$

حاصلضرب ${\displaystyle N=n_{1}n_{2}\ldots n_{k}}$ تعریف می‌شود. جواب x به صورت زیر بدست می‌آید. برای هرi، ${\displaystyle n_{i}}$ و ${\displaystyle N/n_{i}}$ نسبت به هم اولند. با استفاده از الگوریتم گسترده اقلیدس(extended Euclidean algorithm) می‌توان اعداد ${\displaystyle r_{i}}$ و ${\displaystyle s_{i}}$ را طوری‌که ${\displaystyle r_{i}n_{i}+s_{i}N/n_{i}=1}$ باشد را یافت. با فرض اینکه ${\displaystyle e_{i}=s_{i}N/n_{i}}$ باشد می‌توان به عبارت زیر رسید.

${\displaystyle r_{i}n_{i}+e_{i}=1\,\!}$

با در نظر گرفتن ${\displaystyle e_{i}}$، عبارت بالا تضمین می‌کند که باقی‌مانده تقسیم آن بر ${\displaystyle n_{i}}$ برابر ۱ خواهد بود. از طرفی چون خود این عدد برابر ${\displaystyle s_{i}N/n_{i}}$ تعریف شده‌است، بر تمام ${\displaystyle n_{j}}$ها مگر ${\displaystyle n_{i}}$ بخشپذیر است و داریم:

${\displaystyle e_{i}\equiv 1{\pmod {n_{i}}}\quad \mathrm {and} \quad e_{i}\equiv 0{\pmod {n_{j}}}\quad \mathrm {for} ~i\neq j}$

در نتیجه با استفاده از قوانین ضرب در همنهشتی‌ها، جوابی برای دستگاه معادلات همنهشتی به صورت زیر خواهد بود:

${\displaystyle x=\sum _{i=1}^{k}a_{i}e_{i}.\!}$

نمونه

پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.

${\displaystyle x\equiv 2{\pmod {3}},\,\!}$

${\displaystyle x\equiv 3{\pmod {4}},\,\!}$

${\displaystyle x\equiv 1{\pmod {5}}.\,\!}$

با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی e_۱ = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی e_۲ = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ''e_۳ = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند. یعنی همه آن‌ها با ۱۱ به پیمانه ۶۰ همنهشتند.

نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای ${\displaystyle e_{i}}$ها متفاوت باشد، اما در جواب نهایی همه مشترکند.

کاربرد

از این قضیه در الگوریتم RSA برای رسیدن به جواب در زمان کمتر استفاده می‌شود.

برای انجام محاسبات بر روی اعداد بسیار بزرگ از این قضیه استفاده می‌شود. اعداد که نسبت به هم اولند به عنوان ${\displaystyle n_{i}}$ انتخاب می‌شوند و اعداد بزرگ برای محاسبه به صورت زوج مرتب از ${\displaystyle a_{i}}$ها در می‌آیند و پس از انجام محاسبات بر روی ${\displaystyle a_{i}}$ها نتیجه به صورت خود عدد درمی‌آید.

اثبات قضیه

یک طرف قضیه با روشی که برای بدست آوردن جواب ارائه شد اثبات شد. اثبات یکتایی این جواب هم با استفاده از برهان خلف ثابت می‌شود:

فرض می‌کنیم که دو جواب صحیح مثبت x و y کوچکتر از N برای دستگاه وجود دارد. بعد ثابت می کنیم که هر کدام از n_iها تفاضل این دو عدد را می شمارد. نتیجه می‌شود که N هم تفاضل این دو عدد را می شمارد که این خلاف فرض ما است که دو عدد x و y را بین صفر و N در نظر گرفتیم.

تعمیم

فرض کنید ${\displaystyle \;d_{1},d_{2},...,d_{n}}$ و همچنین ${\displaystyle \;a_{1},a_{2},...,a_{n}}$ اعدادی صحیح باشند که برای هر ${\displaystyle \;0\leq i,j\leq n}$ داریم: ${\displaystyle \;(d_{i},d_{j})|a_{i}-a_{j}}$. که ${\displaystyle \;(d_{i},d_{j})}$ ب.م.م ${\displaystyle \;d_{i}}$ و ${\displaystyle \;d_{j}}$ است. حال حتماً عدد صحیح ${\displaystyle \;x}$ وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند:

${\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {d_{1}}}\\x&\equiv a_{2}{\pmod {d_{2}}}\\&\vdots \\x&\equiv a_{k}{\pmod {d_{k}}}\end{aligned}}}$

منابع

• دانلد کنوت. هنر برنامه‌نویسی رایانه, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.3.2 (pp.286–291), exercise 4.6.2–3 (page 456).
• توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.5: The Chinese remainder theorem, pp.873–876.
• Sigler, Laurence E. (trans.) (2002), Fibonacci's Liber Abaci, Springer-Verlag, p. 402–403, ISBN 0-387-95419-8