费马小定理

要学数论肯定会遇见这个东西

它的结论就是很简单一个式子 \[ a^p≡a\quad(mod\space p) \] 其中p是个质数，a是任意自然数

但我觉得证明它这件事是蛮有趣的

去年暑假打mai的人多，我是坐在mai机前想破脑袋也没想出来

当时上网搜基本都是群论或者其他我没学过的东西

我就想着，证明这东西这么难吗？这种东西费马是怎么敢不写证明就跟朋友交流的

要是我有什么主意但不写证明我觉得我朋友会打死我(

当我刚认识到这个定理时，感觉这东西好反直觉，但好像又有点道理，因为p既是指数也是模数，而且还得是个质数，肯定有什么东西在里面

因为那会我才只知道同余两侧能同加减这种还算符合直觉的结论

我这人蛮懒的，不认识的东西能不学就不学，所以没耐心去了解群论

后面真的在网上找到了连高中生都能明白的证明，我十分喜欢它

用的是二项式定理+数学归纳法

第一次看到这种证明法是在这里

费马小定理（Fermat's Little Theorem）

我这篇文章只是相当学了以后把这个方法抄一遍

由于数论中只研究整数，不像实数一样连续，数学归纳法在高中课本里属于随便讲一下的知识，在这里就成了强而有力的武器

那对谁归纳呢？

p？不太合适，因为它是质数，在自然数上它不会连续

所以不妨对a作归纳，因为a是任意自然数

证明： \[ 0^p≡0\quad(mod\space p) \] 这不就废话

那现在只需要 \[ 假设k^p≡k\quad(mod\space p)\newline证明(k+1)^p≡k+1\quad(mod\space p) \] 看着同余式感觉没有头绪，还是把它转化成我们熟悉的等式吧 \[ 即\newline 假设fn=k^p-k\newline 求证p|(k+1)^p-(k+1) \] 接下来要么用k^p-k来凑(k+1)^p-(k+1)

要么在(k+1)^p-(k+1)中找k^p-k

虽然后者也不简单，但感觉前者的难度更抽象，所以还是拆括号吧

对于这种括号带指数，我们只能用牛老爷的二项式定理暴力撕开它 \[ (k+1)^p-(k+1)=C_p^0+C_p^1k+C_p^2k^2+...+C_p^{p-1}k^{p-1}+C_p^pk^p-(k+1) \] 只要熟悉组合数，那么就很容易能发现 \[ C_p^0=1,C_p^pk^p=k^p \] 所以就剩下 \[ (k+1)^p-(k+1)=C_p^1k+C_p^2k^2+...+C_p^{p-1}k^{p-1}+(k^p-k) \] 要们现在的目的是根据别人画好的靶来射箭

我们已经明白p能够整除这一坨，根据分配律也就是里面随便拎一个项出来都是p的倍数

其中(k^p-k)已经是p的倍数了，那么就剩下一堆的组合数乘k的相加

那这个倍数会来自k,k²,k³...k^p吗？那不应该

如果我们觉得它对，那也就是在说任意自然数的1-p都会是p的倍数，那费马小定理就不该这么写了

或者说，这个k只是个路人，它可以是任何数，我们并不关心它是多少。只要p满足条件，那么同余式就成立。就像飘洋过海，我们关心的是船，只要船符合条件了就能够过海，不论上面载的是谁，但船不行就会翻，不论载的是谁

那么证明的方向也就不可能是k

只能剩下C_p¹,C₀²...C_p^p-1了 \[ C_p^n=\frac{p!}{n!(p-n)!}=p\frac{(p-1)!}{n!(p-n)!} \] 简单用定义式拆一下

就很明显 \[ C_p^n是整数,p是整数\newline那么\frac{(p-1)!}{n!(p-n)!}是整数\newline所以C_p^n是p的倍数\newline即(k+1)^p-(k+1)=C_p^0+C_p^1k+C_p^2k^2+...+C_p^{p-1}k^{p-1}+C_p^pk^p-(k+1)是p的倍数 \] 如此我们就证明了费马小定理

吗？

有没有发现，到这里，我们还没用过一个条件——p是质数

如果这样就能得证，我随便就有一个反例 \[ 2^4≡2\quad(mod\space 4)\newline这显然不成立吧 \] 这里就是有一个小陷阱。我想了十几分钟才明白，我是笨蛋😢

两数相乘得整数，其中一数是整数，另一因数是整数吗？

如果你还说：这不废话吗，难道还要整数乘小数才能得整数？

那你再想两秒钟，是不是发现不对了？ 2*0.5是多少？10*0.3是多少？

是不是，一下就能明白错在哪

分子和分母可以约分啊！

我们希望另一因数是整数，不然我们就证不出费马小定理

重新审视一下问题 \[ C_p^n=\frac{p!}{n!(p-n)!}=p\frac{(p-1)!}{n!(p-n)!} \newline是题设的质数，C_p^n是组合数 \newline组合数从其诞生的由来就决定它一定是整数(或者你想想阶乘的定义都能明白为什么它是整数) \newline很明显的是\frac{(p-1)!}{(p-n)!}一定是整数，结合n的取值范围和阶乘的定义就能明白 \newline C_p^n=p\frac{(p-1)!}{n!(p-n)!}=p\frac{\frac{(p-1)!}{(p-n)!}}{n!} \] 我们不要去正着思考，什么条件下右边那一坨会是整数

思考这个"什么条件"想想就复杂不是吗？

实际上我们并不关心能满足题意的所有情况

我们只是想知道，p是质数这个条件够不够让右边那一侧成为整数

n∈[1,p-1]，那么n!最多也就是1*2*...(p-2)(p-1)

里面每一个因子都是小于p的数

对于质数p，任何小于p的数都与它互质

所以p不可能与n!有公因数，也就是没法约分

如果这种情况下右边那一坨还不是整数的话，乘积一定会留有一个不可约的分母，使得乘积不为整数

所以只能推断右边那坨是整数 \[ 所以(k+1)^p-(k+1)=C_p^0+C_p^1k+C_p^2k^2+...+C_p^{p-1}k^{p-1}+C_p^pk^p-(k+1)一定是p的倍数 \] 由此我们证明了费马小定理 \[ a^p≡a\quad(mod\space p)\newline a是任意自然数，p是任意质数 \] 如果a和p互质的话(因为p是质数，要使a和p互质，只需要a不是p的倍数就行)

还能写成 \[ a^{p-1}≡1\quad(mod\space p)\newline a是任意自然数，p是任意质数，且a和p互质 \]