Eulerのtotient関数
Eulerのtotient関数
$\varphi(N)$ を
Eulerの定理
にあらわれたEuler関数とする。すなわち
$1, 2, \ldots, N-1$ のうち $N$ と互いに素な整数の個数とする。
合同式:定理7.2
で述べたように
$$N=p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$
と素因数分解すると
$$\varphi(N)=\prod_{i=1}^r p_i^{e_i-1}(p_i-1)$$
となる。このことは包含と除去の原理から証明することもできる。
$S=\{0, 1, \ldots, N-1\}$ とし、$1\leq i\leq r$ に対して
$$S_i=\{m\in S, p_i\mid m\}$$
を $0, 1, \ldots, N-1$ のうち $p_i$ の倍数全体の集合とする。
とおく。
$T$ を $0, 1, \ldots, N-1$ のうち、$N$ と互いに素な整数全体の集合とすると
$$T=S\backslash \bigcup_{p\mid d}S_p$$
が成り立つ。一方
$$S_I=\bigcap_{i\in I}S_I$$
とおくと、$S_I$ は $\prod_{i\in I}p_i$ の倍数全体の集合だから
$$\#S_I=\frac{N}{\prod_{i\in I}p_i}$$
が成り立つ。よって包含と除去の原理より
$$\begin{split}
\# T= & \sum_{I\in \{1, 2, \ldots, r\}}(-1)^{\# I}\frac{N}{\prod_{i\in I}p_i} \\
= & N\sum_{I\in \{1, 2, \ldots, r\}} \prod_{i\in I}\left(-\frac{1}{p_i}\right) \\
= & N\prod_{i=1}^r \left(1-\frac{1}{p}\right)
\end{split}$$
となる。
このことから、約数関数と同様に、次のことがわかる。
$\gcd(m, n)=1$ ならば $\varphi(mn)=\varphi(m)\varphi(n)$.
$\varphi(n)$ の値について、次のことがすぐにわかる。
$\varphi(n)$ が奇数ならば、$n=1$ または $2$ で、$\varphi(n)=1$.
$p$ が奇素数のとき、$\varphi(p^e)=p^{e-1}(p-1)$ は $p-1$ で割り切れるから偶数。よって、$n$ が奇素数を素因数にもつとき、$n$ は偶数。
また、$n=2^e$ のとき、$\varphi(n)=2^{e-1}$ なので、$\varphi(n)$ が奇数ならば $e=1$ でなければならない。
よって、$\varphi(n)$ が奇数ならば、$n=1$ または $2$ である。このとき、$\varphi(n)=1$ となる。
参考文献
