オイラー関数

オイラー関数とは、正の整数nと互いに素な正の整数の個数を表す関数です。この関数は、レオンハルト・オイラーによって導入されました。

オイラー関数を表す一般的な記号は、$\varphi(n)$です。例えば、$\varphi(1) = 1$、$\varphi(2) = 1$、$\varphi(3) = 2$、$\varphi(4) = 2$、$\varphi(5) = 4$、$\varphi(6) = 2$、$\varphi(7) = 6$、$\varphi(8) = 4$、$\varphi(9) = 6$、$\varphi(10) = 4$、$\varphi(11) = 10$、$\varphi(12) = 4$、$\varphi(13) = 12$、$\varphi(14) = 6$、$\varphi(15) = 8$、$\varphi(16) = 8$、$\varphi(17) = 16$、$\varphi(18) = 6$、$\varphi(19) = 18$、$\varphi(20) = 8$、$\varphi(21) = 12$、$\varphi(22) = 10$、$\varphi(23) = 22$、$\varphi(24) = 8$、$\varphi(25) = 20$、$\varphi(26) = 12$、$\varphi(27) = 18$、$\varphi(28) = 12$、$\varphi(29) = 28$、$\varphi(30) = 8$、$\varphi(31) = 30$、$\varphi(32) = 16$、$\varphi(33) = 20$、$\varphi(34) = 16$、$\varphi(35) = 24$、$\varphi(36) = 12$、$\varphi(37) = 36$、$\varphi(38) = 18$、$\varphi(39) = 24$、$\varphi(40) = 16$、$\varphi(41) = 40$、$\varphi(42) = 12$、$\varphi(43) = 42$、$\varphi(44) = 20$、$\varphi(45) = 24$、$\varphi(46) = 22$、$\varphi(47) = 46$、$\varphi(48) = 16$、$\varphi(49) = 42$、$\varphi(50) = 20$です。

オイラー関数には、いくつかの性質があります。以下にいくつかの性質を挙げます。

1. $n$が素数$p$の場合、$\varphi(n) = p - 1$です。
2. $n$が異なる素数$p_1, p_2, \cdots, p_k$の積である場合、$\varphi(n) = n \cdot \left( 1 - \frac{1}{p_1} \right) \cdot \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_k} \right)$です。
3. $n$が正の整数$m$の$k$乗である場合、$\varphi(n) = m \cdot \left( 1 - \frac{1}{p} \right)$です。ただし、$p$は$m$の素因数です。
4. $n$が正の整数$m$と互いに素である場合、$\varphi(mn) = \varphi(m) \cdot \varphi(n)$です。
5. $n$が正の整数の場合、$\sum\limits_{d \mid n} \varphi(d) = n$です。ここで、$d \mid n$は$d$が$n$の約数であることを表します。

オイラー関数は、数学において重要な役割を果たしています。例えば、RSA暗号においては、オイラー関数を用いて、公開鍵と秘密鍵を生成します。

オイラー関数についての詳しい説明は、数学の教科書やウェブサイトなどで確認することができます。

リンク

Euler's totient function[EN]