【徹底解説】素数に対するオイラー関数

本記事は数学の徹底解説シリーズに含まれます。

初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

素数に対するオイラー関数

証明

素数の定義より$p$と互いに素となる数は$p{-}1$個となるため，$\varphi(p){=}p{-}1$となります。また，$p^{e}$と互いに素でない数は$p$の倍数と一致します。$1,\ldots,p^{e}$のうち$p$の倍数は$p^{e}/p{=}p^{e-1}$個存在することに注意すれば，$\varphi(p^{e}){=}p^{e}{-}p^{e-1}$と表されます。