關於歐拉函數及其一些性質的美妙證明(1)

05-23

來自專欄「數學與邏輯」之美

關於歐拉函數及其一些性質的美妙證明（1）

歐拉函數是數論中最重要也是最基礎的一個函數，這個函數的很多性質及其證明雖然基礎，但是顯得很「燒腦」，一些數學愛好者往往看了不少資料，最終仍然「莫名其妙」，不能理解它的奧妙所在。這回，我努力用一些更容易看懂的方式，來證明（或者叫說明）歐拉函數許多有趣的性質。

一、什麼是歐拉函數？

歐拉是一位極其偉大的數學家，他一生建樹頗多，在數論領域也有著很多貢獻。歐拉函數就是以他的名字命名的一個數論中的極其基礎同時也極其重要的函數。歐拉函數的概念簡單易懂，但是帶來的性質卻讓人很難一眼看穿，這也是數論基礎知識中很有思維樂趣的地方。

對於一個正整數n，歐拉函數被定義為小於等於n且與n互質的正整數的個數，記為 $?(n)$ 。

注意，上面說的「小於等於n」的「等於」僅在n=1時才出現，n>1時，n不會與自身互質。

對於較小的數，歐拉函數很容易手工計算，比如與1、2互質的數只有1，與3互質的數有1和2兩個，與4互質的數有1和3兩個，與5互質的數有1、2、3、4共4個，與6互質的數有1和5兩個，於是：

$?(1)=1 ?(2)=1 ?(3)=2 ?(4)=2 ?(5)=4 ?(6)=2$

從上面可以看出，歐拉函數值肯定是一個正整數，但是歐拉函數不是一個增函數，更不是一個嚴格增函數。歐拉函數定義簡單明確，卻具有很多奇妙的性質。

二、歐拉函數的兩個有趣性質

1、如果正整數a與n互質，那麼 $a^{?(n)} ≡1 (mod n)$ 。

這個性質敘述上很簡單，但是如果有誰能夠立刻明白為什麼，或者能夠直接判斷此性質成立，那麼這個人一定具有極為良好的數學直覺和極佳的數學天賦！絕大多數人都很難自行證明這個性質。下面給出一個美妙且並不複雜的證明。

既然小於n且與n互質的數有 $?(n)$ 個，那麼我們設這 $?(n)$ 個數是 $u_1 、u_2 、$ ...、 $u_{?(n)}$ ，它們每個數都小於n。

然後我們考察這 $?(n)$ 個數與a相乘後得到的新的 $?(n)$ 個數，為 $a·u_1 、a·u_2 、$ ...、 $a·u_{?(n)}$ ，它們中任意兩個數的差都不能被n整除。這是因為任意兩個數的差是

$a·u_i-a·u_j=a·(u_i-u_j)$ ，其中a與n互質，而 $(u_i-u_j)$ 又小於n。

這意味著新的 $?(n)$ 個數除以n得到的餘數兩兩不相同。

另外，由於每個 $u_i$ 都與n互質，a也與n互質，這就是說每個 $a·u_i$ 都與n互質。我們知道，與n互質的數除以n得到的餘數也必然與n互質。也就是說，這新的 $?(n)$ 個數除以n得到的數都是小於n且與n互質的數。

而小於n且與n互質的數正好就是 $u_1 、u_2 、...、u_{?(n)}$ 。

所以我們知道，新的 $?(n)$ 個數除以n的餘數就是 $u_1 、u_2 、...、u_{?(n)}$ 。當然，不見得恰巧順序也一一對應。

有了這個結論，我們顯然可以得到以下同餘式成立，

$a·u_1·a·u_2·...·a·u_{?(n)} ≡u_1·u_2·...·u_{?(n)} (mod n)$

即

$a^{?(n)} ·u_1·u_2·...·u_{?(n)} ≡u_1·u_2·...·u_{?(n)} (mod n)$

即

$a^{?(n)} ≡1 (mod n)$

這個性質又被叫做歐拉定理，是數論中非常有名、非常基礎的定理。在比歐拉早幾十年的一個著名大牛民間數學家費馬曾經得到了一個定理，對於正整數a和素數p，如果p不能整除a，那麼

$a^{(p-1)}≡1 (mod p)$

可以被看作是歐拉定理的一個特例。因為對於素數p， $?(p)=p-1$ 。

