首先考虑两个集合：
Zn = {x₁，x₂，···x_φ(n)}
S = {a * x₁ mod n，a * x₂ mod n，···a * x_φ(n) mod n}

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

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

所以，Zn = S。

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

等式两遍mod n
x₁ * x₂ * ··· * x_φ(n) ≡
(a * x₁ mod n) * (a * x₂ mod n) * ··· * (a * x_φ(n) mod n) mod n

等式右侧合并a得
x₁ * x₂ * ··· * x_φ(n) ≡
a^φ(n) * (x₁ mod n) * (x₂ mod n) * ··· * (x_φ(n) mod n) mod n

简化
x₁ * x₂ * ··· * x_φ(n) ≡
a^φ(n) * x₁ * x₂ * ··· * x_φ(n) mod n

因为x₁ * x₂ * ··· * x_φ(n)与n互质，可消去
1 ≡ a^φ(n) mod n

得到

a^φ(n) ≡ 1 mod n。

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