オイラーのφ関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
オイラー関数から転送)
移動先: 案内検索
ファイル:EulerPhi.svg
φ(n)の最初の1000個の値
ファイル:EulerPhi100.PNG
最初の100個の値のグラフ

オイラーのトーシェント関数(オイラーのトーシェントかんすう、テンプレート:Lang-en-short)は各正の整数 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)とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。なおトーシェント関数の値域に含まれない自然数をノントーシェントという。1761年レオンハルト・オイラーが発見したとされるが、それより数年前に日本久留島義太が言及したとも言われる。

性質

p素数とすると、1 から p − 1 のうちに p の素因子である p を因子として含むものは存在しないから φ(p) = p − 1 が成り立つ。さらに、k を自然数としたとき、 1 から pk の中で p を因子として含むもの、すなわち p の倍数は pk-1 個あるから、

<math>\varphi(p^k) = p^k - p^{k-1} = p^k\left(1 - \frac{1}{p}\right)</math>

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

<math>n = \prod_{k=1}^d {p_k}^{e_k}</math>

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

<math>\varphi(n) = n \prod_{k=1}^d \left(1-\frac{1}{p_k}\right)</math>

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

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

<math>\sum_{d \mid n} \varphi(d) = n</math>

が成り立つ(d | ndn を割り切るの意)。

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

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

<math>\varphi(m) = \sharp(\mathbb{Z}/m\mathbb{Z})^\times</math>

が成立する。これは特に、オイラーの定理 <math> a^{\varphi(m)} \equiv 1\pmod m</math> の成立を意味する。また同じ式から、1 の m 乗根で原始的であるものの一つを ζ とし、既約剰余類群 (Z/mZ)×を円分拡大 Q(ζ)/Qガロア群と見れば φ(m) が円の m 分多項式の次数に等しいことも従う。

n > 1 ならば φ(n) < n である。また、n > 3 ならば

<math>\varphi(n)\geq e^{-\gamma}\cfrac{n}{\log\log n+\cfrac{2.50637}{e^{\gamma}\log\log n}}</math>

が成り立つ。もし n=2×3×5×7×11×13×17×19×23でなければ2.50637のかわりに2.5とおくことができる。

σ(n) を約数関数とすると、n > 1において、

<math>\frac {6 n^2} {\pi^2} < \varphi(n) \sigma(n) < n^2</math>

が成り立つ。

x が1より大きい奇数の時、x はノントーシェントである。また、偶数であるノントーシェントは無数に存在する事が知られている。φ(n) = xとなるnが存在するならば、それは少なくとも2つ存在するだろうと予想されているが、未だに証明されていない。一方、任意の k > 1 に対して、 φ(n) = x となる n の個数がちょうど k 個であるような x は無数に存在することが知られている。

関連項目

外部リンク