数学

1からnまでの自然数のうちnと互いに素なものの個数を求める

Qiita初投稿。
オイラー関数です。間違っているところがあったら教えてください。
コードも載せたいなと思ったのですが、プログラミング力がまだアレすぎるので今回は載せません(ほんとうは書けない)。

とりあえずざっくり

$n, k$は自然数であるとし、$E(n)$は1以上n以下の自然数のうち$n$と互いな素であるような数の個数を求める関数であるとします。

nが

n = p_1^{r_1}×p_2^{r_2}×\ldots×p_{k}^{r_k}

のように因数分解されるとき(素因数分解の一意性からすべての自然数は素因数分解できる)、1以上n以下の自然数のうちnと互いに素な数の個数E(n)は

\begin{align*}
E(n)=n×(1-{\frac{1}{p_1}})×(1-{\frac{1}{p_2}})×\ldots×(1-{\frac{1}{p_k}}) \\
=(p_1 - 1)×(p_2 - 1)×\ldots×(p_k - 1)×{p_1}^{r_1 - 1}×{p_2}^{r_2 - 1}×\ldots×{p_k}^{r_k - 1}
 \end{align*}

で求められます。(1からnまでの数を列挙して、$p_1$の倍数, $p_2$の倍数, $\ldots$, $p_k$の倍数をふるいにかけて落としていく、というイメージ(伝わって))
なお、$m$と$n$が互いに素であるとき、$E(m)E(n)=E(mn)$が成り立ちます。

\begin{align*}
E(1024) = E(2^{10})
=1024×(1-{\frac{1}{2}})
=512
\end{align*}
\begin{align*}
E(7) = E(7^1) = 7 × (1- \frac{1}{7}) = 6
\end{align*}

どう応用するの?

ウーン、センター試験で時短になるくらいしか思いつかない。ぐぐってみてもあんまりそれらしき情報もない。重要な応用例を知っているよ!という方がいらっしゃったらその応用例をぜひ教えていただけるとうれしいです(ひと任せ)!