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


在前两期

一周一定理No.1 中国剩余定理

一周一定理No.2  求一术与方程术

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


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


他还说(大意):只有当一个教师能够教会计算机了,才能教明白学生。


1.jpg

高德纳




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


欧拉定理 n是正整数,a 是一个整数,且a  n互素,则

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

2.jpg

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

4.jpg

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

5.jpg

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


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


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


6.jpg



又如今年(2018年)国庆节是星期一,由此可知明年的国庆节是星期二,因为

7.jpg

Question1: 2020年的国庆节星期几?(注意,这里有个


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

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

8.jpg

推出高斯属鸡(2017年是鸡年).


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


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

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


12.jpg


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

13.jpg

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


14.jpg

:历史上先有费马小定理,而后有欧拉定理,因此欧拉定理也被称为费马-欧拉定理


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


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


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


16.jpg

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页):


17.jpg



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


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


Alissa S. Crans、Thomas M Fiore、Ramon Satyendra 的二面体群作


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

18.jpg


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


Question6: 已知 2017是素数,求 

19.jpg



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


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




0.269377s