欧拉函数：欧拉函数是数论中非常重要的函数。 欧拉函数是指：对于正整数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 ε锌。 ②若i≠j，则xi≠xj，由a与n互质可得a*xi mod n≠a*xj mod n（消去律）。