オイラーのφ関数

φ(n)最初の100個の値のグラフ
φ(n)の最初の1000個の値

オイラーのトーシェント関数(オイラーのトーシェントかんすう、: Euler's totient function[2])とは、正の整数 n に対して、 n互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数 φ である。これは

と表すこともできる(ここで (m, n)mn最大公約数を表す)。慣例的にギリシャ文字φ(あるいは)で表記されるため、オイラーの φ 関数(ファイかんすう、phi function)とも呼ばれる。また、簡略的にオイラーの関数と呼ぶこともある。

1761年レオンハルト・オイラーが発見したとされるが、それより数年前に日本久留島義太が言及したとも言われる。

  • 1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2個であるから、 φ(6) = 2 である。
  • 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 である。

1 から 20 までの値は以下の通りである[3]

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8,…

性質

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

定理 ― 

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

定理 ― n素因数分解が次のように

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

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

が成り立つ(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× で表すとき、等式

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

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

が成り立つ。ここで γオイラー定数である。もし n2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ⋅ 17 ⋅ 19 ⋅ 23 であれば 2.50637 のかわりに 2.5 とおくことができる。一般に任意の ε > 0 に対して

が十分大きな n に対して成り立つ[4]。簡明な下界として がある[5]

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

が成り立つ。

トーシェント関数の値域に含まれない自然数をノントーシェントという。

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

脚注

  1. ^ Schwartzman, S. (1994). The Words of Mathematics: An Etymological Dictionary of Mathematical Terms Used in English. Mathematical Association of America. ISBN 0-88385-511-9. MR1270906. Zbl 0864.00007. https://books.google.co.jp/books?id=iuoZSkSOBQsC 
  2. ^ 英語のtotientはラテン語のtotに由来する[1]
  3. ^ オンライン整数列大辞典の数列 A000010
  4. ^ M. B. Nathanson (1996). Additive Number Theory: The Classic Bases. Springer. p. 315. ISBN 0-387-94656-X 
  5. ^ Is the Euler phi function bounded below?”. Mathematics Stack Exchange. 2020年3月26日閲覧。

関連項目

外部リンク

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!