歐拉函數

模

的同餘類指的是模

餘數相同的整數構成的集合。

在模

的

個同餘類

中，每一類

中取一個數

，則

叫做模

的一個完全剩餘系(簡稱完系)。顯然，完系中的

個數分別屬於

個不同的剩餘類。

最簡單的模

的完全剩餘系是

，也叫作模

的最小非負完系。

一組數

稱為是模

的既約剩餘系(簡稱縮系)，如果對

，並定義

，即

中與

互素的數的個數，

稱為歐拉函數。

顯然

，而對於

，

就是

中與

互素的數的個數，比如説

，則有

。

⑴設

，則有

①若

和

有相同的素因數，那麼

,其中

②若

，則

⑵關於歐拉函數的兩個重要結論：

①對於

有

.

②引理：

.

①的證明：

易證

對

,

,設

,則

.一方面數

有

個，另一方面(按

分類計數)滿足

的

有

種取法.故有

②從反面思考或利用容斥原理易證.

⑶歐拉定理：設

，則

.

特別地，當

為素數時，

.

歐拉定理的證明：

取模

的縮系

，則

也是模

的縮系.

特別地，當

時，

，此時