某些数论知识
转载自
欧拉函数 ： 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。
完全余数集合： 定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。 显然 |Zn| ＝φ(n) 。
有关性质： 对于素数 p ，φ(p) = p -1 。 对于两个不同素数 p， q ，它们的乘积 n = p q 满足 φ(n) = (p -1) (q -1) 。 这是因为 Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) p} - {q, 2q, ... , (p - 1) q} ， 则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) (q -1) ＝φ(p) φ(q) 。
欧拉定理 ： 对于互质的正整数 a 和 n ，有 aφ(n) ≡ 1 mod n 。
证明： ( 1 ) 令 Zn = {x1, x2, ..., xφ(n)} ， S = {a x1 mod n, a x2 mod n, ... , a xφ(n) mod n} ， 则 Zn = S 。 ① 因为 a 与 n 互质， xi (1 ≤ i ≤ φ(n)) 与 n 互质， 所以 a xi 与 n 互质，所以 a xi mod n ∈ Zn 。 ② 若 i ≠ j ， 那么 xi ≠ xj，且由 a, n互质可得 a xi mod n ≠ a * xj mod n （消去律）。
( 2 ) aφ(n) x1 x2 ... xφ(n) mod n ≡ (a x1) (a x2) ... (a xφ(n)) mod n ≡ (a x1 mod n) (a x2 mod n) ... (a xφ(n) mod n) mod n ≡ x1 x2 ... * xφ(n) mod n 对比等式的左右两端，因为 xi (1 ≤ i ≤ φ(n)) 与 n 互质，所以 aφ(n) ≡ 1 mod n （消去律）。 注： 消去律：如果 gcd(c,p) = 1 ，则 ac ≡ bc mod p ⇒ a ≡ b mod p 。
费马定理 ： 若正整数 a 与素数 p 互质，则有 ap - 1 ≡ 1 mod p 。 证明这个定理非常简单，由于 φ(p) = p -1，代入欧拉定理即可证明。
参考来源