素數的有關性質（二）歐拉函數的一些定理證明與計算

文章目錄

• ​​寫在前面​​
• ​​内容回顧​​

• ​​模剩餘類環​​

• ​​定理​​

• ​​模剩餘類域​​

• ​​定義​​

• ​​歐拉函數的定義​​
• ​​歐拉函數的性質​​

• ​​命題1：歐拉函數等于與互素整數個數​​
• ​​命題2：取值為素數的歐拉函數等于​

• ​​證明​​

• ​​定理2：取值為素數方幂的歐拉函數​​

• ​​證 明​​

• ​定理3：取值為可分解成互素整數乘積的歐拉函數​​

• ​證 明​​

• ​​證明思路​​
• ​​會用到的一些結論​​
• ​​具體步驟​​

• ​​定理4：取值為任意大于1整數的歐拉函數​​

• ​​歐拉函數的計算​​
• ​​總結​​

寫在前面

這回總結歐拉函數的一些有關定理，涉及到的以前的知識比較多，具體内容參見丘維聲教授的《數學的思維方式與創新》一書。

内容回顧

介紹後面定理證明中可能會用到的一些定義與定理，在教材中均有相關的證明，在此不做詳述。

模

m

m

m剩餘類環

定理

• 在模剩餘類環中，是可逆元當且僅當。
• 的每一個元素或者是可逆元，或者是零因子，二者必居其一，且隻居其一。

模

p

p

p剩餘類域

定義

• 設是一個有機關元的交換環，若中每一個非零元都是可逆元，那麼稱是一個域。
• 設是一個素數，則是一個域，稱其為模剩餘類域。

歐拉函數的定義

把中所有可逆元組成的集合記作，把中可逆元的個數記作，稱為歐拉函數，即。

歐拉函數的性質

下面的這些命題與定理，都可以從具體的例子中歸納總結出來，本文僅介紹定理的證明部分。

命題1：歐拉函數等于與

m

m

m互素整數個數

等于集合中與互素的整數的個數。

命題2：取值為素數

p

p

p的歐拉函數等于

p

−

1

p-1

p−1

若是素數，則.

證明

若是素數，則是一個域，進而

于是.

定理2：取值為素數方幂的歐拉函數

設是素數，則對于任一正整數，有

證 明

由于互素的整數個數不易計算，下面從不互素的整數出發進行證明。

設集合，其中與不互素的整數的個數即所求。對，利用互素整數的性質3推廣，有。若，則，進而，是以

進而中與中不互素的整數的個數為，于是得到

★

\bigstar

★定理3：取值為可分解成互素整數乘積的歐拉函數

設，且與是互素的大于的整數，則

★

\bigstar

★證 明

證明思路

這個定理的證明比較長，但思路很清晰，大緻可總結為：

1. 由于所要證明的等式是【中可逆元的個數等于中可逆元的個數乘以中可逆元的個數】，自然想到聯系兩個環(本質上是一種集合)的一種運算是将兩個環對應元素進行Cartes積（笛卡爾積），定義滿足一定條件，且經笛卡爾積運算後的環為直和：。
2. 由于和的結構并不清楚，于是想到從和入手進行分析。
3. 從映射的角度考慮兩個環的對應關系，再研究上的映射，可以發現集合計數之間的聯系。

會用到的一些結論

1. 映射的一些定義及結論，可以參考《​​關于映射的一些了解與常用定理​​》.
2. 互素的一些性質，可以參考《​​與素數有關的一些性質及證明（一）​​》.

具體步驟

• 首先考慮環和的笛卡爾積：

  規定：

  易驗證為一個交換環，且其零元為，機關元為。把這個環稱為環和環的直和，記作.

• 而
• 根據上面的推導，以及“分步計數原理”，可以得到：，是以我們隻需證明成立，即可證明這個定理。根據上面的分析，首先建立環與環之間的聯系（對應法則）。
• 建立的元素與的元素之間的對應關系，令

• 驗證上述的對應法則是否構成映射，即對中的任一進制素，是否能從中找到唯一确定的一個元素與之對應，亦即驗證

  是否成立。而

  是以是到的一個映射，而由于像相同推出其對應的原像相同，是以為單射。

• 又由于，并根據結論“建立單射且元素個數相同的兩有限集合，其對應法則也為滿射”，可以得到映射為滿射，是以為雙射。

• 下面尋找環與環的可逆元之間的關系，隻需證明存在到的一個雙射，即可得到。因為可逆元是由乘法運算定義的，是以首先要驗證保持乘法運算，即驗證成立。

  于是，

• ①：須滿足為單射且保持乘法運算;
• ②：因為是的可逆元，而是滿射（陪域等于值域），是以，進而中每個元素都可以表成的形式，又，是以。

• 由于是的可逆元是的可逆元，将映射限制在環（集合）上，記為，于是這個新的映射是到的一個映射，且該映射是滿射（陪域中每一個元素都能找到一個與之對應，即值域等于陪域），而該映射顯然為單射，是以是雙射，于是證明了

  即

定理4：取值為任意大于1整數的歐拉函數

設，其中是兩兩不等的整數，則

（這個定理是定理2與定理3的推論，利用算術基本定理及數學歸納法易證。根據此定理可以很友善地計算任意大于1整數的歐拉函數。）

歐拉函數的計算

例：計算.

總結