オイラーのφ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

オイラーのトーティエント関数（トーティエント-かんすう、totient function）は各正の整数 n に対して、1 から n までの正整数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2 個であるから、定義に拠れば φ(6) = 2 である。また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 と定まる。慣例的に φ(n) と表記されるため、オイラーの φ 関数（ファイかんすう、phi function）とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。

[編集] 性質

p を素数とすると、1 から p − 1 のうちに p の素因子である p を因子として含むものは存在しないから φ(p) = p − 1 が成り立ち、同様に p の冪は p の冪でしか割り切れないので k を正整数として

$\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac{1}{p}\right)$

が成立することが確かめられる。また、m, n を互いに素な正整数とすると、φ(mn) = φ(m)φ(n) が成り立つ。これをオイラーの関数は（互いに素な数の積に関して）乗法的であると言い表す。これらのことからさらに、任意の自然数 n における値を知ることができる。実際に、p_k はどの二つも相異なる素因数であるとして、n の素因数分解が次のように

$n = \prod_{k=1}^d {p_k}^{e_k}$

と与えられているならば、

$\varphi(n) = n \prod_{k=1}^d \left(1-\frac{1}{p_k}\right)$

によって φ(n) を計算することができる。

正整数 n, d で d が n を割り切るものとすると、1 から n までの整数のうち n との最大公約数が 'n / d であるものの数は φ(d) 個である。特に、1 から n までの整数は n との最大公約数によって類別されるから、d が n の正の約数全てを亘る和に関して等式

$\sum_{d|n} \varphi(d) = n$

が成り立つ（d | n は d が n を割り切るの意）。

G を位数 n の巡回群とすれば、n の約数 r に対して G の位数 r の元は φ(r) 個存在する。特に、巡回群 G の生成元は φ(n) 個存在する。

正の整数 a, m (1 ≤ a < m) とするとき、剰余環 Z/m Z に属する剰余類 a + m Z が既約、つまり Z/m Z の単数である必要十分な条件は代表元 a が m と互いに素であることであるから、既約剰余類の数は φ(m) に等しい。同じことだが、群 G の位数を #G, 環 R の単数群を R^× で表すとき、等式