费马小定理

设\(p\)是素数，\(a\)是任意整数且\(a\)，则 \[a^{p-1} \not\equiv 1 \mod p\]

证明过程

尝试证明一般性的费马小定理。首先证明如下断言。

引理 9.2 设\(p\)是素数，\(a\)是任何整数且\(a \not\equiv 0 \mod p\)，则数\(a,2a,3a, \cdots , (p-1)a \mod p\)与数\(1,2,3, \cdots ,(p-1)\)相同，尽管他们的次序并不相同。

证明 反证法，假设存在两个模\(p\)同余的\(ka,ja\)，且两个数本身是不同的，做差后在这个假设下反推，若同余，而\(p\)为素数，素数整除乘积，必定整除乘积的一个因数，而我们从要求中已经得到\(p \nmid a\)，而又\(\vert k-j \vert < p-1\)，得到\(k-j = 0\)，而这与我们假设两者本身不同相违背，得证。

利用该引理，容易完成费马小定理的证明，引理说明数列\(a,2a,3a, \cdots , (p-1)a \mod p\)与数列\(1,2,3, \cdots ,(p-1) \mod p\)相同，构造：

\[a \cdot (2a) \cdot (3a) \cdots ((p-1)a) \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \mod p\]

从左边提出\(p-1\)个\(a\)得：

\[a^{p-1} \cdot (p-1)! \equiv (p-1)! \mod p\]

根据同余式两边消的性质（参加另一篇《同余式、线性同余定理》拓展性质 2），我们便可以得到。

\[a^{p-1} \equiv 1 \mod p\]