オイラーのトーシェント関数の定義

オイラーのトーシェント関数

正の整数\(n\)に対し、\(n\)と互いに素である1以上\(n\)以下の個数をオイラーのトーシェント関数といい、\(\varphi(n)\)で表す。

\begin{align*} \varphi(n) & =\#\left\{ k\in\mathbb{N};1\leq k\leq n,\gcd(k,n)=1\right\} \\ & =\sum_{1\leq k\leq n,\gcd(k,n)=1}1 \end{align*}