中國剩餘定理計算機

中國剩餘定理通常縮寫為 CRT，可將多個模運算條件整合為一個解。例如 x ≡ 2（模 3）表示 x 除以 3 的餘數為 2。本計算機接受三個這樣的方程，找出同時滿足所有條件的最小非負整數。 經典定理適用於模數兩兩互質的情況，也就是任意一對模數的最大公因數皆為一。在此條件下，以所有模數的乘積為模，恰有一個解。模數為 3、5、7 時，乘積為 105。若最小解是 23，則 23、128、233，以及藉由加減 105 所得的所有整數，都滿足相同的方程組。 建構演算法先將所有模數相乘，得到 M。對每個方程，以 M 除以該方程的模數，得到部分乘積。由於模數兩兩互質，該部分乘積在被除去的模數下具有乘法反元素。將各餘數、部分乘積及反元素相乘，即可建立符合一個同餘條件、在其他模數下餘數為零的項。將各項相加後對 M 取模，即得答案。 CRT 的應用遠超過教科書中的數論，涵蓋高效率大整數運算、密碼學實作、編碼理論、曆法週期、輪班排程、電腦代數，以及由餘數重建數值。當困難的計算能拆成多個模數下較小且獨立的計算，再合併結果時，這項定理特別實用。 請輸入整數餘數及大於一的模數。餘數可以是負數或大於模數，因為取模會自動將其正規化。本版本刻意要求模數兩兩互質，符合標準定理並保證唯一剩餘類。模數不互質的方程組有時仍有解，但須額外檢查相容性，不在本計算機的範圍內。請將結果分別除以各模數，核對餘數以驗證答案。