定义

对于正整数a和n，若a与n互质，有a``φ(n)``≡ 1 (mod n)
读作a的φ(n)次方在模n的情况下同余

证明

设1~n中与n互质的数为s1 = {a1, a2, ..., an}
s2 = {aa1, aa2, ..., aan}满足

  • aai与n互质

已知a与c互质，b与c互质，证a*b与c互质
a的分解质因数与c的各不相同
b的分解质因数与c的各不相同
则ab的分解质因数与c的各不相同
故a` b与c` 互质

  • aai与aaj各不相同

反证法：假设aai == aaj (mod n)
因为a与n互质，两边可同时除以a
得 ai == aj (mod n) 与已知不符，得出矛盾
说明aai与aaj各不相同

s1和 s2 都是 1~n 中的全体与n互质的数的集合，故 s1 <==> s2
欧拉定理.pdf

费马小定理

当n为质数时φ(n) = n - 1

a``φ(n)``≡ 1 (mod n) <==> a``n-1``≡ 1 (mod n)