费马小定理

破除误解#

第一个公开证明属于欧拉，时间要拆成两步，不能并成「1736 年发表」。1736 年 8 月 2 日，这篇证明被宣读。刊出要到 1741 年，载于 Commentarii academiae scientiarum Petropolitanae 第 8 卷 141–146 页。篇名是 Theorematum quorundam ad numeros primos spectantium demonstratio，Eneström 编号 E54。篇名的意思是若干条关于素数的定理的证明。这是对拉丁文标题的转述，不是从费马的信里再引一句。宣读不是刊出。把 1736 年写成发表年，会把卷期和页码提前。本页下面写的重排，是这条定理为什么成立的一条证明，不是那一印本的逐页抄录。印本里其余命题叫什么，本页不另编。

莱布尼茨在 1683 年之前的未发表手稿里有过同类论证。手稿没有刊出，所以它不是公开证明。欧拉仍然是第一个把证明印出来的人。本页不猜测那份手稿藏在哪一座档案馆，也不给它编库藏号。未发表只说明当时的读者看不到，不说明论证不存在。谁先想到，和谁先把证明印出来，是两本账。不要为了把优先权说圆，就给手稿补一个地址。

它也不是光学里的费马原理。那一条谈光从一点到另一点时，传播时间取驻定值的路径。对象是路径和时间。本页的对象是整数、素数和余数。名字都叫费马，问的句子并不相同。把同余式拿去解释折射，或者把光程拿来判断一个数是不是素数，都是把两件事焊成一件。光学那条写在费马那一页。本页不重写光路，只把它从这条同余旁边拿开。

同余式有两种写法，不能收成同一句假设。第一种：p 是素数，而且 p 不整除 a，则 a 的 p−1 次幂除以 p 余 1。这里的 a 必须躲开 p 的倍数。第二种：对所有整数 a，都有 a 的 p 次幂与 a 本身被 p 除余数相同。第二种不预先要求 p 不整除 a。p 整除 a 时，第一种的结论会失败，第二种仍然成立。取 p 等于 5，a 等于 10。10 被 5 整除。10 的四次幂是 10000，被 5 除余 0，不是 1。10 的五次幂仍然被 5 整除，10 自己也被 5 整除，所以两边同余。再取不被整除的底数 3。3 的四次幂是 81，81 减 1 是 80，80 被 5 整除，所以余数是 1。两种写法都真，前提并不相同。把「对所有整数」说成第一种，会在底数是 p 的倍数时立刻碰到反例。

陈述，以及证明为什么成立#

把第一种写完整。设 p 是素数，a 是整数，p 不整除 a。a 可以是负的。只要 p 不整除它，就和正的底数走同一句。则

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

把第二种写完整。设 p 是素数，a 是任意整数，不再另加「不被整除」。则

$$a^p\equiv a\pmod{p}.$$

第二种覆盖 p 整除 a 的情形。那种情形里，a 的 p−1 次幂通常不余 1，所以不能从第二种的字面把指数减一，再宣称余数是 1。前面的 10 和 5 就是这一刀：五次幂与 10 同余于模 5，四次幂却不余 1。p 等于 2 时也不另开例外。第一种说的是：奇数的一次幂余 1，也就是奇数本身被 2 除余 1。第二种说的是：任何整数的平方与自己被 2 除余数相同。偶数两边都余 0，奇数两边都余 1。

第一种可以这样看。1 到 p−1 这 p−1 个数，各自乘上 a，再去掉 p 的倍数，只是把同一批数重新排队。先看它们都不会余 0。若 a 乘 i 被 p 整除，p 不整除 a，而 p 是素数，p 就得整除 i。可是 i 只在 1 与 p−1 之间，p 整除不了 i。再看没有两个撞在同一个余数上。若 a 乘 i 与 a 乘 j 被 p 除余数相同，p 就整除 a 乘 (i−j)。同样因为 p 不整除 a，p 整除 i−j。i 与 j 的差的绝对值小于 p，所以 i 等于 j。于是这 p−1 个余数两两不同，又都落在 1 到 p−1 里，只能是这批数的一种重排。重排是证明，不是一段可以拿去运行的程序。

p 等于 5、a 等于 3 可以当面看。1、2、3、4 各自乘以 3，得到 3、6、9、12。去掉 5 的倍数以后是 3、1、4、2。这四个数仍是 1、2、3、4，只是次序换了。重排不改变连乘的积。所以两边连乘，模 p 的余数一样。左边每个因子都带一个 a，一共 p−1 个，再乘上 1 到 p−1 的积。右边就是那个积本身。

$$a^{p-1}\cdot (p-1)! \equiv (p-1)! \pmod{p}.$$

约去这个公因子，不是在整数里做除法，把商写出来再丢掉余数。因为 p 是素数，1 到 p−1 的每个数都不被 p 整除，它们的积也不被 p 整除。因此存在一个整数，乘上这个积以后被 p 除余 1。两边同乘那个整数，左边剩下 a 的 p−1 次幂，右边剩下 1。这就是第一种。Ireland 与 Rosen 的 A Classical Introduction to Modern Number Theory 第二版由 Springer 在 1990 年出版，按古典数论的路子容纳这条定理。本页不编页码，也不把书里的章节顺序说成上面这一段的目录。

