本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
目次
オイラー関数の計算方法
自然数$n$の素因数分解を$n{=}p^{a}q^{b}r^{c}\cdots$とすると，
\begin{align}
\varphi(n) &= n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots
\end{align}
\varphi(n) &= n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots
\end{align}
が成り立つ。
証明
素数に対するオイラー関数の性質とオイラー関数の乗法的性質を組み合わせることにより，
\begin{align}
\varphi(n)
&= \varphi(p^{a})\varphi(q^{b})\varphi(r^{c})\cdots\\[0.7em]
&= (p^{a}-p^{a-1})(q^{b}-q^{b-1})(r^{c}-r^{c-1})\cdots\\[0.7em]
&= p^{a}\left(1-\frac{1}{p}\right)q^{b}\left(1-\frac{1}{q}\right)r^{c}\left(1-\frac{1}{r}\right)\cdots\\[0.7em]
&= n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots
\end{align}
\varphi(n)
&= \varphi(p^{a})\varphi(q^{b})\varphi(r^{c})\cdots\\[0.7em]
&= (p^{a}-p^{a-1})(q^{b}-q^{b-1})(r^{c}-r^{c-1})\cdots\\[0.7em]
&= p^{a}\left(1-\frac{1}{p}\right)q^{b}\left(1-\frac{1}{q}\right)r^{c}\left(1-\frac{1}{r}\right)\cdots\\[0.7em]
&= n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)\left(1-\frac{1}{r}\right)\cdots
\end{align}
が得られます。
コメント