对于互质的正整数 a 和 n ,有 aφ(n) ≡ 1 mod n。

首先考虑两个集合:
Zn = {x1,x2,···xφ(n)}
S = {a * x1 mod n,a * x2 mod n,···a * xφ(n) mod n}

对于这两个集合,有以下点:
1. Zn和S两个集合元素个数都为φ(n)个。
2. a与n互质,xi(1 ≤ i ≤ φ(n))与n互质,那么a * xi与n互质,所以a * xi ∈ Zn。
3. 对于i ≠ j,那么xi ≠ xj,可得a * xi mod n ≠ a * xj mod n。证明很简单,因为a * xi - a * xj的值肯定不是n的倍数。

根据以上几点,我们知道:
1. 集合Zn和集合S元素个数相等。
2. 集合S中的元素都属于Zn。
3. 集合S中的任意两个元素值不相等。

所以,Zn = S。

两个集合所有元素乘积也相等
x1 * x2 * ··· * xφ(n) =
(a * x1 mod n) * (a * x2 mod n) * ··· * (a * xφ(n) mod n)

等式两遍mod n
x1 * x2 * ··· * xφ(n)
(a * x1 mod n) * (a * x2 mod n) * ··· * (a * xφ(n) mod n) mod n

等式右侧合并a得
x1 * x2 * ··· * xφ(n)
aφ(n) * (x1 mod n) * (x2 mod n) * ··· * (xφ(n) mod n) mod n

简化
x1 * x2 * ··· * xφ(n)
aφ(n) * x1 * x2 * ··· * xφ(n) mod n

因为x1 * x2 * ··· * xφ(n)与n互质,可消去
1 ≡ aφ(n) mod n

得到

aφ(n) ≡ 1 mod n。

费马定理是欧拉定理的一个特例,即n为素数


a是不能被质数p整除的正整数,则有 ap-1 ≡ 1 mod p。