在前兩期
我們分別介紹了初等數論中的兩個基本結果，中國剩餘定理與求一術（及其推廣方程術）。與其說它們是定理，還不如說它們是算法。算法與普通的定理有個差別，算法應用起來是要操作整個過程，而定理可能只需要你會用最終結論。所以你要掌握算法，就免不了要走一遍程序。也正是這個原因，不會跳躍的計算機很容易理解算法。記得編程大師高德納(D. E. Knuth)有句名言：
所謂科學，就是能夠教會計算機的東西。
他還說（大意）：只有當一個教師能夠教會計算機了，才能教明白學生。
高德納
今天我們介紹初等數論中一個地地道道的定理，歷史上著名的歐拉定理。大數學家歐拉(Euler)有許多定理，我們這裡所指的是下一個：
歐拉定理：設 n是正整數，a 是一個整數，且a與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的《基礎代數》中譯本。
閱讀更多 好玩的數學 的文章