整除这一步要和算术基本定理分开。那一页写明，欧几里得第七卷命题 30 只是引理：素数量尽一个乘积，就量尽其中一个因子。本页约去公因子时用的是这件事。p 量尽 a 乘 (i−j)，却不量尽 a，就量尽 i−j。引理不是「大于 1 的整数有唯一的素数幂分解」那一整句。借引理，不等于把两条定理说成同一条。唯一分解回答因子怎么写。重排回答的是：乘上一个不被整除的 a，为什么不把 1 到 p−1 送出这批数之外。

第二种从第一种分情形推出来，而不是把两句假设并成一句。若 p 不整除 a，第一种给出 p−1 次幂余 1，两边再乘 a，得到 p 次幂与 a 同余。若 p 整除 a，则 p 整除 a 的任意正次幂，也整除 a 本身，所以两边被 p 除都余 0。两种情形合在一起，才是「对所有整数 a」。少了后一种，被 p 整除的底数没有着落。少了前一种，不被整除的底数还没有从第一种走过来。0 也落在后一种里：p 整除 0，0 的正次幂仍是 0，两边都余 0。

素数这个条件在重排里是出力的，不是附在句末的装饰。模若换成合数，1 到 n−1 里会混进与 n 不互素的数，连乘里也会出现 n 的因子，公因子不再能约掉。指数若仍照抄 n−1，结论也可以失败。取 n 等于 9，a 等于 2。2 的八次幂是 256。256 除以 9，9 乘 28 得 252，余 4，不是 1。9 不是素数，重排那句「模是素数」从一开始就不成立。这只说明证明用到了素数。它不是在下达一套检查步骤，也不告诉人下一步去试哪一个底数。

第二种还有一个直接的推论，仍然是同余，不是整数里的等式。对素数 p 和任意整数 a、b，(a+b) 的 p 次幂与 a+b 同余，a 的 p 次幂与 a 同余，b 的 p 次幂与 b 同余，所以 (a+b) 的 p 次幂与 a 的 p 次幂加上 b 的 p 次幂同余，模是 p。取 a 等于 1，b 等于 1，p 等于 2。左边 (1+1) 的平方是 4，右边 1 的平方加 1 的平方是 2。4 与 2 被 2 除都余 0，同余成立。作为整数，4 并不等于 2。定理保证的是模 p 下的余数，不是把二项式展开里的中间项在整数里抹掉。

它没有保证的东西#

在 p 不整除 a 的前提下，若 a 的 p−1 次幂不余 1，则这个被叫做 p 的数不是素数。这是第一种的逆否。前提不能省。若 p 整除 a，左边常常不余 1，而 p 仍可以是素数。取 p 等于 7，a 等于 7。7 的正次幂都被 7 整除，六次幂被 7 除余 0，不是 1，7 却是素数。口号若写成「只要这个幂不余 1，旁边那个数就不是素数」，7 会把口号打穿。失败的是省略了前提的口号，不是定理。前提还在时，逆否只做一件否定的事：同余失败，就把素数这个身份否定掉。

反过来不能推出一个数是素数。看见某个与 n 互素的 a 满足 a 的 n−1 次幂余 1，即使用了许多个这样的 a，也推不出 n 是素数。卡迈克尔数说明这件事可以整批失败。最小的一个是 561，它等于 3×11×17。对每一个与 561 互素的底数 a，a 的 560 次幂被 561 除都余 1。561 不是素数。本页不再列举别的卡迈克尔数。3、11、17 写在这里，是为了点明 561 是合数，不是为了把三个素因子上的同余再拼成一次推导，也不是一套把合数拆开的步骤。

因此这条定理不能单独证明一个数是素数。它能做的否定很窄：前提满足而同余失败时，那个数不是素数。同余成立时，它保持沉默。沉默不是一种弱一点的肯定。561 上那种整批成立的同余，就是沉默的样子：式子都对，数仍是合数。本页不把这种沉默写成测试步骤，不写如何挑选底数，也不写同余失败以后怎样去分解。那些手续不从这条定理的陈述里长出来。这里停在逻辑。否定成立。肯定不成立。

它也不是欧拉定理那一页。欧拉定理说：只要 a 与 n 互素，a 的 φ(n) 次幂被 n 除就余 1。n 不必是素数。φ(n) 计数的是从 1 到 n 之中与 n 互素的正整数个数。n 为素数 p 时，1 到 p−1 全都与 p 互素，所以 φ(p) 等于 p−1。指数变成 p−1，模换成 p，就是费马小定理的第一种。特例是把模收成素数以后的样子。本页不把欧拉定理的证明重写一遍，也不展开 φ 在合数上的乘积公式。那是那一页的正文。这里只核对代入：素数模、指数少一、底数不被整除，三件事一起出现时，两句话对准同一条同余。

欧拉定理自己的假设是互素，不是「模必须为素」。互素失败时，那条结论不必成立。取 a 等于 2，n 等于 4。最大公因数是 2，不是 1。φ(4) 等于 2，而 2 的平方是 4，被 4 除余 0，不是 1。这组数不反驳欧拉定理，因为它不在假设里。它只提醒：推广式比费马小定理的第一种多要求一条互素，也多允许一个合数模。费马小定理不负责替这条更宽的假设作证。反过来，合数模上互素底数的那条一般式，也不能倒过来说成「本页已经把合数模写完了」。

第二种也不替所有的模作保。把素数 p 换成任意正整数 n 以后，a 的 n 次幂与 a 同余，不必对所有 a 成立。仍取 n 等于 4，a 等于 2。2 的四次幂是 16。16 减 2 是 14，14 不被 4 整除，所以 16 与 2 被 4 除的余数不同。费马小定理的第二条把模限制在素数上。合数模上的失败，不是这条定理的反例，因为假设里的那个数已经不是素数。不要把「对所有 a」从素数模上摘下来，贴到任意模上，再声称还是同一句。

它不分解整数，也不生成密钥。算术基本定理回答素因子怎么写。一组剩余能不能粘成模乘积下的一个类，是另一条定理的问题。本页只回答素数模下的幂何时回到一，以及去掉「不被整除」之后，幂与底数何时同余。正确性若要用到合数模上的幂，用的是欧拉定理这一推广，不是把本页的第一种原样套到合数上。指数怎么选、两个方向的运算怎么配对，本页都不写。

跨域连接#

• 欧拉定理：费马小定理是欧拉定理在模为素数时的特例。欧拉定理要求底数与模互素，模数可以是合数。模是素数 p 时，与 p 互素的剩余恰好是 1 到 p−1，个数是 p−1，指数就从 φ(n) 收成 p−1。本页只把这个代入写清楚，不替那一页证明互素模上的一般式，也不把 φ 的乘积公式展开。读一般式，去那一页。读素数模上哪一种写法要躲开倍数，留在本页。两种写法的分界，不因它是特例就被抹掉。
• 数论：数论页在历史叙述里把费马大定理和费马小定理放在同一句里点名。那一句是目录，不是定义。大定理的未知数是三个正整数的幂和。小定理的未知数是素数模下的余数。同页还把同余和素因子分解并列。本页的重排用到素数量尽乘积则量尽一个因子，那是整除引理，不是分解的唯一性。唯一分解不推出幂会回到一。幂回到一也不给出标准分解。两件事可以先后读，不能互相代替。
• 费马大定理：那一页的陈述是指数大于二时，幂和等式没有正整数解。证明路线经过椭圆曲线和模形式，不是模 p 下把 1 到 p−1 重新排队。页边那句空白太窄，属于那一条，不属于 1640 年 10 月 18 日给弗雷尼克勒·德·贝西的信。本页的信只留下「若不是怕太长，我本会把证明也写上」，而且没有附证明。两句都表示证明当时不在纸上，句子不同，对象也不同。不要用「小」字把幂和等式收成少一次的同余。
• 中国剩余定理：剩余类能不能粘成模乘积下的一个类，是那一页的问题。本页不需要联立好几条模，一条素数模就够。两边会在合数模上相遇：素数模上的同余若要抬到素数乘积的模上，粘合用的是那一页，而不是把费马小定理的指数直接换成合数。本页不写这次粘合的步骤。561 写成 3×11×17，只用来标明它是合数。不在这里把三个模上的余数再拼一次，也不把「有解且类唯一」说成幂会回到一。
• RSA 公钥密码：那一页的正确性用到本定理的推广，也就是欧拉定理，而不是用素数模上的原式去完成运算。模是合数时，第一种里的指数 p−1 不再是那一页需要的指数。本页因此只说明这条依赖：合数模上、底数与模互素时，回到一的是欧拉定理，不是把 p 换成合数以后的费马小定理。不写密钥如何产生，不写配对的指数，也不把分解的难度说成本定理的结论。
• 埃尔加迈勒 1985：那一页写明，方案用到的工具里包括费马小定理，指数可以按 p−1 取模。这是因为不被 p 整除的底数，其 p−1 次幂余 1，指数加上 p−1 的倍数，不改变乘方的余数。本页提供的就是这个周期。周期从第一种来，不从「p 整除 a」那种情形来，因为那种情形下幂不回到一。那四页上的加密、签名和参数如何摆，本页不重写。周期存在，不等于任何一张具体方案已经写在这里。

参考文献#

• Euler, Leonhard. “Theorematum quorundam ad numeros primos spectantium demonstratio.” Commentarii academiae scientiarum Petropolitanae 8 (1741): 141–146. 宣读于 1736-08-02。E54。
• Ireland, Kenneth, and Michael Rosen. A Classical Introduction to Modern Number Theory. 2nd ed. Springer, 1990.