费马小定理

1. 定义

假如a是一个整数， p 是一个质数，那么

是p 的倍数，可以表示为\begin{array}{c} a^p \equiv a \,\, (mod \,\, p) \end{array}

如果a不是p的倍数，这个定理也可以写成

2. 证明

• 对于 a=0 的情况，定义中的第一个等式显然成立。
• 对于 a≠0 的情况，则 (a,p)=1。此时模p 的所有非零的余数，在同于意义下对乘法构成一个群，此群的阶是 p−1。根据群论中的拉格朗日定理，对于该群中的 ∀x，都有 x的阶必整除群的阶，故命题得证。

3. 推广

• 费马小定理是欧拉定理的一个特殊情况。
• 卡迈克尔函数比欧拉函数更小，费马小定理也是它的特殊情况。它的特殊情况。