歐拉函數(shù)是數(shù)論中很重要的一個(gè)函數(shù)，歐拉函數(shù)是指：對(duì)于一個(gè)正整數(shù) n ，小于 n 且和 n 互質(zhì)的正整數(shù)（包括 1）的個(gè)數(shù)，記作 φ(n) 。
定義小于 n 且和 n 互質(zhì)的數(shù)構(gòu)成的集合為 Zn ，稱(chēng)呼這個(gè)集合為 n 的完全余數(shù)集合。 顯然 |Zn| ＝φ(n) 。
對(duì)于兩個(gè)不同素?cái)?shù) p， q ，它們的乘積 n = p * q 滿(mǎn)足 φ(n) = (p -1) * (q -1) 。
這個(gè)是歐拉定理的特殊情況，p是素?cái)?shù)，則p的歐拉函數(shù)就是p-1.
( 1 ) pk 的歐拉函數(shù)
對(duì)于給定的一個(gè)素?cái)?shù) p ， φ(p) = p -1。則對(duì)于正整數(shù) n = pk ，
φ(n) = pk - pk -1
證明：
小于 pk 的正整數(shù)個(gè)數(shù)為 pk - 1個(gè)，其中
和 pk 不互質(zhì)的正整數(shù)有{p * 1,p * 2,...,p * (pk - 1-1)} 共計(jì) pk - 1 - 1 個(gè)
所以 φ(n) = pk - 1 - (pk - 1 - 1) = pk - pk - 1 。
( 2 ) p * q 的歐拉函數(shù)
假設(shè) p, q是兩個(gè)互質(zhì)的正整數(shù)，則 p * q 的歐拉函數(shù)為
φ(p * q) = φ(p) * φ(q) ， gcd(p, q) = 1 。
證明：
令 n = p * q ， gcd(p,q) = 1
根據(jù)中國(guó)余數(shù)定理，有
Zn 和 Zp × Zq 之間存在一一映射
（我的想法是： a ∈ Zp ， b ∈ Zq ⇔ b * p + a * q ∈ Zn 。）
所以 n 的完全余數(shù)集合的元素個(gè)數(shù)等于集合 Zp × Zq 的元素個(gè)數(shù)。
而后者的元素個(gè)數(shù)為 φ(p) * φ(q) ，所以有
φ(p * q) = φ(p) * φ(q) 。
( 3 ) 任意正整數(shù)的歐拉函數(shù)
任意一個(gè)整數(shù) n 都可以表示為其素因子的乘積為：
I
n = ∏ piki (I 為 n 的素因子的個(gè)數(shù))
i=1
根據(jù)前面兩個(gè)結(jié)論，很容易得出它的歐拉函數(shù)為：
I I
Φ(n) = ∏ piki -1(pi -1) = n ∏ (1 - 1 / pi)
i=1 i=1
對(duì)于任意 n > 2，2 | Φ(n) ,因?yàn)楸卮嬖?nbsp; pi -1 是偶數(shù)。