オイラーのφ関数

オイラーのφ関数とは、任意の自然数$n$に対して、$n$を超えない自然数のうち$n$と互いに素な数の個数として定義される関数である。例えば、$1,3,5,7$は互いに素であるため、$\varphi (8)=4$となる。スイスの数学者のレオンハルト・オイラーにちなむ。

計算

関数の定義から、$\varphi (1)=1$であり、$n$が素数$p^k$の$k$乗である場合、$\varphi (n)=(p-1)p^{k-1}$であることが直接導かれる。また、この関数は乗法的であり、$m$と$n$が互いに素である場合、$\varphi (mn)=\varphi (m)\cdot \varphi (n)$となる。よって、$\varphi (n)$の値は素因数分解によって計算できる。

$n=p_1^{k_1}...p_r^{k_r}$

したがって、

$\phi (n)=(p_1-1)p_1^{k_1-1}...(p_r-1)p_r^{k_r-1}$

最後の式はオイラー積で表され、よく次のように表記される。

$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})$

ここで、積は$n$を素因数分解した際に時数が0でない素数$p$に対して計算される。