费马小定理 & 欧拉定理

费马小定理

定理

如果 那么有 a^p − 1 ≡ 1 (mod  p)

证明

引理 1

若 a ⋅ c ≡ b ⋅ c (mod  m) 且 c ⊥ m，则 a ≡ b (mod  m)。

证明 1

a ⋅ c ≡ b ⋅ c (mod  m) 可得 (a − b) × c ≡ 0 (mod  m)，又因为 c ⊥ m，那么 (a − b) × c 当且仅当 a − b 是 m 的倍数即 a − b ≡ 0 (mod  m)，即可得 a ≡ b (mod  m)。

---

引理 2

若 a ⊥ m，则 {a, 2a, 3a, …, (m − 1)a} 是一个模 m 的完全剩余系。

证明 2

考虑使用反证法。

假设 使得 i × a ≡ j × a (mod  m)，又因为 a ⊥ m，根据 引理 1，可得 i ≡ j (mod  m)，而 i, j ∈ [1, m − 1]，所以 i ≡ j (mod  m) 当且仅当 i = j，与假设矛盾，故得证。

由上述引理，可知 {1, 2, 3, …, p − 1} 与 {a, 2a, 3a, …, (p − 1)a} 均为模 p 的完全剩余系，那么将两个集合内部元素分别相乘，可得 (p − 1)! ≡ (p − 1)! × a^p − 1 (mod  p) 又因为 p ∈ ℙ，所以 φ(p) = p − 1，故可得 p ⊥ (p − 1)!，根据 引理 1，两边同时约去 (p − 1)!，可知 a^p − 1 ≡ 1 (mod  p) 证毕。

欧拉定理

扩展欧拉定理