同一餘數的學問

同餘新世界

德國數學家,有數學王子之稱的高斯 (Carl Friedrich Gauss 1777-1855) 也這樣的說過:若一數 m 可整除 a 與 b 的差,則 a 和 b 是同餘 (Congruence) ;反之,則是不同餘 (Incongruence) 。數 m,我們稱之為模 (Modulo)。

以現在的符號,我們這樣寫

a = b (mod m)

其寫所有同餘式 (Congruence Expression) 的等號均是三橫劃,但由於網頁內行文所限,故本網全用兩橫劃之等號。

上式,我們讀作在模 m 下,a 同餘於 b 或 b 是 a 對模 m 的剩餘 (Residue) 。若 b 介乎於 0 和 m-1 之間,我們稱之為模 m 的最小非負剩餘 (Least Non-negative Residue);若 b 介乎於 -m/2 和 m/2 之間,我們稱之為模 m 的絕對最小剩餘 (Absolutely Least Residue)。若表示不同餘,我們會在等號加上一斜線。留意,對於模數 m ,我們必須要求其為正數,至於式中的 a 或 b 則可正可負可零。

 

如 14 = 8 (mod 6) 或 35 = 0 (mod 5) 等。

其實同餘有很多性質是我們用得上,現在讓我們來看看吧!

a = a (mod m) ;

若 a = b (mod m) 則有 b = a (mod m);

若 a = b (mod m) 及 b = c (mod m) 則有 a = c (mod m);

若 a = b (mod m) 則有 a*c = b*c (mod m) 對任意整數 c ;

若 a = b (mod m) 則有 an = bn (mod m) 對任意整數 n ;

若 a = b (mod m) 及 c = d (mod m) 則有 a ± c = b ± d (mod m) 及 a*c = b*d (mod m);

若 a = b (mod m) 及 c 為 a, b, m 的公因子之一,則有 a/c = b/c (mod m/c);

若 c*a = c*b (mod m) 則有 a = b (mod m/(c,m)) 特別是當 (c,m) = 1 時有 c*a = c*b (mod m) 得 a = b (mod m);

若 a = b (mod mi) ,其中 i 取由 1 至 n,則 a = b (mod M),其中 M 為 m1 、 m2 至 mn 的最小公倍數 (Least Common Multiple , L.C.M.)。

若以所有與 a 在模 m 同餘的數組成的一個集合,我們稱其為模 m 的同餘類 (Congruence Class) 或剩餘類 (Residue Class)。如模 m 的所有剩餘 (同餘) 類便是 0, 1, 2, 3, ....., m-1,這我們稱模 m 的最小非負剩餘 (同餘) 類 (Least Non-negative Residue (Congruence) Class),若取 0, ±1, ±2, ±3, ...... , ±m/2,這我們稱模 m 的絕對最小剩餘 (同餘) 類 (Absolutely Least Residue (Congruence) Class)。

 

單看性質是不足夠的,我們還得如何運用。不講不知,原來同餘是數學競賽 (Mathematics Competition) 中題目的常客,到底如何運用同餘的知識來競賽,且看《同餘小問題》一文吧!

 

同餘下的除法

除法會出現餘數或小數的問題,故在同餘式的計算,某些除法實可被乘法取代。

若 c 與 m 互素 (Coprime),即 (c,m) = 1 ,我們必然找到整數 a, b 使 a*c + b*m = 1。在模 m 的同餘下,有:

 a*c + b*m = a*c = 1 (mod m)

亦即存有一數 a 使之與 c 的積為 1。

 

這樣,若我們考慮某數 除以 c 的問題,即等同考慮該數乘以 a 的值了。

 

例:求 18 / 7 (mod 20) 的值。

由於 7*3 - 20*1 = 1,故得 7*3 = 1 (mod 20)。

即 18 / 7 = 18 * 3 = 54 = 14 (mod 20)。

 

又例:求 4 / 23 (mod 74) 的值。

由於 23*29 - 74*9 = 1,故得 23*29 = 1 (mod 74)。

即 4 / 23 = 4 * 29 = 116 = 42 (mod 74)。

 

至於除數  c 不與模數 m 互素,這情況除法不一定有解了。