موضوع مقاله: قضیه باقی‌مانده چینی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه باقی‌مانده چینی | مقدمه: پیوند= اصلی Sun-tzu: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7)با جواب ، که k یک عدد صحیح است.|حاشیه در ریاضیات، قضیه باقیمانده چینی بیان می‌کند که اگر باقی‌مانده تقسیم اقلیدسی یک عدد صحیح n را بر چند عدد صحیح بدانیم، می‌توانیم باقیمانده تقسیم n را بر حاصل ضرب این اعداد صحیح به‌طور یکتا تعیین کنیم، به شرط آن که مقسوم‌علیه‌ها نسبت به هم اول باشند (هیچ دو مقسوم‌علیه به جز ۱ عامل مشترکی نداشته باشند). | ## بخش 1: قضیه باقی‌مانده چینی | به عنوان مثال، اگر بدانیم که باقیمانده n تقسیم بر ۳ برابر ۲ است، باقیمانده n تقسیم بر ۵ برابر ۳ است و باقیمانده n تقسیم بر ۷ برابر ۲ است، بدون دانستن مقدار n، می‌توانیم تعیین کنیم که باقیمانده n تقسیم بر ۱۰۵ (ضرب ۳، ۵ و ۷) ۲۳ است. مهمتر از همه، این به ما می‌گوید که اگر n عدد طبیعی کمتر از ۱۰۵ باشد، ۲۳ تنها مقدار ممکن n است. قضیه باقیمانده چینی به‌طور گسترده برای محاسبات با اعداد صحیح بزرگ استفاده می‌شود، زیرا محاسباتی را که برای آن فرد محدودیتی در اندازه خروجی دارد با چندین محاسبات مشابه روی اعداد صحیح کوچک جایگزین می‌کند. قضیه باقی مانده چینی (بیان شده بر حسب همنهشتی‌ها) در هر حوزه ایده‌آل اصلی صادق است. اگر آنها را سه‌تا سه‌تا بشماریم، دو عدد باقی می‌ماند و با پنج، ما سه تا باقی‌مانده خواهیم داشت. اولین چیزی که بتوان آن را به عنوان یک الگوریتم برای این سؤال شناخت توسط آریابهاتا در قرن ششم ارائه شد. نسخه‌های خاصی از قضیه باقی‌مانده چینی توسط برهماگوپتا (قرن ۷ام) نیز شناخته شده بود که در کتاب Liber Abaci فیبوناچی در ۱۲۰۲ میلادی نیز آورده شده‌اند. | ## بخش 2: قضیه باقی‌مانده چینی | گاوس قضیه باقیمانده چینی را در مورد مسئله‌ای در مورد تقویم‌ها نشان می‌دهد، یعنی «پیدا کردن سال‌هایی که دارای یک دوره معین نسبت به چرخه خورشیدی و قمری و دوره رومی هستند». گاوس روشی را برای حل مسئله معرفی می‌کند که قبلاً توسط لئونارد اویلر استفاده شده بود اما در واقع یک روش بسیار قدیمی‌تر بود که چندین بار ظاهر شده بود. برای هر سری اعداد صحیح a۱،a۲، …، ak عدد صحیح x وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند: علاوه بر این تمام جوابهای x به پیمانه N = n۱n۲…nk همنهشتند. گاهی اوقات این دستگاه حتی زمانی که همه niها دوبه دو نسبت به هم اول نیستند هم قابل حل است. حال حتماً عدد صحیح وجود دارد به‌طوری‌که در دستگاه معادلات همنهشتی زیر صدق کند: روش ساختاری برای یافتن جواب این الگوریتم قسمتی از اثبات قضیه هم هست زیرا جواب x را برای دستگاه پیدا می‌کند. در حالی که روش تفریق‌های متوالی معمولاً حتی زمانی که پیمانه‌ها دو به دو نسبت به هم اول نیستند هم کاربرد دارد. با در نظر گرفتن ، عبارت بالا تضمین می‌کند که باقی‌مانده تقسیم آن بر برابر ۱ خواهد بود. | ## بخش 3: قضیه باقی‌مانده چینی | از طرفی چون خود این عدد برابر تعریف شده‌است، بر تمام ها مگر بخشپذیر است و داریم: در نتیجه با استفاده از قوانین ضرب در همنهشتی‌ها، جوابی برای دستگاه معادلات همنهشتی به صورت زیر خواهد بود: نمونه پرسشی برای بدست آوردن عدد صحیح x که در دستگاه زیر صدق کند را در نظر بگیرید. با استفاده از الگوریتم اقلیدس برای ۳و ۴×۵ = ۲۰ داریم (۱۳-) × ۳ + ۲ × ۲۰ = ۱، یعنی e۱ = ۴۰ و برای ۴ و ۳×۵ = ۱۵ بدست می‌آوریم (۱۱-) × ۴ + ۳ × ۱۵ = ۱ یعنی e۲ = ۴۵. در نهایت برای ۵ و ۳×۴ = ۱۲ الگوریتم اقلیدس نتیجه می‌دهد۵ × ۵ + (۲-) × ۱۲ = ۱ به این معنا که ''e۳ = −۲۴ است. تمام اعداد صحیح دیگر که به پیمانه ۳ × ۴ × ۵ = ۶۰ با ۱۹۱ همنهشتند هم جواب هستند؛ یعنی همه آن‌ها با ۱۱ به پیمانه ۶۰ همنهشتند. نکته: ممکن است اعداد بدست آمده با الگوریتم اقلیدس برای ها متفاوت باشد، اما در جواب نهایی همه مشترکند. کاربرد از این قضیه در الگوریتم RSA برای رسیدن به جواب در زمان کمتر استفاده می‌شود. | ## جمع‌بندی | اعداد که نسبت به هم اولند به عنوان انتخاب می‌شوند و اعداد بزرگ برای محاسبه به صورت زوج مرتب از ها در می‌آیند و پس از انجام محاسبات بر روی ها نتیجه به صورت خود عدد درمی‌آید.