费马小定理的证明以及逆元

· · 算法·理论

提示：由于本人才疏学浅，不得不使用小学数学进行证明。敬请原谅。

费马小定理及其证明：

设 p 是素数，对于任意整数 a 且 p \nmid a，都成立：

a^{p-1} \equiv 1 \pmod{p}

证明

前置知识：若素数 p 能整除两个数的乘积，那么 p 至少可以整除其中一个数。

第一步

设立一个数 a，分别乘以 1,2,3,\dots,p-1。得到：

a,2a,3a,\dots,(p-1)a

第二步

此步可以证明上面的每一个数除以 p 的余数都不同。

如果我们假设有 i \times a,j \times a 除以 p 余数相同 (i<j)。

根据同余定理，我们得出 j-i 一定可以被 p 整除。但是，我们发现由于 j-i 最大为 (p-1)-1=p-2。在 1 \sim (p-2)，是不可能出现 p 的倍数的。因此余数各不相同。

所以一共有 p-1 个余数，它们互不相同，并且都在 1 到 p-1 之间。

第三步

把第一步得出来的数列相乘，得到：

\begin{aligned} & a \times 2a \times 3a \times \cdots \times (p-1)a\\ = & a^{p-1} \times \bigl(1 \times 2 \times 3 \times \cdots \times (p-1)\bigr) \end{aligned}

第四步

由于 1 \sim (p-1) 除以 p 的余数是它自己。并且也互不相同。联系第二步的结论，发现它们的余数集合相同，都是 1 \sim (p-1) 的一个排列。得出此式（有点长）：

a^{p-1} \times (1 \times 2 \times 3 \times \cdots \times(p-1)) \equiv 1 \times 2 \times 3 \times \cdots \times(p-1) \pmod{p}

第五步

因为 p 是素数，而且 1,2,3,\dots,(p-1) 都不可以被 p 整除，所以其乘积也不能被 p 整除。因此模 p 有逆元,两边同乘它的逆元，得：

a^{p-1} \equiv 1 \pmod{p}

以上就是费马小定理的证明了。感谢观看。

逆元及其证明

逆元定义

对于非零整数 a,p，如果存在 b。使得 ab \equiv 1 \pmod{p}。就称 b 是 a 在模意义下的逆元。

快速幂求逆元

先说结论：\frac{a}{b} \equiv a \times b^{p-2} \pmod{p}

推导

不难发现 \frac{a}{b} \equiv a \times b^{-1} \pmod{p}

那么定义 b^{-1} 是满足 b \times b^{-1} \equiv 1 \pmod{p} 的数。

联系费马小定理，得出：b^{p-1}\equiv b \times b^{p-2} \equiv 1 \pmod{p}

由于 b \times b^{-1} \equiv 1 \pmod{p}，所以 b^{-1}\equiv b^{p-2} \pmod{p}。

所以a \times b^{-1} \equiv a \times b^{p-2} \pmod{p}。