オイラーのφ関数(Euler's Phi function)は正の整数 n に対して定義される関数で、通常φ(n)と表記される。1 から n までの正整数のうち n と互いに素なものの個数を与える関数である。
オイラー関数, オイラーのトーティエント関数(Euler's totient function)とも呼ばれる。
例
- 1,2,3,4,5,6のうち、6と互いに素なのは1,5の2個であるから、φ(6) = 2
- 1,2,3,4,5,6,7のうち、7以外は全て7と互いに素だから、φ(7) = 6
計算法
nの素因数分解が次のように与えられているものとする。ただし、pkは互いに相異なる素数とする。
このとき、φ(n)は次によって計算できる。
性質
- p を素数とすると、φ(p) = p - 1
- m,n を互いに素な正整数とすると、φ(mn) = φ(m)φ(n)
-
- 剰余環 Z/mZ の単数群の位数はφ(m)である。
- G を位数 n の巡回群とする。n の約数 r に対して、位数が r の G の元は φ(r) 個存在する。
- 特に、巡回群 G の生成元は φ(n)個存在する。
関連記事
