欧拉定理
如果正整数(n)和整数(a)互质，那么就有
[a^{varphi(n)}equiv 1\,mod\,n
]
其中(varphi(n))是欧拉函数
证明：
令(Phi={x_1,x_2,cdots,x_{varphi(n)}})表示小于数(n)且与(n)互质的数的集合
那么集合(aPhi={ax_1,ax_2,cdots,ax_{varphi(n)}})中的数模(n)的余数都不同，这里可用反证法，假设(ax_iequiv ax_j\,mod\,n)，由于(gcd(a,n)=1)，推出(x_iequiv x_j\,mod\,n)，这是不可能的
所以集合(aPhi={ax_1,ax_2,cdots,ax_{varphi(n)}})模(n)的余数集合({ax_1\%n,ax_2\%n,cdots,ax_{varphi(n)}\%n})与({x_1,x_2,cdots,x_{varphi(n)}})是相同的（次序不一样）
所以
[egin{align}
prod_{i=1}^{varphi(n)}{x_i} &equiv left(prod_{i=1}^{varphi(n)}{ax_i}
ight)\,mod\,n\
&equiv left(a^{varphi(n)}prod_{i=1}^{varphi(n)}{x_i}
ight)\,mod\,n\
end{align}]
由于(gcd(prod_{i=1}^{varphi(n)}{x_i},n)=1)，所以消去(prod_{i=1}^{varphi(n)}{x_i})，得到
[a^{varphi(n)}equiv 1\,mod\,n
]
即得证