قضیه باقی‌مانده چینی کیست؟ توضیح بده.
در ریاضیات، قضیه باقیمانده چینی بیان می‌کند که اگر باقی‌مانده تقسیم اقلیدسی یک عدد صحیح n را بر چند عدد صحیح بدانیم، می‌توانیم باقیمانده تقسیم n را بر حاصل ضرب این اعداد صحیح به‌طور یکتا تعیین کنیم، به شرط آن که مقسوم‌علیه‌ها نسبت به هم اول باشند (هیچ دو مقسوم‌علیه به جز ۱ عامل مشترکی نداشته باشند).به عنوان مثال، اگر بدانیم که باقیمانده n تقسیم بر ۳ برابر ۲ است، باقیمانده n تقسیم بر ۵ برابر ۳ است و باقیمانده n تقسیم بر ۷ برابر ۲ است، بدون دانستن مقدار n، می‌توانیم تعیین کنیم که باقیمانده n تقسیم بر ۱۰۵ (ضرب ۳، ۵ و ۷) ۲۳ است. مهمتر از همه، این به ما می‌گوید که اگر n عدد طبیعی کمتر از ۱۰۵ باشد، ۲۳ تنها مقدار ممکن n است.فرم اولیه قضیه در کتاب (孙子算经)(Sun Zi Suanjing) نوشته ریاضی‌دان چینی سون تزو (Sun Tzu) که بعداً در ۱۲۴۷ توسط قین جیوشاو (Qin Jiushao) باز نوشت شد گنجانده شده.قضیه باقیمانده چینی به‌طور گسترده برای محاسبات با اعداد صحیح بزرگ استفاده می‌شود، زیرا محاسباتی را که برای آن فرد محدودیتی در اندازه خروجی دارد با چندین محاسبات مشابه روی اعداد صحیح کوچک جایگزین می‌کند.قضیه باقی مانده چینی (بیان شده بر حسب همنهشتی‌ها) در هر حوزه ایده‌آل اصلی صادق است. این قضیه با صورتی شامل ایده‌آل‌های دوطرفه به هر حلقه‌ای تعمیم داده شده‌است.تاریخچه.اولین نسخه شناخته شده از این قضیه، به عنوان مسئله ای با اعدادی خاص، در کتاب قرن سوم Sun-tzu Suan-ching توسط ریاضیدان چینی Sun-tzu آمده‌است:چند شی داریم که تعدادشان مشخص نیست. اگر آنها را سه‌تا سه‌تا بشماریم، دو عدد باقی می‌ماند و با پنج، ما سه تا باقی‌مانده خواهیم داشت. برای هفت هم، دو تا باقی می‌ماند. چند شی وجود دارد؟کارهای سون تزو شامل هیچ الگوریتم یا اثباتی کاملی برای این سؤال نیست. اولین چیزی که بتوان آن را به عنوان یک الگوریتم برای این سؤال شناخت توسط آریابهاتا در قرن ششم ارائه شد. نسخه‌های خاصی از قضیه باقی‌مانده چینی توسط برهماگوپتا (قرن ۷ام) نیز شناخته شده بود که در کتاب فیبوناچی در ۱۲۰۲ میلادی نیز آورده شده‌اند. در نهایت تعمیم این صورت‌بندی‌ها به اسم "Da-yan-shu" () توسط در "" (, "Shu-shu Chiu-chang") در سال ۱۲۴۷ میلادی منتشر شده‌است که نهایتاً اوایل قرن ۱۹ام میلادی به زبان انگلیسی توسط ترجمه شده‌اند.اولین صورت‌بندی به وسیله همنهشتی‌ها توسط گاوس در "Disquisitiones Arithmeticae"(منتشر شده در ۱۸۰۱ میلادی) استفاده شد است. گاوس قضیه باقیمانده چینی را در مورد مسئله‌ای در مورد تقویم‌ها نشان می‌دهد، یعنی «پیدا کردن سال‌هایی که دارای یک دوره معین نسبت به چرخه خورشیدی و قمری و دوره رومی هستند». گاوس روشی را برای حل مسئله معرفی می‌کند که قبلاً توسط لئونارد اویلر استفاده شده بود اما در واقع یک روش بسیار قدیمی‌تر بود که چندین بار ظاهر شده بود.شرح قضیه.فرض کنید "n"۱، "n"۲، …، "n""k" اعداد صحیحی باشند که دو به دو نسبت به هم اولند. برای هر سری اعداد صحیح "a"۱،"a"۲، …، "a""k" عدد صحیح x وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند:علاوه بر این تمام جوابهای x به پیمانه "N" = "n"۱"n"۲…"n""k" همنهشتند. در نتیجه برای همه formula_2 داریم:formula_3 اگر و تنها اگر formula_4.گاهی اوقات این دستگاه حتی زمانی که همه "ni"ها دوبه دو نسبت به هم اول نیستند هم قابل حل است.فرض کنید formula_5 و همچنین formula_6 اعدادی صحیح باشند که برای هر formula_7 داشته باشیم formula_8. که formula_9 ب.م. م formula_10 و formula_11 است. حال حتماً عدد صحیح formula_12 وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند:formula_13روش ساختاری برای یافتن جواب.این الگوریتم قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند.این الگوریتم تنها زمانی که formula_14ها دوبه دو نسبت به هم اولند جواب می‌دهد. در حالی که روش تفریق‌های متوالی معمولاً حتی زمانی که پیمانه‌ها دو به دو نسبت به هم اول نیستند هم کاربرد دارد.فرض کنید جوابی برای دستگاه معادلات زیر وجود دارد.حاصلضرب formula_16 تعریف می‌شود. جواب x به صورت زیر بدست می‌آید. برای هرi, formula_14 و formula_18 نسبت به هم اولند. با استفاده از الگوریتم گسترده اقلیدس(extended Euclidean algorithm) می‌توان اعداد formula_19 و formula_20 را طوری‌که formula_21 باشد را یافت. با فرض اینکه formula_22 باشد می‌توان به عبارت زیر رسید.با در نظر گرفتن formula_24، عبارت بالا تضمین می‌کند که باقی‌مانده تقسیم آن بر formula_14 برابر ۱ خواهد بود. از طرفی چون خود این عدد برابر formula_26 تعریف شده‌است، بر تمام formula_27ها مگر formula_14 بخشپذیر است و داریم:در نتیجه با استفاده از قوانین ضرب در همنهشتی‌ها، جوابی برای دستگاه معادلات همنهشتی به صورت زیر خواهد بود:نمونه.پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید.با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی "e"۱ = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی "e"۲ = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ""e"۳ = −۲۴ است. پس یکی از جوابها برای x عدد ۲ × ۴۰ + ۳ × ۴۵ + ۱ × (۲۴-) = ۱۹۱ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند؛ یعنی همه آن‌ها با ۱۱ به پیمانه ۶۰ همنهشتند.نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای formula_24ها متفاوت باشد، اما در جواب نهایی همه مشترکند.کاربرد.از این قضیه در الگوریتم RSA برای رسیدن به جواب در زمان کمتر استفاده می‌شود.برای انجام محاسبات بر روی اعداد بسیار بزرگ از این قضیه استفاده می‌شود. اعداد که نسبت به هم اولند به عنوان formula_14 انتخاب می‌شوند و اعداد بزرگ برای محاسبه به صورت زوج مرتب از formula_36ها در می‌آیند و پس از انجام محاسبات بر روی formula_36ها نتیجه به صورت خود عدد درمی‌آید.تعمیم.فرض کنید formula_38 یک حلقه باشد و formula_39 ایده‌آل‌هایی از formula_38 باشند که برای هر formula_41 داشته باشیم formula_42. اگر formula_43 عنصرهای دلخواه formula_38 باشند آنگاه عنصر formula_45 چنان در formula_38 موجود است که formula_47 (در واقع formula_48). به علاوه اگر formula_49 موجود باشد که خاصیت formula_45 را داشته‌باشد آنگاه formula_51 (در واقع formula_52).