一周一定理No.3 欧拉定理

在前两期

我们分别介绍了初等数论中的两个基本结果，中国剩余定理与求一术（及其推广方程术）。与其说它们是定理，还不如说它们是算法。算法与普通的定理有个差别，算法应用起来是要操作整个过程，而定理可能只需要你会用最终结论。所以你要掌握算法，就免不了要走一遍程序。也正是这个原因，不会跳跃的计算机很容易理解算法。记得编程大师高德纳(D. E. Knuth)有句名言：

所谓科学，就是能够教会计算机的东西。

他还说（大意）：只有当一个教师能够教会计算机了，才能教明白学生。

高德纳

今天我们介绍初等数论中一个地地道道的定理，历史上著名的欧拉定理。大数学家欧拉(Euler)有许多定理，我们这里所指的是下一个：

欧拉定理：设 n是正整数，a 是一个整数，且a 与 n互素，则

aφ(n)≡1(modn){\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}

其中（φ是希腊字母，发音即 wifi 的fi )是欧拉函数，表示1,2,…,n中与n互素的数的个数。

这里看起来像汉字 三 的记号是同余记号，由高斯(Gauss)在1801年首次引进。同余式（可读作：a 与 b 模m同余，或 a 模m 同余于 b)

表示a-b 是 m 的倍数，或者可以等价的说, a除以m的余数（用带余数的除法）与b 除以m的余数相同。

其实在生活中，我们经常用到同余的观念。例如，你如果问一个小朋友：假设现在是中午12点，那么再过12个钟头，是几点？他很可能回答说，是0点（如果他有0的概念的话）。这是因为一天有24个小时，在模24的意义下，24与0是一样的。

一个更简单而往往被忽略的，是下述电影海报上的等式：在模2意义下，2=0. 它的一个生活常识解释是：开关的运算法则是，两次操作，回复原位。模2运算同时也是数理逻辑的基础（也许常常称为布尔运算）。

又如今年（2018年）国庆节是星期一，由此可知明年的国庆节是星期二，因为

Question1: 2020年的国庆节星期几？（注意，这里有个坑）

再如，如果我告诉你某个人的出生年份，那么你可以推出他的属相。例如，

高斯出生于1777年，那么不难根据

推出高斯属鸡（2017年是鸡年）.

Question2: 出生于1642年的牛顿(Newton)的生肖是什么？

现在回到欧拉定理本身，我们需要理解的，是欧拉函数，这个函数表示1，2，…，n 中与 n 互素的数目的个数。例如，若取 n=12, 则不难发现，在1-12中，与12互素的数只有1，5，7，11，一共4个，所以。

如果知道了n的全部素因子（这里有一个相关的定理，算术基本定理），那么很容易求出。我们有下述结果：

这个定理的一个特例是n=p是素数的情况，此时 

这一点根据定义也很容易看出。在这个特殊情况下，欧拉定理退化为费马小定理：

注：历史上先有费马小定理，而后有欧拉定理，因此欧拉定理也被称为费马-欧拉定理。

Question3: 用数学归纳法证明第二种表述的费马小定理。

欧拉定理（或费马-欧拉定理）的证明，可以在维基百科查到，我们这里不再展开，见网页https://en.wikipedia.org/wiki/Euler%27s_theorem。

要指出的是，高观点下的欧拉定理，是一个群论定理（拉格朗日定理）的特殊情形。这个定理说，一个有限阶群，每个元素的阶数都整除群的阶数。这里的群，是整数在模n下的（乘法）可逆元（也就是与n 互素的同余类）构成的群，其阶数恰好是。要说明这一点，相当于要证明下述结果：

Question4: 请利用第2期介绍的求一术或方程术证明上述定理。

另一方面，我们也可以对模n下的（乘法）可逆元给出另一个解释。这就涉及到另一个群，即整数在模n下的加法群。这个群是一个循环群（注：循环群是最简单的一类群），其阶数恰好等于n. 这个循环群的生成元，恰好就是那些与n互素的同余类。以n=12为例，容易看出， 1,5,7,11恰好是模12的加群的生成元。这一点（主要是5)很早就被中国古代的音律学家发现了，在《吕氏春秋》之《音律》篇中我们可以读到：

黄钟生林钟，林钟生太簇，太簇生南吕，南吕生姑洗，姑洗生应钟，应钟生蕤宾，蕤宾生大吕，大吕生夷则，夷则生夹钟，夹钟生无射，无射生仲吕。

指的就是，在模12的加群下, 从7 出发，反复加7, 将遍历各个同余类，依次得到

7（黄钟）→14=2（林钟）→9（太簇）→16=4（南吕）→11（姑洗）→18=6（硬钟）→13=1（蕤宾）→8（大吕）→15=3（夷则）→10（夹钟）→17=5（无射）→12（仲吕）

如下图所示（引自程贞一《黄钟大吕》，王翼勋译，上海科技教育出版社，104页）：

Question5: 写出在模12的加群下, 从5出发，反复加5, 依次得到的各个同余类。

注：应该指出，在音律中有对称，有群（你可以大致认为，群就是对称生成的）。这里的模12加群与十二平均律有关。在几何上对应着一个正十二边行的旋转群。正如正十二边形的对称，除了旋转，还有关于对称轴的反射；音律群里除了对应着旋转的变调，还有对应着反射的转位。因此，主导音乐的对称群是正十二边形的对称群，也就是24阶的二面体群。对此有兴趣的读者，我们推荐一篇漂亮的文章：

Alissa S. Crans、Thomas M Fiore、Ramon Satyendra

的二面体群作

Alissa S. Crans、Thomas M. Fiore、Ramon Satyendra，音乐中的二面体群作用，中译文收入“数学与人文”丛书第17辑《数学的艺术》，丘成桐；刘克峰；杨乐；季理真 李方主编，高等教育出版社，2015年。

最后，回到欧拉定理本身，为加深你对这个定理的印象，我们再给出一个练习：

Question6: 已知 2017是素数，求 

小结：欧拉定理体现了这样的观念，在整数中存在着结构（在这里，就是群）。有了这样的观点，许多东西理解起来会比较简单而深刻，因为一些表面上不同的东西可以得到统一。陈省身先生曾经说，真正重要的观念是很少的，毫无疑问，群是其中一个。

P. S. 写到这里，我回想起从前念书时，我读到的第一个很喜欢的观念，就是群作用。当时我在田代军老师的指引下，自学Jacobson的《基础代数》中译本。