一、同餘基本概念與定義
設 m 為正整數，整數 a、b 除以 m 餘數相同，稱 a、b 對模 m 同餘，記作：
a ≡ b (mod m)
等價條件：m | (a - b)，即 a - b 能被 m 整除。
二、同餘核心性質（定理 1-5）
- 自反性：a ≡ a (mod m)
- 對稱性：a ≡ b ⇒ b ≡ a
- 遞移性：a ≡ b, b ≡ c ⇒ a ≡ c
- 加減乘封閉：若 a ≡ b, c ≡ d，則 a±c ≡ b±d, ac ≡ bd
- 乘冪保持：a ≡ b ⇒ aⁿ ≡ bⁿ
- 約除法則：ca ≡ cb (mod m), (c,m)=d ⇒ a ≡ b (mod m/d)；若 (c,m)=1 可直接約去 c。
- 合併模數：a ≡ b (mod m), a ≡ b (mod n) ⇒ a ≡ b (mod [m,n])
三、經典應用：整除性判斷
例 1：9 的倍數判斷
10 ≡ 1 (mod 9) ⇒ 10ᵏ ≡ 1，故數字 a = Σ aₖ·10ᵏ ≡ Σ aₖ (mod 9)。
∴ 9|a ⇔ 9|各位數字和。
例 2：11 的倍數判斷
10 ≡ -1 (mod 11) ⇒ 10ᵏ ≡ (-1)ᵏ，故 a ≡ a₀ - a₁ + a₂ - ... (mod 11)。
∴ 11|a ⇔ 11|交替和。
例 3：7 的倍數判斷（三位一組）
1000 ≡ -1 (mod 7)，以千進制分組，交替相加減即可判斷。
四、剩餘類與完全剩餘系
- 剩餘類：Kᵣ = {x | x = mt + r}，模 m 有 m 個剩餘類，構成整數的分割。
- 完全剩餘系：從每個剩餘類取一數，共 m 個，兩兩模 m 不同餘。常用集合：{0,1,...,m-1}。
五、歐拉函數 φ(m) 與核心定理
定義：φ(m) = 模 m 完全剩餘系中與 m 互質的數的個數。
例：φ(10)=4（1,3,7,9），φ(7)=6，φ(1)=1。
關鍵定理
- 歐拉定理：(a,m)=1 ⇒ a^φ(m) ≡ 1 (mod m)
- 費馬小定理（歐拉定理推論）：p 為質數，(a,p)=1 ⇒ a^{p-1} ≡ 1 (mod p)；對任意 a，a^p ≡ a (mod p)。
- φ 函數計算公式：
- φ(pᵃ) = pᵃ - p^{a-1}（p 為質數）
- (m,n)=1 ⇒ φ(mn) = φ(m)φ(n)
- m = Π pᵢ^{aᵢ} ⇒ φ(m) = Π pᵢ^{aᵢ-1}(pᵢ-1)
六、綜合範例
例：證 a⁵ ≡ a (mod 30)
30 = 2·3·5，分別用費馬小定理得 a⁵ ≡ a (mod 2,3,5)，再由中國剩餘定理合併得證。
例：(n,10)=1 ⇒ n¹⁰¹ 與 n 末三位相同
證 n¹⁰⁰ ≡ 1 (mod 1000)。φ(125)=100 ⇒ n¹⁰⁰ ≡ 1 (mod 125)；n 為奇數 ⇒ n¹⁰⁰ ≡ 1 (mod 8)；(125,8)=1 ⇒ n¹⁰⁰ ≡ 1 (mod 1000)。
總結
同餘理論是數論核心工具，廣泛應用於密碼學（RSA）、雜湊、校驗碼、演算法設計等領域。掌握歐拉函數與費馬小定理，能高效解決大數模運算與同餘方程問題。
