本記事は数学の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
オイラー関数の和
自然数$n$の正の約数の集合を$D$とおくと，
\sum_{d\in D}\varphi(d) &= n\label{主題}
\end{align}
が成り立つ。
証明
やや天下り的ですが，公約数の定義から，自然数$n$の正の約数$d$からなる集合$D$は$n/d$からなる集合$D^{\prime}$と等しくなりますので，
\sum_{d\in D}\varphi(d)
&= \sum_{d^{\prime}\in D^{\prime}}\varphi(d^{\prime})
= \sum_{d\in D}\varphi\left(\frac{n}{d}\right)
\end{align}
となります。さらに天下り的ですが，$\gcd(x,n){=}d$となる$x$の個数が$\varphi(n/d)$で与えられることを示すことができれば，$d$を集合$D$の中で動かしたときに$\gcd(x,n){=}d$を満たす$x$は$\{1,\ldots, n\}$を漏れなく重複なく動くため，式($\ref{主題}$)を示すことができます。
そこで，$\gcd(x,n){=}d$となる$x$の個数が$\varphi(n/d)$で与えられることを示します。$x$は少なくとも$d$の倍数である必要があるため，自然数$x^{\prime}$を用いて
x &= x^{\prime}d
\end{align}
と表されます。このとき，$n^{\prime}{=}n/d$とおくと，$\gcd(x,n){=}d$は
&\gcd(x^{\prime}d, n^{\prime}d) = d\\[0.7em]
&~\Rarr~\gcd(x^{\prime}, n^{\prime}) = 1
\end{align}
となります。逆に，$\gcd(x^{\prime}, n^{\prime}){=}1$のとき$\gcd(x,n){=}d$を示します。$\gcd(x,n){=}e$とおくと，$d$は$x$と$n$の公約数となるため，自然数$e^{\prime}$を用いて
e &= e^{\prime}d
\end{align}
と表されます。一方，$e{=}e^{\prime}d$は$x{=}x^{\prime}d$の約数および$n{=}n^{\prime}d$の約数であることから，$e^{\prime}$は$x^{\prime}$および$n^{\prime}$の約数となります。$\gcd(x^{\prime}, n^{\prime}){=}1$に注意すると$e^{\prime}{=}1$となり，$e{=}d$が得られました。以上より，
&\gcd(x, n) = d\\[0.7em]
&~\Lrarr~\gcd(x^{\prime}d, n^{\prime}d) = d\\[0.7em]
&~\Lrarr~\gcd(x^{\prime}, n^{\prime}) = 1\\[0.7em]
&~\Lrarr~\varphi(n^{\prime})
\end{align}
が示されたため，$\gcd(x, n){=}d$は$\varphi(n^{\prime})$で与えられます。
コメント