歐拉函式

在數論，對正整數n，歐拉函式是小於n的正整數中與n互質的數的數目。

基本介紹

• 中文名：歐拉函式
• 外文名：Euler's totient function
• 所屬學科：數論

基本性質

定義

一組數稱為是模的既約剩餘系(簡稱縮系)，如果對，並定義，即中與互素的數的個數，稱為歐拉函式。

顯然，而對於，就是中與互素的數的個數，比如說，則有。

性質

⑴設，則有

①若和有相同的素因數，那么,其中

②若，則

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

①對於有.

②引理：.

①的證明：

易證

對,,設,則.一方面數有個，另一方面(按分類計數)滿足的有種取法.故有

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

⑶歐拉定理：設，則.

特別地，當為素數時，.

歐拉定理的證明：

取模的縮系，則也是模的縮系.

特別地，當時，，此時

同餘類和完系

同餘類

模的同餘類指的是模餘數相同的整數構成的集合。

完系

在模的個同餘類中，每一類中取一個數，則叫做模的一個完全剩餘系(簡稱完系)。顯然，完系中的個數分別屬於個不同的剩餘類。

最簡單的模的完全剩餘系是，也叫作模的最小非負完系。