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

在前兩期

我們分別介紹了初等數論中的兩個基本結果，中國剩餘定理與求一術（及其推廣方程術）。與其說它們是定理，還不如說它們是演算法。演算法與普通的定理有個差別，演算法應用起來是要操作整個過程，而定理可能只需要你會用最終結論。所以你要掌握演算法，就免不了要走一遍程序。也正是這個原因，不會跳躍的計算機很容易理解演算法。記得編程大師高德納(D. E. Knuth)有句名言：

所謂科學，就是能夠教會計算機的東西。

他還說（大意）：只有當一個教師能夠教會計算機了，才能教明白學生。

高德納

今天我們介紹初等數論中一個地地道道的定理，歷史上著名的歐拉定理。大數學家歐拉(Euler)有許多定理，我們這裡所指的是下一個：

歐拉定理：設n是正整數，a是一個整數，且a與n互素，則

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

其中（φ是希臘字母，發音即 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，音樂中的二面體群作用，中譯文收入「數學與人文」叢書第17輯《數學的藝術》，丘成桐；劉克峰；楊樂；季理真李方主編，高等教育出版社，2015年。

最後，回到歐拉定理本身，為加深你對這個定理的印象，我們再給出一個練習：

Question6: 已知 2017是素數，求

小結：歐拉定理體現了這樣的觀念，在整數中存在著結構（在這裡，就是群）。有了這樣的觀點，許多東西理解起來會比較簡單而深刻，因為一些表面上不同的東西可以得到統一。陳省身先生曾經說，真正重要的觀念是很少的，毫無疑問，群是其中一個。

P. S. 寫到這裡，我回想起從前念書時，我讀到的第一個很喜歡的觀念，就是群作用。當時我在田代軍老師的指引下，自學Jacobson的《基礎代數》中譯本。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！