オイラー関数
自然数$N$を素因分解した形
$N = a_{1}^{p_1} a_{2}^{p_2} ... a_{n}^{p_n}$
で表すとします。
この$N$の関数$φ(N)$を次のように定めます($φ$はトーシェントと読む)。
$φ(N) = N(1 -\dfrac{1}{a_1})(1 -\dfrac{1}{a_2})...(1 -\dfrac{1}{a_n})$
この関数は、N以下の自然数でNと互いに素の個数を表し、
オイラーのトーシェント関数と呼びます。
オイラー関数の使用例
$N = 10$として、N以下の自然数でNと互いに素の個数を求めてみたいと思います。
10を素因数分解すると
$10 = 2 \cdot 5$
オイラー関数に当てはめると
$φ(10) = 10(1 -\dfrac{1}{2})(1 -\dfrac{1}{5}) = 4$
実際10以下の互いに素の個数は
$2,3,7,9$で$4$個
以上のように使うことができます。
初版:2023/5/24
更新:2023/8/13(オイラー関数の使用例を追加した)
