若a与n互质, 则a^(φ(n)) === 1 (mod n)

φ(n) = p1, p2, p3 ……, pk; p1-pk是n中的所有和n互质的数, 互质, 比如a、b互质, 那么二者最大公约数就只有1

又因为 a 也和 n互质, 所以
a*p1 a * p2 …… a * pk 均与n互质

所以a^(φ(n)) * (p1, ……, pk) === (p1, ……, pk) (mod n);

所以a^(φ(n)) === 1 (mod n);

费马小定理
a^(p-1) === 1 (mod p) 当且仅当p是质数, 且a p 互质.