قضیه باقیمانده چینی؛ حل دستگاه همنهشتیها
آموزش شرط پیمانههای نسبتبههم اول، ساخت جواب و تعیین دوره جوابهای دستگاه همنهشتی در تست.
پاسخ کوتاه
قضیه باقیمانده چینی چند شرط باقیمانده را به یک کلاس همنهشتی تبدیل میکند. وقتی پیمانهها دوتادوتا نسبت به هم اول باشند، جواب در پیمانه حاصلضرب آنها یکتا است.
صورت قضیه
اگر پیمانههای m1 تا mk دوتادوتا نسبت به هم اول باشند، دستگاه x≡a_i (mod m_i) یک جواب یکتا نسبت به پیمانه M=m1m2...mk دارد. یکتایی یعنی همه جوابهای صحیح با اختلاف مضربی از M هستند.
روش جستوجوی منظم
برای دو همنهشتی، از یکی بنویس x=a+mt و آن را در شرط دوم جایگذاری کن. سپس یک همنهشتی خطی برای t حل میشود. این روش از فهرستکردن بیهدف عددها منظمتر و برای اعداد متوسط سریع است.
ساخت با وارون
در روش عمومی، M_i=M/m_i را میسازیم و وارون M_i نسبت به m_i را پیدا میکنیم. مجموع a_iM_iN_i یک جواب است. در پایان باقیمانده آن را نسبت به M میگیریم.
پیمانههای غیرنسبتاول
اگر پیمانهها نسبت به هم اول نباشند، دستگاه ممکن است بیجواب یا چند کلاس جواب داشته باشد. برای دو شرط، تفاضل باقیماندهها باید بر ب.م.م دو پیمانه بخشپذیر باشد؛ سپس دوره جواب ک.م.م پیمانههاست.
مثال و تست کوتاه
دستگاه x≡2 (mod 3) و x≡3 (mod 5) را حل میکنیم. از x=2+3t، شرط دوم 3t≡1 (mod 5) میدهد؛ وارون 3 برابر 2 است، پس t≡2 و x≡8 (mod 15).
چکلیست حل تست
- برای یکتایی ساده، پیمانهها دوتادوتا نسبتاول باشند.
- جواب نهایی را در همه شرطها آزمایش کن.
- دوره جواب در حالت نسبتاول حاصلضرب پیمانههاست.