قضیه باقی‌مانده چینی
قضیه باقی‌مانده چینی قضیه‌ای در زمینه نظریه اعداد است و تعمیم آن در جبر نظری بیان می‌شود.
فرم اولیه قضیه در کتاب سان زی سوآنجینگ(孙子算经)(Sun Zi Suanjing) نوشته ریاضی‌دان چینی سان تزو (Sun Tzu) که بعداً با عنوان ۱۲۴۷ توسط قین جیوشاو (Qin Jiushao) باز نوشت شد گنجانده شده.
فرض کنید "n"، "n"، …، "n" اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح "a"،"a"، …، "a" عدد صحیح x وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند:
علاوه بر این تمام جوابهای x به پیمانه "N" = "n""n"…"n" همنهشتند. در نتیجه برای همه formula_2 داریم:formula_3 اگر و تنها اگر formula_4. گاهی اوقات این دستگاه حتی زمانی که همه "n"ها دوبه دو نسبت به هم اول نیستند هم قابل حل است: جواب x وجود دارد اگر و تنها اگر:
در این حالات تمام جوابهای x به پیمانه کوچک‌ترین مضرب مشترک "n"ها همنهشتند. شکلهایی از این قضیه در کتابLiber Abaci از فیبوناچی(Fibonacci) در سال ۱۲۰۲ آمده‌است.
این الگوریتم قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند.
این الگوریتم تنها زمانی که formula_6ها دوبه دو نسبت به هم اولند جواب می‌دهد. در حالی که روش تفریق‌های متوالی معمولاً حتی زمانی که پیمانه‌ها دو به دو نسبت به هم اول نیستند هم کاربرد دارد.
فرض کنید جوابی برای دستگاه معادلات زیر وجود دارد.
حاصلضرب formula_8 تعریف می‌شود. جواب x به صورت زیر بدست می‌آید. برای هرi، formula_6 و formula_10 نسبت به هم اولند. با استفاده از الگوریتم گسترده اقلیدس(extended Euclidean algorithm) می‌توان اعداد formula_11 و formula_12 را طوری‌که formula_13 باشد را یافت. با فرض اینکه formula_14 باشد می‌توان به عبارت زیر رسید.
با در نظر گرفتن formula_16، عبارت بالا تضمین می‌کند که باقی‌مانده تقسیم آن بر formula_6 برابر ۱ خواهد بود. از طرفی چون خود این عدد برابر formula_18 تعریف شده‌است، بر تمام formula_19ها مگر formula_6 بخشپذیر است و داریم:
در نتیجه با استفاده از قوانین ضرب در همنهشتی‌ها، جوابی برای دستگاه معادلات همنهشتی به صورت زیر خواهد بود:
پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.
با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی "e" = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی "e" = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ""e" = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند. یعنی همه آن‌ها با ۱۱ به پیمانه ۶۰ همنهشتند.
نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای formula_16ها متفاوت باشد، اما در جواب نهایی همه مشترکند.
از این قضیه در الگوریتم RSA برای رسیدن به جواب در زمان کمتر استفاده می‌شود.
برای انجام محاسبات بر روی اعداد بسیار بزرگ از این قضیه استفاده می‌شود. اعداد که نسبت به هم اولند به عنوان formula_6 انتخاب می‌شوند و اعداد بزرگ برای محاسبه به صورت زوج مرتب از formula_28ها در می‌آیند و پس از انجام محاسبات بر روی formula_28ها نتیجه به صورت خود عدد درمی‌آید.
یک طرف قضیه با روشی که برای بدست آوردن جواب ارائه شد اثبات شد. اثبات یکتایی این جواب هم با استفاده از برهان خلف ثابت می‌شود:
فرض می‌کنیم که دو جواب صحیح مثبت x و y کوچکتر از N برای دستگاه وجود دارد. بعد ثابت می کنیم که هر کدام از nها تفاضل این دو عدد را می شمارد. نتیجه می‌شود که N هم تفاضل این دو عدد را می شمارد که این خلاف فرض ما است که دو عدد x و y را بین صفر و N در نظر گرفتیم. فرض کنید formula_30 و همچنین formula_31 اعدادی صحیح باشند که برای هر formula_32 داریم: formula_33. که formula_34 ب.م.م formula_35 و formula_36 است. حال حتماً عدد صحیح formula_37 وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند: