欧拉定理

破除误解#

第二条要拆开的，是把素数情形的证明当成这条推广。费马小定理的素数模说法，费马在 1640 年陈述过，那一次没有附证明。欧拉对素数情形的公开证明是 E54，篇名 Theorematum quorundam ad numeros primos spectantium demonstratio。1736 年 8 月 2 日宣读，1741 年刊在 Commentarii academiae scientiarum Petropolitanae 第 8 卷 141–146 页。那一篇证的是 $a^{p-1}\equiv 1\pmod{p}$。它不把模从素数放宽到一般正整数，也不把「小于 $N$ 且与 $N$ 互素的正整数个数」当作指数。把 E54 叫成欧拉定理，会把 1741 年已经印出的素数证明，和 1763 年才刊出的推广，焊成同一篇。

第三条要拆开的，是「合数模上对一切底数都成立」。假设写在前面：$\gcd(a,n)=1$。拿掉它，句子是假的。模 8 时 $\varphi(8)=4$，底数 2 与 8 不互素，$2^4=16\equiv 0\pmod{8}$，不是 1。模 15 时 $\varphi(15)=8$，底数 3 与 15 不互素，$3^8=6561$。15 乘 437 得 6555，余数是 6，不是 1。反过来也要互素。若 $a^{\varphi(n)}\equiv 1\pmod{n}$，则这个幂与 1 同余，表示 $a$ 在模 $n$ 下可逆：$\varphi(n)$ 至少是 1，所以存在非负整数次幂 $a^{\varphi(n)-1}$，乘上 $a$ 以后与 1 同余。于是 $a$ 与 $n$ 的任何公因数都整除 1，只能是 $\gcd(a,n)=1$。同余一旦成立，互素就被逼出来。不互素的底数不可能满足这条同余。定理不是对一切底数成立，而是恰好在互素时成立。从互素推出同余，是定理本身。从同余推出互素，只靠可逆，不必当成 1763 年第 11 条的原文。

第四条要拆开的，是把计数当成密钥步骤。两个不同的素数 $p$、$q$ 满足 $\varphi(pq)=(p-1)(q-1)$。这是在数 1 到 $pq$ 之中，有多少个数不被 $p$ 整除、也不被 $q$ 整除。RSA 公钥密码那一页用本页的同余，保证与模互素的明文在加密后再解密回到原类。假设本身包含互素。个数仍然只是个数。本页不写密钥怎么选，不写填充，也不写把解密幂拆到两个素数模上再合并。那些做法不能从「互素的剩余有多少个」这句话里直接抄出来。

定理在说什么#

正整数 $n$ 与整数 $a$ 若满足 $\gcd(a,n)=1$，则 $a^{\varphi(n)}\equiv 1\pmod{n}$。$\varphi(n)$ 是 1 到 $n$ 中与 $n$ 互素的正整数个数。负的底数先换成模 $n$ 下的剩余，互素与否不变，定理看的是这个类。$n>1$ 时，$n$ 自己与 $n$ 的最大公因数是 $n$，不是 1，所以 $n$ 不被数进去。「从 1 数到 $n$」和「只数小于 $n$ 的」在 $n>1$ 时是同一批数。1763 年的原文用的是后一种说法，见下文。符号 $\varphi$ 是后来的名字。定义先于这个字母。

单独看 $n=1$ 时，1 到 1 之中与 1 互素的只有 1 自己，因为 $\gcd(1,1)=1$，所以 $\varphi(1)=1$。这不是把全体整数都数进函数值。模 1 时，任何两个整数之差都被 1 整除，同余式一律成立，$a^{1}\equiv 1\pmod{1}$ 看不出「余数是 1」这种除法现象。本页后面的例子都取大于 1 的模。原文说的是小于 $N$ 的个数。$N>1$ 时它与「1 到 $N$」相同，因为 $N$ 自己不互素。$N=1$ 时小于 1 的正整数不存在。本页不把这个空集说成第 11 条已经写过的情形。

数论那一页已经写下 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$，乘积跑过 $n$ 的不同素因子。本页沿用这个式子，不把它展开成一套筛法。两个例子够核对。$n=8=2^3$，只有素因子 2，$\varphi(8)=8(1-1/2)=4$，对应 1、3、5、7。$n=15=3\times 5$，$\varphi(15)=15(1-1/3)(1-1/5)=8$，对应 1、2、4、7、8、11、13、14。式子要用到素因子的集合已经定下来。集合为什么不计次序只有一种，是 算术基本定理 的事。本页用这个集合去数剩余，不重新证明分解唯一。

$n=p$ 为素数时，1 到 $p-1$ 都与 $p$ 互素，$p$ 自己不互素，所以 $\varphi(p)=p-1$。定理变成：若 $p$ 不整除 $a$，则 $a^{p-1}\equiv 1\pmod{p}$。这就是费马小定理。素数限制拿掉以后，指数从 $p-1$ 换成 $\varphi(n)$，互素的条件还在。因此说本页是费马小定理去掉素数限制后的陈述，不是说素数情形直到 1763 年才有公开证明。素数情形的公开证明早在 E54。用 $p=7$、$a=3$ 可以看见退回以后的句子：$3^6=729$，7 乘 104 得 728，余数是 1。

还有一种容易混进去的替换。素数时指数是 $p-1$，于是有人把合数 $n$ 的指数写成 $n-1$，以为去掉素数限制只是把字母 $p$ 换成 $n$。模 15、底数 2 与 15 互素，$\varphi(15)=8$，$2^8=256$，256 减 1 得 255，$255=17\times 15$，所以 $2^8\equiv 1\pmod{15}$，定理成立。若误用指数 14：$2^4=16\equiv 1\pmod{15}$，于是 $2^{14}\equiv 2^{2}\equiv 4\pmod{15}$，不是 1。互素仍然满足假设，错在指数。去掉的是「模必须为素数」，不是把 $p-1$ 里的 $p$ 原样换成合数。

两个不同素数 $p$ 与 $q$ 时，乘积式给出 $\varphi(pq)=pq(1-1/p)(1-1/q)=(p-1)(q-1)$。也可以直接数。1 到 $pq$ 一共 $pq$ 个数，被 $p$ 整除的有 $q$ 个，被 $q$ 整除的有 $p$ 个，同时被 $p$ 和 $q$ 整除的有 1 个。容斥以后剩下 $(p-1)(q-1)$ 个与 $pq$ 互素。$p=3$、$q=5$ 时是 $2\times 4=8$，与 $\varphi(15)=8$ 一致。这是计数，不是密钥生成。它不指定一对指数，也不保证一个随便写下的底数会与 $pq$ 互素。

指数够用，不等于它总是最小的正指数。模 8 上与 8 互素的底数都是奇数，奇数的平方被 8 除余 1。$3^2=9\equiv 1\pmod{8}$，而 $\varphi(8)=4$，$3^4=81\equiv 1\pmod{8}$ 也成立。定理保证 4 次幂回到 1，不保证没有更小的正指数。把 $\varphi(n)$ 说成「底数的阶一定等于它」，比定理多说了一句，而且这一句是假的。E271 刊出的是「这个次数已经够」，不是「这个次数不能再小」。

最小的正指数一旦存在，就整除 $\varphi(n)$。设 $d$ 是使 $a^{d}\equiv 1\pmod{n}$ 的最小正整数，并已经知道 $a^{\varphi(n)}\equiv 1$。用带余除法写成 $\varphi(n)=qd+r$，其中 $0\le r<d$。则 $a^{\varphi(n)}=(a^{d})^{q}\cdot a^{r}\equiv a^{r}\equiv 1\pmod{n}$。若 $r$ 大于 0，$r$ 就是更小的正指数，与 $d$ 的最小性矛盾，因此 $r=0$。模 8 上底数 3 的最小正指数是 2，$\varphi(8)=4$，2 整除 4。定理给出的次数可以比最小的那一次大，但大出来的仍是最小次数的整数倍。平方已经回到 1 时，4 次幂回到 1 就不再显得意外。这里没有把「阶一定等于 $\varphi(n)$」加回定理。

把互素的类乘一遍#

证明不必写成一段程序。令 $S$ 是模 $n$ 下与 $n$ 互素的剩余类，一共 $\varphi(n)$ 个。取与 $n$ 互素的 $a$，把 $S$ 里每个类乘上 $a$。乘完仍与 $n$ 互素。若某个素数 $p$ 既整除 $n$ 又整除 $ax$，则 $p$ 不能整除 $a$，只好整除 $x$，这与 $x$ 属于 $S$ 矛盾。若 $ax\equiv ay\pmod{n}$，则 $n$ 整除 $a(x-y)$。$a$ 与 $n$ 互素，所以 $n$ 整除 $x-y$，两类相同。有限集合上的这个对应是一一的，因此乘以 $a$ 只是把 $S$ 重排。

用 $n=10$ 看一次重排。$\varphi(10)=4$，代表可取 1、3、7、9。乘以 3：$3\times 1=3$，$3\times 3=9$，$3\times 7=21\equiv 1$，$3\times 9=27\equiv 7$。得到的仍是这四类，只是次序变了。四类各自乘上 3 再连乘，等于 $3^4$ 乘上原来的连乘。代表的普通乘积 $1\times 3\times 7\times 9=189$。于是 $3^4\times 189$ 与 189 被 10 除的余数相同。189 被 10 除余 9，9 与 10 互素，可以约去，剩下 $3^4\equiv 1\pmod{10}$。直接算，81 被 10 除余 1。

模 15 上再看一次，底数取与 15 互素的 2。$\varphi(15)=8$，互素的代表是 1、2、4、7、8、11、13、14。乘以 2 得到 2、4、8、14、16、22、26、28。按 15 收余数，16 余 1，22 余 7，26 余 11，28 余 13。八个数仍是原来的八类。若改乘 3，3 与 15 不互素，3 乘 1 得 3，3 已经不在这八类里。重排从第一步就失败，所以不能指望 $3^8$ 回到 1。前面算过，它的余数是 6。

一般情形是同一句话。把 $S$ 里全部类连乘，记这个乘积为 $P$。重排不改变连乘，所以 $P\equiv a^{\varphi(n)}P\pmod{n}$。$P$ 由若干个与 $n$ 互素的类乘出来，自己也与 $n$ 互素，在模 $n$ 下可逆。两边乘上 $P$ 的逆，得到 $a^{\varphi(n)}\equiv 1\pmod{n}$。也可以说 $n$ 整除 $P\bigl(a^{\varphi(n)}-1\bigr)$，再由 $\gcd(P,n)=1$ 推出 $n$ 整除 $a^{\varphi(n)}-1$。约去的是与模互素的公因子，不是把同余式两边随便消去一个与模不互素的数。2 乘上 $\{1,3,7,9\}$ 得到 $\{2,6,4,8\}$，已经离开 $S$。重排的前提不在，就不能对底数 2 引用这一步。$2^4=16\equiv 6\pmod{10}$，确实不是 1。

同一件事也可以先说成群。与 $n$ 互素的剩余类在乘法下构成群，群的阶是 $\varphi(n)$。有限群里每个元素自乘群的阶那么多次，得到单位元。重排再约去 $P$，就是不先使用群这个词也能把这个次数用完的写法。数论页已经把群的那一句写在跨域连接里。本页给出的是连乘与约去。两种写法指向同一条同余，都依赖底数在这个群里，也就是依赖互素。

宣读年与刊出年要分开#

费马在 1640 年说出的是素数模。若 $p$ 是素数且 $p$ 不整除 $a$，则 $a^{p-1}-1$ 被 $p$ 整除。他没有在那一次陈述旁边给出证明。本页也不把后来的证明说成 1640 年已经印出。素数情形因此先有陈述，后有公开证明。在欧拉名下，先刊出的那一份素数证明是 E54。E271 更晚，本页用它是为了推广，不是为了把 E54 改称欧拉定理。

E54 的题目表明它看着素数。1736 年 8 月 2 日宣读。刊出在 1741 年的 Commentarii academiae scientiarum Petropolitanae 第 8 卷，页码 141–146。宣读年与刊出年差了五年。把卷期上的 1741 改写成 1736，或把宣读日写成出版日，都会让人以为证明在宣读的当年就已经落到这一卷的页码上。E54 证明的是素数模上的 $a^{p-1}\equiv 1$。它不是本页的推广。推广要等指数换成与模互素的剩余个数。

推广的公开刊出是 E271，篇名 Theoremata arithmetica nova methodo demonstrata。这个拉丁文篇名可以读成「用新方法证明的算术定理」。它不是 算术基本定理 那一页，也不是后来把唯一分解写清楚的那本书。刊出处是 Novi Commentarii academiae scientiarum Petropolitanae 第 8 卷，1763 年，74–104 页。Theorema 11 在第 102 页。文中不把这个指数叫作 $\varphi$。它称之为 numerus partium ad N primarum，也就是小于 $N$ 且与 $N$ 互素的正整数个数。第 11 条要说的是：底数与 $N$ 互素时，这个次数的幂减 1 被 $N$ 整除。用今天的同余号，就是本页的陈述。

E271 不是把素数情形删掉以后另起的一篇。素数模仍在文中出现。本页引用它，是因为第 11 条把指数从 $p-1$ 换成那个互素剩余的个数，模不再限于素数。不要把整篇收成「又一份只有素数的证明」，也不要用 E54 代替第 102 页。时间有三层。1758 年 6 月 8 日，这篇在柏林科学院宣读。1759 年 10 月 15 日，在圣彼得堡科学院宣读。1763 年，第 8 卷把它印出来。本页把年份记为 1763，指的是刊出年，不是两次宣读中的任何一次。只看见 1763，会以为推广在这一年才被想到。只看见 1758，会以为那一年已经有了可以核对的印刷页。三层都要留下。

它保证什么，不保证什么#

它保证的只有这一件。底数与正整数模互素时，把底数自乘 $\varphi(n)$ 次，余数是 1。素数模上，$\varphi(p)=p-1$，句子退回费马小定理。两个不同素数的积上，指数是 $(p-1)(q-1)$，那是互素剩余的个数。重排说明这个次数为什么够用：乘以底数不离开那些类，连乘以后与模互素的公因子可以约掉。同余成立时，底数必定可逆，因而必定与模互素。所以不互素的底数既不在假设里，也不可能偷偷满足结论。

它不保证 $\varphi(n)$ 是使幂回到 1 的最小正指数。模 8 上的 3，平方已经回到 1。它不证明 $e^{i\pi}+1=0$，不给出 ζ 的欧拉乘积，不算示性数，也不讨论三角形的欧拉线。它不把大于 1 的整数拆成素数幂。它只用已经拆好的素因子去数 $\varphi(n)$。分解是否唯一，要回到算术基本定理。它也不给联立同余配解。中国剩余定理问的是几个剩余能不能粘成模乘积下的一个类。本页问的是一个与模互素的底数，乘够 $\varphi(n)$ 次以后会不会回到 1。类可以粘合，并不代替这条幂。

RSA 公钥密码那一页用这条同余，保证与模互素的明文加密之后再解密，回到原来的类。那一页自己也写明，正确性在适当条件下成立。与本页重合的条件就是互素。明文若与模不互素，本定理的句子没有开口，不能把「适当条件」换成「一切明文」。密钥怎样生成、填充怎样避开确定性加密、用中国剩余定理把解密幂拆开再合并，都是那一页的实现问题。$\varphi(pq)=(p-1)(q-1)$ 在两页里同时出现时，本页只认它是计数。

跨域连接#

• 费马小定理：费马在 1640 年陈述的是素数模，那一次没有附证明。素数 $p$ 不整除 $a$ 时，$a^{p-1}\equiv 1\pmod{p}$。欧拉对这一情形的公开证明是 E54，1736 年 8 月 2 日宣读，1741 年刊出，页码 141–146。那不是本页。本页把模从素数放宽：指数换成 $\varphi(n)$，假设仍是互素。$n=p$ 时 $\varphi(p)=p-1$，推广退回原句。退回成功，并不表示 E54 已经写过 numerus partium ad N primarum。公开刊出的推广在 E271 的第 11 条。
• 欧拉恒等式：恒等式页的等式是 $e^{i\pi}+1=0$，来自复指数在单位圆上转到半周。五个常数各自先有定义，等式只约束它们同时出现时必须满足的关系。本页没有复指数，没有圆周率，也没有虚数单位。两页都叫欧拉，年份一个记 1748，一个记刊出年 1763。把同余 $a^{\varphi(n)}\equiv 1\pmod{n}$ 读成那条恒等式，是把除法的余数读成了平面上的旋转。示性数、欧拉线和 ζ 的乘积也不在这条同余里。
• 数论：数论页把欧拉函数写成 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$，并把欧拉定理写成互素时 $a^{\varphi(n)}\equiv 1\pmod{n}$，同时注明费马小定理是素数特例。本页补上的是假设不能省略，以及同余成立时底数必定可逆、因而必定互素。乘积式用来核对 $\varphi(8)=4$、$\varphi(15)=8$。它默认素因子集合已经由分解唯一给定。数论页还把互素剩余类的乘法群写进跨域连接。群的阶给出一个够用的指数，与本页的重排约分是同一条同余的两种说法。
• 中国剩余定理：那一页的未知数是同时满足几条剩余的整数，唯一性只活在模乘积的一个类里。模两两互素时，类能够粘合。本页的未知数不是那个公共解，而是一个与单个模互素的底数，看它的幂是否回到 1。两个不同素数给出 $\varphi(pq)=(p-1)(q-1)$，计数可以借模 $p$ 与模 $q$ 的剩余成对来理解，因为这两条模互素。理解计数，不是把解密写成先分开再合并。那一页已经写明，实现上的倍数、填充和分解难度都不从中国剩余定理推出来。本页同样不写这些做法。
• RSA 公钥密码：那一页写明，欧拉定理用来保证加密与解密互为逆运算，并且正确性在适当条件下成立。与本页重合的条件，是明文与模互素。同余 $m^{\varphi(n)}\equiv 1\pmod{n}$ 只有在这个假设下才由定理给出。不互素时同余一定不成立，因为成立就会推出可逆。那一页讨论的安全性来自分解模数的代价，不来自本定理突然对一切底数成立。本页不重复密钥的选取次序，不讨论填充，也不把中国剩余定理加速解密写成做法。
• 算术基本定理：那一页证明大于 1 的正整数写成素数幂之积，不计次序只有一种。本页的乘积式要先知道有哪些不同的素因子。集合定了，$\varphi(n)$ 才不随书写次序改变。$(p-1)(q-1)$ 也用到 $p$ 与 $q$ 是两个不同的素数，而不是一对还可以再拆的合数。分解唯一不推出互素底数的幂回到 1。幂回到 1 也不推出 12 只能写成 $2^2\times 3$。E271 的篇名虽可读成算术定理，第 102 页印的是那条同余，不是唯一分解。

参考文献#

• Euler, Leonhard. “Theoremata arithmetica nova methodo demonstrata.” Novi Commentarii academiae scientiarum Petropolitanae 8 (1763): 74–104. Theorema 11 在第 102 页。E271。1758-06-08 柏林宣读，1759-10-15 圣彼得堡宣读。
• Euler, Leonhard. “Theorematum quorundam ad numeros primos spectantium demonstratio.” Commentarii academiae scientiarum Petropolitanae 8 (1741): 141–146. E54。这是素数情形，不是本页的推广。
• Ireland, Kenneth, and Michael Rosen. A Classical Introduction to Modern Number Theory. 2nd ed. Springer, 1990. 同余形式的现代叙述可与这一本对照。本页不标页码。