设 $\phi(N)$ 为欧拉函数，其值等于 $1-N$中所有与N互质的数的个数，则有：
$$若a与n互质，则a^{\phi(n)} \equiv 1(\mod n)$$

证明：设$1-n$中与n互质的数为:
$$k_1、k_2、k_3、…、k_{\phi(n)} \tag{1}$$
则序列：
$$ak_1、ak_2、ak_3、…、ak_{\phi(n)} \tag{2}$$

(1)和(2)在对$n$取模的条件下完全等价，只是顺序不同。

故分别将其相乘则有有：

$$k_1k_2k_3…k_{\phi(n)} \equiv a^{\phi(n)}k_1k_2k_3…k_{\phi(n)} (\mod n)$$

进一步变形得到:

$$a^{\phi(n)} \equiv 1 (\mod n) \tag{3}$$

其中当$p$为质数时，则有$\phi(p) = p-1$,代入等式$(3)$中可以得到费马小定理：
$$a^{p-1} \equiv 1 (\mod p), 其中a与p互质$$