第5章 不定方程與中國剩餘定理
5.1 先檢查是否可解,再構造全部解
對不全為零的整數 a、b,令 g=gcd(a,b)。若 ax+by=c 有整數解,g 必整除 c;若 g∣c,把 ua+vb=g 兩側乘 c/g 就得到一組解。當 a、b 皆非零,若 (x₀,y₀) 是一組解,所有整數解為 x=x₀+(b/g)t,y=y₀−(a/g)t,t 為任意整數。代入可驗;反過來,兩組解相減,(a/g)(x−x₀)=−(b/g)(y−y₀),兩係數互質,故 b/g 整除 x−x₀(可乘互質線性組合驗出),於是正好有上述參數式。若只有一個係數非零,先檢查它是否整除 c。整除時,對應變數等於 c 除以該係數,另一個變數任取。若兩係數皆零,只有 c=0 才有解,此時所有整數對都可。
取 m,n≥2。求 x≡r(mod m)、x≡s(mod n)時,先把第一式寫成 x=r+mt。第二式等於 mt≡s−r(mod n)。若 m、n 互質,乘 m 的模 n 反元素即給 t 的唯一模 n 類,因此 x 在模 mn 下唯一。這是兩個模數的中國剩餘定理;多個兩兩互質的模數可逐次合併,因前面乘積仍與下一個互質。
若模數不互質,令 g=gcd(m,n)。差 s−r 必被 g 整除,否則無解;可整除時,將 mt−(s−r) 被 n 整除這句話整體除以 g,得到模 n/g 的條件。當 n/g>1,m/g 與 n/g 互質,所以 m/g 可逆,t 有唯一模 n/g 類。當 n/g=1,所有 t 都可。兩種情形中,所有 x 都由一個解加上 m(n/g) 的整數倍得到,故最小正週期為 m(n/g)=lcm(m,n)。
5.2 四個例題
例題1 從一組解走到全部解
15x+21y=6,gcd=3,且 15(−1)+21(1)=6。約去 3 得 5x+7y=2,兩係數互質。全解為 x=−1+7t、y=1−5t;例如 t=1 給 (6,−4),兩項加總仍是 6。
例題2 先用可解條件擋掉不可能
6x+10y=7 的左式每一項都是偶數,右式為奇數。等價地,gcd=2 不能整除 7,沒有整數解。
例題3 用反元素找同餘交會
求 x≡2(mod 3)、x≡3(mod 5)。令 x=2+3t,需 3t≡1(mod 5);3×2≡1,所以 t≡2。全解 x=8+15k,8 除以 3、5 分別餘 2、3。
例題4 非互質仍可能相容
求 x≡2(mod 4)、x≡4(mod 6)。令 x=2+4t,得到 4t≡2(mod 6)。除去共同的 2,模數也變為 3:2t≡1(mod 3),所以 t≡2。全解 x=10+12k,而非只每隔 24 一次。
5.3 練習
- B13-C05-Q01 8x+12y=20 有整數解嗎?若有,給一組。
- B13-C05-Q02 上一題的全部整數解?
- B13-C05-Q03 9x+6y=4 有整數解嗎?
- B13-C05-Q04 若 0x−5y=20,變數可取哪些整數?
- B13-C05-Q05 解 x≡1(mod 4)、x≡2(mod 5)。
- B13-C05-Q06 −3 是否也是上題解?
- B13-C05-Q07 x≡1(mod 4)、x≡2(mod 6)能同時成立嗎?
- B13-C05-Q08 求同時滿足 x≡3(mod 8)、x≡3(mod 4)的解。
- B13-C05-Q09 解 x≡1(mod 6)、x≡3(mod 8)。
- B13-C05-Q10 已知有兩個共同解,為什麼其差被 lcm(m,n) 整除?
5.4 完整解答
Q01
gcd=4,且 4∣20,所以可解。直接取 x=1、y=1,8+12=20。
Q02
除以 4 得 2x+3y=5。與 (1,1) 相減得 2(x−1)=−3(y−1),故 x−1 是 3 的倍數,寫 x=1+3t;代回得 y=1−2t。
Q03
沒有。左式必被 gcd(9,6)=3 整除,但 4 除以 3 餘 1。
Q04
唯一的 y 為 −4,x 不出現在限制中,所以可取任何整數。沒有必要除以係數 0。
Q05
令 x=1+4t,得到 4t≡1(mod 5)。4×4≡1(mod 5),所以可乘反元素 4,得 t≡4。故 x≡17(mod 20)。
Q06
是,−3 與 17 差 −20;直接算其模 4、模 5 的餘數,分別為 1、2。
Q07
不能。第一式要求奇數,第二式要求偶數;亦即 g=2 不整除餘數差 1。
Q08
模 8 的條件已保證模 4 的條件,因 8 是 4 的倍數,所以全解 x=3+8t。兩模數的最小公倍數是 8。
Q09
令 x=1+6t。6t≡2(mod 8)等價於 3t≡1(mod 4),故 t≡3(mod 4)。x≡19(mod 24),可代入驗算。
Q10
每個模數都整除兩解的差,因此差是共同倍數。逐一比較質因數指數就知它被 lcm 整除;若差是 0,也能被 lcm 整除。