同一餘數的學問

德國數學家，有數學王子之稱的高斯 (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 Remainder modulo m) ；若 b 介乎於 -m/2 和 m/2 之間，我們稱之為模 m 的絕對最小剩餘 (Absolutely Least Remainder modulo m)。若表示不同餘，我們會在等號加上一斜線。留意，對於模數 m ，我們必須要求其為正數，至於式中的 a 或 b 則可正可負可零。

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

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

若 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) 對任意整數 (Integer) c ；

若 a = b (mod m) 則有 aⁿ = bⁿ (mod m) 對任意整數 n ；

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

若 a = b (mod m) 及 c = 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 m_i) ，其中 i 取由 1 至 n，則 a = b (mod M)，其中 M 為 m₁ 、 m₂ 至 m_n 的最小公倍數 (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 modulo m)，若取 0, ±1, ±2, ±3, ...... , ±m/2，這我們稱模 m 的絕對最小剩餘 (同餘) 類 (Absolutely Least Residue (Congruence) Class modulo m)。

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