有一個與我們日常生活息息相關的非對稱加密演算法——RSA演算法，就是基於歐拉定理設計出來的。感興趣的朋友可以在網上查一下RSA演算法的原理，很容易就可以利用歐拉定理給出證明。

2、對於每個能夠整除n的正整數d，其歐拉函數之和恰好為n。或者說，n的所有因子的歐拉函數之和等於n。

這個性質用數學公式表示為， $∑_{(d|n)}?(d) =n$ 。

這個性質更不容易立刻想通了。從基本概念出發，n的每個因子d，小於d且與d互質的正整數的個數加在一起，居然恰好等於n，好神奇！？

我們驗證一下一個小一點的數字，比如n=10，那麼n的因子有1、2、5、10。容易計算得到，

$?(1)=1 ?(2)=1 ?(5)=4 ?(10)=4$

把它們加起來，恰好結果是10。

這個性質用一些高等的數學工具會給出更精鍊的證明，不過涉及到的數學知識會深一些。下面我給出的這個證明，相信對於具有紮實初中數學基礎的數學愛好者，都應該可以看懂。無論是使用深一些的數學知識還是更初等的數學知識證明，其數學實質都是一樣的。

我們首先設n的全部因子為 $d_1$ 、 $d_2$ 、…、 $d_k$ 。對於每個 $d_i$ ，我們再設與 $d_i$ 互質且小於等於 $d_i$ 的 $?(d_i )$ 個數為 $β_{i,1} 、β_{i,2} 、...、β_{i,?(d_i ) }$ 。

顯然，所有的 $(β_{i,j}，d_i) ，(i=1,2,...,k; j=1,2,...,?(d_i ))$ 數對們的個數就是要計算的 $∑_{(d|n)}?(d)$ 。

下面，我們定義兩個集合，並在這兩個集合之間建立一一對應，如果這個一一對應建立成功，就說明這兩個集合中元素的個數是一樣多的，從而就證明了命題。

定義集合 $A={(β_{i,j}，d_i) | (β_{i,j}，d_i)，(i=1,2,...,k; j=1,2,...,?(d_i ))}$ ，即A是全部 $(β_{i,j},d_i)$ 數對的集合。

定義集合B={1,2,…,n}，就是前n個正整數的集合。

下面在集合A到B之間建立一個映射，

$f(A→B) : (β_{i,j}，d_i)→β_{i,j}·n/d_i$

這個映射是可以成立的，因為任意 $1≤β_{i,j}≤d_i$ ，所以 $n/d_i ≤β_{i,j}·n/d_i ≤n$ ，而且

$n/d_i$ 是整數，所以 $β_{i,j}·n/d_i$ 必然是一個1到n之間的整數。

下面我們來證明這個映射是一個一一對應（雙射）。這隻需要證明兩點，一是A中不同的元素映射成的B中的元素也不同（單射），二是B中每個元素都有A中元素來對應（滿射）。

先來證明第一點（單射成立）。

A中的兩個不同元素有兩種情況，一是i相同但j不同，設為 $(β_{i,j}，d_i)$ 和 $(β_{i,j}，d_i)$ ， $j≠j$ 。

此時顯然 $β_{i,j}≠β_{i,j}$ ，所以 $β_{i,j}·n/d_i ≠β_{i,j}·n/d_i$ ，所以對應的B中元素不同。

二是i就不同，設為 $(β_{i,j}，d_i)$ 和 $(β_{i,j}，d_{i})$ ， $i≠i$ ，也即 $d_i≠d_{i}$ 。因為只要i不同，相應的數對就不同，這種情況下無須 $j≠j$ 。

這兩個A中元素對應的B中元素分別是 $β_{i,j}·n/d_i$ 和 $β_{i,j}·n/d_{i}$ ，如果它們相等，有

$β_{i,j}·n/d_i =β_{i,j}·n/d_{i} ? β_{i,j}·d_{i}=β_{i,j}·d_i$

因為 $eta_{i,j}$ 與 $d_i$ 互質，因此上面等式成立意味著 $eta_{i,j}$ 要整除 $eta_{i,j}$ ；同理，因為 $eta_{i,j}$ 與 $d_{i}$ 互質，因此上面等式成立意味著 $eta_{i,j}$ 要整除 $eta_{i,j}$ 。這就是說， $β_{i,j}=β_{i,j}$ ，這意味著 $d_{i}=d_i$ ，因此與 $d_i e d_{i}$ 矛盾。