中國剩余定理

題目

今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？

題目抽象

求數(shù)x，使得 \(\begin{cases}x \equiv 2 (mod 3) \\ x \equiv 3(mod5) \\ x \equiv 2 (mod7) \end{cases}\)

解法

分別考慮特征方程
1.\(\begin{cases}x \equiv 1 (mod 3) \\ x \equiv 0(mod5) \\ x \equiv 0 (mod7) \end{cases}\)

2.\(\begin{cases}x \equiv 0 (mod 3) \\ x \equiv 1(mod5) \\ x \equiv 0 (mod7) \end{cases}\)

3.\(\begin{cases}x \equiv 0 (mod 3) \\ x \equiv 0(mod5) \\ x \equiv 1 (mod7) \end{cases}\)

易得對于方程1,由方程組中的2、3兩式可設(shè)$x = 35m_1 \(,又x滿足\)x mod 3 = 1$,所以\(35m_1 mod 3 =1\)。利用拓展歐幾里得可求出對于上式推導(dǎo)的不定方程\(35m_1 + 3y = 1\),求得\(m_1\)的最小整數(shù)解為\(2\),即\(x_1 = 70\).
同上述步驟可求得\(x_2 = 21\),\(x_3 = 15\).

可以看出，滿足上述特征方程的每一個解\(x_i\),均是其中另外兩個數(shù)的倍數(shù),與剩下的數(shù)關(guān)于1同余.那么我們可以知道,若有一個整數(shù)\(p\),那么可以看出,\(px\)是其特征方程關(guān)于該數(shù)與0同余的數(shù)的倍數(shù),關(guān)于 關(guān)于該數(shù)與1同余的數(shù) 與 \(p\) 同余。

也就是說,舉第一個方程為例, \(\begin{cases}px \equiv p (mod 3) \\ px \equiv 0(mod5) \\ px \equiv 1 (mod7) \end{cases}\)

現(xiàn)在來考慮從特征方程的解構(gòu)造原同余方程的解。

從上面的說明可以得出,\(2x_1\)可以滿足第一個方程,\(3x_2\)可以滿足第二個方程,\(2x_3\)可以滿足第3個方程。即將余數(shù)帶入上文的字母p,從而使得滿足該條件。

那么如何使得3個條件同時滿足?

將解得3個x值相加,就可以得到一個滿足所有條件的解。

簡單的證明:
$x_1 | 5 且 x_1 | 7 , x_ 1 mod 3 = 2 $
略.

可以得出一個解\(x_1 * 2 + x_2 * 3 + x_3 * 2 = 233\)。
但這個是最后的解嘛?顯然不是，因?yàn)檫@個解大于105.105是同余方程中所有模數(shù)的最小公倍數(shù),顯而易見地答案有無數(shù)個,如果最小的答案是\(t\),那么任何的\(t + 105k\)也是答案,因?yàn)槊恳粋€105總可以被3個模數(shù)同時整除.

所以最后的答案是\((x_1 * 2 + x_2 * 3 + x _3 * 2 ) mod 105 = 23\),這只是滿足條件的最小解,解有無數(shù)個,具體來說,解集是\(\{x | x = 23 + 105k\}\).注意，本證明中出現(xiàn)的所有數(shù)均為非負(fù)整數(shù)。

推廣

等更。