一次同餘問題

同餘 (Congruence)

現有整數 a 、 b  和 n,若 n 整除 (a b) ,這樣我們稱 a 和 b 關於模 n 同餘, 記為 :

a = b (mod n)

e.g. 8 = 2 (mod 3) , 9 = 5 (mod 4) , 28 = 0 (mod 7)


不定方程

問題 : 試求整數 x , y 使 4x + 2y = 5.

各位唔好以為 x , y 是整數這條件會使問題容易了, 事實恰恰相反

方程形如 4x + 2y = 5 稱為不定方程 , 解不定方程其實即是解同餘式, 事實上,

4x + 2y = 5 <=> 2y = 5 4x <=> 4x = 5 (mod 2)

因為 4x 是偶數 , 所以 4x = 0 (mod 2), 但 5 = 1 (mod 2) , 所以 4x = 5 (mod 2) 沒有解 , 亦即是沒有整數 x , y 可使 4x + 2y = 5

這篇文章旨在討論同餘式 ax = b (mod n) 的解 , 從而使不定方程 ax + ny = b 有一個完滿的解答

加 , 減 , 乘 , (除 ?)

兩個同模的同餘式可以進行加 , 減 , 乘運算 , 見下列定理

定理一

如果 a = b (mod n) , c = d(mod n) , 那麼

(i) a + c = b + d (mod n)

(ii) a - c = b - d (mod n)

(iii) ac = bd (mod n)

証明

(i)

a = b (mod n) <=> n | (a b) <=> a b = nk1 , 其中 k1 是整數 ______(*)

同理 , c = d(mod n) <=> n | (c d) <=> c d= nk2 , 其中 k2 是整數 ______(**)

(*) + (**) :

(a + c) (b + d) = n(k1 + k2) <=> n | [(a + c) (b + d)] <=> a + c = b + d (mod n)

(ii) , (iii) 留給閣下自証

e.g. (x 3) = 1 (mod 3) <=> x = 4 (mod 3) <=> x = 1 (mod 3)

e.g. (x / 2) = 7 (mod 9) <=> x = 14 (mod 9) <=> x = 5 (mod 9)

e.g. x = 3 (mod 5) <=> x = 9 (mod 5) <=> x = 4 (mod5)

e.g. 6x = 4 (mod 10) <=> 3x = 2 (mod 10) 是錯的推論 , 其實定理一並沒有討論過有關同餘式如何進行除法運算 , 讀者可把 9 代入 x , 有 6 × 9 = 4 (mod 10) 正確 , 但 3 × 9 = 2 (mod 10) 不正確

由上例可知 , 解同餘式與解等式有很大的差異 , 以下定理敘述同餘式可解條件

定理二

同餘式 ax = b (mod n) 對 x 有解當且僅當 gcd(a , n) | b (i.e. a, n 的最大公因數整除b)

証明

(=>)

設 ax = b (mod n) 有解 , 即存在整數 x 使

n | (ax b) => ax b = nk , (其中 k 是某整數) => ax nk = b

=> gcd(a , n) × { [a/gcd(a , n)] x [n/gcd(a, n)] k } = b

=> gcd(a , n) | b

(<=)

設 gcd(a , n) | b

注意 : 用輾轉相除法 , 我們總能找到整數 s , t 使 gcd(a , n) = as + nt

所以 , 從前設得知

as + nt | b => b = (as + nt)m , (其中 m 是某整數) => b = a(sm) + n(tm)

取 x = sm , 得 b = ax + n(tm) => ax b= n( - tm) => ax = b (mod n)

e.g. 6x = 4 (mod 10) 可解 , 因為 6 和 2 的 最大公因數是 2 , 能整除 4

e.g. 4x = 5 (mod 2) 不可解 , 因為 gcd(4 , 2) = 2 不能整除 5

e.g. 4x = b (mod 9) 不論 b 是什麼整數 , 此式定當有解 , 因為 4 和 9 互質 , 即 gcd(4 , 9) = 1 , 必能整除 b

定理二給出一個判別同餘式是否可解的方法 , 但並未討論到如何一般地解同餘式 , 我們試一試實戰...

e.g. 6x = 4 (mod 5) => (5x + x) = 4(mod 5) => x = 4(mod 5)

i.e. x = . . . , - 11 , - 6 , - 1 , 4 , 9 , 12 , . . . ( 解與解相差是 5 的倍數 ? )

如果 a = b (mod n) 可解 , 解與解相差是否必定是 n 的倍數 ??

不幸地 , 答案是"否" , 見下例

e.g. 8x = 4 (mod 12) , 觀察所得 . . . , 2 , 5 , 8 , . . . 等都是解 , 他們相差都不一定是 12 的倍數

但是仍有下列定理 :

定理三

如果 a 和 n 互質 , 那麼同餘式 ax = b (mod n) 有解 , 且解與解之間相差一個 n 的倍數 , i.e. x = c (mod n) 其中 ac = b (mod n)

証明

ax = b (mod n) => n | (ax b) => ax b = ns , (其中 s是某整數) ___(*)

同理 , ac = b (mod n) => ac b = nt , (其中 t是某整數)___(**)

(*) (**) : a(x c) = n(s t) =>n | a(x c)

因為 a 和 n 互質 , 他們除 1 外沒有公因子 , 所以 n | (x c)

但是如果 a 和 n 不是互質又如何 ?

定理四

如果 ax = ab (mod n) 有解 , 設 gcd (a , n) = c , 那麼 x = b (mod n/c)

這定理說出如何對同餘式進行除運算

証明

ax = ab (mod n) => n | a(x b) => (n/c) | (a/c) (x b)

又 gcd(a/c , n/c) = 1 , 所以 (n/c) | (x b) , 即 x = b (mod n/c)

e.g. 6x = 4( mod 10) => 3x = 2 (mod 5) (定理四) => x = 4 (mod 5) (定理三 , 這裡 c = 4 是一特殊解)

e.g. 60x = 12 (mod 24) => 12x = 12 (mod24) => x = 1 (mod 2)

e.g. 39x = 26 (mod 52) => 3x = 2 (mod 4) => x = 2 (mod 4)

e.g. 12x = 1 (mod 37) 這題較難 , 其實 12 和 37 已是互質 , 所以只須找到一特殊解 c 便可 , 有耐性的話 , c = 1 , 2 , 3 ... 試下去必定找到 (最多試 36 次 , 點解?) , 觸覺敏銳的話 , 有

12x = 1 (mod 37) => 36x = 3 (mod 37) => - x = 3 (mod 37) => x = - 3 (mod 37) => x = 34 (mod 37)

e.g. 求整數 x , y 使 14x + 15y = 11

14x + 15y = 11 => 14x = 11 (mod 15) => - x = - 4(mod 15) => x = 4 (mod 15)

所以 x = 4 + 15 t , 其中 t 為任意整數 , 代入原方程得 y = - 3 - 14 t

故原方程的整數解為 x = 4 + 15 t & y = - 3 - 14 t , 其中 t 為任意整數

e.g. 求整數 x , y 使 21x + 10y = 9

21x + 10y = 9=> 21x = 9 (mod 10) => x = 9 (mod 10)

所以 x = 9 + 10 t , 其中 t 為任意整數 , 代入原方程得 y = - 18 - 21t

故原方程的整數解為 x = 9 + 10 t & y = - 18 - 21t , 其中 t 為任意整數

e.g. 求整數 x , y 使 3x + 6y = 8

3x + 6y = 8=> 3x = 8 (mod 6)

gcd(3 , 6) = 3 不能整除 8 , 所以 x 沒有解

故原方程亦沒有解