专门去查了一下这个定理： 欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n) 欧拉定理：gcd(a, n) = 1，则a^φ(n) ≡ 1 mod n 对于互质的整数a和n，有a^φ(n) ≡ 1 mod n 证明： 首先证明下面这个命题： 对于集合Z = {X1,X2,...,Xφ(n)}，Xi为第i个小于n且和n互质的正整数 考虑集合 S = {aX1 mod n,aX2 mod n,...,aXφ(n) mod n} 则S = Z 证明: a, n互质，Xi与n互质，那么aXi与n互质 对于Z中两个元素Xi和Xj，如果Xi ≠ Xj 则aXi mod n ≠ aXj mod n，若aXi mod n = aXj mod n， 那么a(Xi - Xj) mod n = 0, a, n互质那么Xi - Xj mod n = 0 由于 0 < Xi, Xj < n显然不可能。因此S中的元素各不相同，这样S中含有φ(n)个与n互 质的正整数，且满足每个元素小于n所以，很明显，S = Z 既然这样，那么 (aX1 × aX2×...×aXφ(n))mod n = (aX1 mod n × aX2 mod n × ... × aXφ(n) mod n)mod n = (x1 × x2 × ... × xφ(n))mod n 考虑上面等式左边和右边 最左边等于(a^φ(n) × (x1 × x2 × ... × xφ(n)) mod n 最右边等于(x1 × x2 × ... × xφ(n))mod n 得到(a^φ(n) - 1)(x1 × x2 × ... × xφ(n)) mod n = 0 而(x1 × x2 × ... × xφ(n))mod n 和 n互质,所以 a^φ(n) ≡ 1 mod n推论：当n为素数时，φ(n) = n - 1, a^(n - 1) - 1 mod n = 0
