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

オイラーのトーシェント関数 $φ(n)$ (ファイ関数とも呼ばれる) とは、 $n$ 未満の正の整数で $n$ と互いに素なものの個数を表す。例えば 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので $φ(9) = 6$ となる。