オイラーのトーティエント関数

Number of integers coprime to and less than n

φ ( n )の最初の1000個の値。上の線上の点は、 pが素数（p − 1）のときのφ ( p )を表す^。[1]

数論において、オイラーのトーティエント関数は、与えられた整数までの正の整数のうち、と互いに素であるものを数えます。ギリシャ文字φを用いてまたはと表記され、オイラーのファイ関数と呼ばれることもあります。言い換えれば、の範囲にある最大公約数が1となる整数の個数です。^{[2] [3]}この形式の整数は、のトーティエント関数と呼ばれることもあります。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle \phi (n)}$ ${\displaystyle k}$ ${\displaystyle 1\leq k\leq n}$ ${\displaystyle \gcd(n,k)}$ ${\displaystyle k}$ ${\displaystyle n}$

例えば、 の合計は1、2、4、5、7、8 の 6 つの数です。これらはすべて 9 と互いに素ですが、この範囲の他の 3、6、9 は および であるため、互いに素ではありません。したがって、 です。別の例として、 の場合、1 から の範囲にある唯一の整数は1 自身であり、 であるためです。 ${\displaystyle n=9}$ ${\displaystyle \gcd(9,3)=\gcd(9,6)=3}$ ${\displaystyle \gcd(9,9)=9}$ ${\displaystyle \varphi (9)=6}$ ${\displaystyle \varphi (1)=1}$ ${\displaystyle n=1}$ ${\displaystyle n}$ ${\displaystyle \gcd(1,1)=1}$

オイラーのトーティエント関数は乗法関数であり、2つの数とが互いに素であれば、となる。^{[4] [5]}この関数は、nを法とする整数の乗法群（環の単位群）の位数を与える。^[6]これはRSA暗号化システムの定義にも使われる。 ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

歴史、用語、表記法

レオンハルト・オイラーは1763年にこの関数を導入した。^{[7] [8] [9]}しかし、当時はこれを表す特定の記号は選んでいなかった。1784年の出版物で、オイラーはこの関数をさらに研究し、それを表すためにギリシャ文字を選んだ。彼は「 より小さく、かつ と公約数を持たない多数の数」を と書いた。^[10]この定義は、 におけるトーティエント関数の現在の定義とは異なるが、それ以外は同じである。現在標準となっている表記法^{[8] [11]は}ガウスの1801年の論文Disquisitiones Arithmeticaeに由来するが、^{[12] [13]}ガウスは引数を括弧で囲まずに と書いた。そのため、これはオイラーのファイ関数または単にファイ関数と呼ばれることが多い。 ${\displaystyle \pi }$ ${\displaystyle \pi D}$ ${\displaystyle D}$ ${\displaystyle D=1}$ ${\displaystyle \varphi (A)}$ ${\displaystyle \varphi A}$

1879年にJJシルベスターはこの関数をトーティエントという用語で表現しました。 ^{[14] [15]そのため}、オイラーのトーティエント関数、オイラートーティエント、またはオイラーのトーティエントとも呼ばれます。^[16] ジョーダンのトーティエントはオイラーのトーティエントの一般化です。

のコトシェントはと定義されます。これはと少なくとも1つの素因数が共通する、より小さいか等しい正の整数の数を数えます。 ${\displaystyle n}$ ${\displaystyle n-\varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$

オイラーのトーティエント関数の計算

を計算するための公式はいくつかあります。 ${\displaystyle \varphi (n)}$

オイラーの積の公式

これは

${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}$

積がnを割り切る異なる素数についてであることを示しています

同等の定式化は

${\displaystyle \varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),}$

ここで、 は の素因数分解です(つまり、は異なる素数です)。 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$ ${\displaystyle n}$ ${\displaystyle p_{1},p_{2},\ldots ,p_{r}}$

これらの公式の証明は 2 つの重要な事実に依存します。

ファイは乗法関数である

これは、 gcd( m , n ) = 1ならばφ ( m ) φ ( n ) = φ ( mn )となることを意味します。証明の概要: A、B、C をそれぞれm、n、mnと互いに素でそれより小さい正の整数の集合とし、| A | = φ ( m )などとします。このとき、中国剰余定理により、A × BとCの間には一対一の関係があります。

素数べき乗の議論におけるφの値

pが素数でk≥1ならば、

${\displaystyle \varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).}$

証明: pは素数なので、gcd( p ^k , m )の取り得る値は1, p , p ² , ..., p ^kのみであり、 gcd( p ^k , m ) > 1となる唯一の条件は、 mがpの倍数、つまりm ∈ { p , 2 p , 3 p , ..., p ^{k − 1} p = p ^k }であり、そのような倍数がp ^{k − 1}個あり、そのうちp ^kより大きくない場合である。したがって、他のp ^k − p ^{k − 1個の数はすべて}p ^kと互いに素である。

オイラーの積の公式の証明

算術の基本定理によれば、n > 1 のとき、 p ₁ < p ₂ < ... < p _rが素数で各k _i ≥ 1 となる唯一の式が存在する。（ n = 1の場合は空積となる。） φの乗法性およびφ ( p ^k )の公式を 繰り返すと、 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},}$

${\displaystyle {\begin{array}{rcl}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\[.1em]&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}}$

これにより、オイラーの積の公式の両方のバージョンが得られます。

乗法性を必要としない別の証明では、代わりに集合 に適用された包含排他原理を使用して、素約数で割り切れる整数の集合を除外します。 ${\displaystyle \{1,2,\ldots ,n\}}$

例

${\displaystyle \varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.}$

言葉で説明すると、20の異なる素因数は2と5です。1から20までの20個の整数のうち半分は2で割り切れるので、10個になります。そのうちの5分の1は5で割り切れるので、20と互いに素な8つの数は1、3、7、9、11、13、17、19です

代替式では整数のみを使用します。 $${\displaystyle \varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.}$$

フーリエ変換

トーティエントは、最大公約数（GCD）の離散フーリエ変換であり、1で評価されます。 ^[17]

${\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}$

ここで、_k∈ { 1, ..., n }に対してxk =gcd( k , n )となる。そして

${\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}$

この式の実部は

${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.}$

例えば、とを用いると、オイラー積や約数の和の公式とは異なり、この公式ではnの因数を知る必要はありません。しかし、 nとn未満のすべての正の整数の最大公約数を計算する必要があり、これは因数分解には十分です。 ${\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}}$ ${\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}$ $${\displaystyle {\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}}$$

約数の和

^{ガウス[18]}によって確立された性質は、

${\displaystyle \sum _{d\mid n}\varphi (d)=n,}$

ここで、和はnのすべての正の約数dについてであり、いくつかの方法で証明できます。(表記規則については算術関数を参照してください。)

証明の一つは、φ ( d ) が巡回群 C _dの可能な生成元の数にも等しいということである 。具体的には、g ^d = 1でC _d = ⟨ g ⟩ならば、g ^{k は}dと互いに素なすべてのkに対して生成元となる。 C _nのすべての元は巡回部分群を生成し、各部分群C _d ⊆ C _nはC _nのちょうどφ ( d )個の元によって生成されるので、式は次式に従う。^{[19]同様に、この式は}n乗根の乗法群と原始d乗根に同じ議論を適用することで導くことができる。

この式は初等算術からも導出できる。^[20]例えば、n = 20とし、分母が20である1までの正の分数を考える。

${\displaystyle {\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.}$

もっと簡単に言うと、

${\displaystyle {\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}}$

これら20の分数はすべて正の分数である。k/d⁠ ≤ 1 で、分母はd = 1, 2, 4, 5, 10, 20です。分母が 20 である分数は、分子が 20 と互いに素である分数、すなわち⁠1/20、 /20、7/20、9/20、11/20、13/20、17/20、19/20⁠ ; 定義により、これはφ (20)個の分数です。同様に、分母が10の分数はφ (10)個、分母が5の分数はφ (5)個、などとなります。このように、20個の分数の集合は、 20を割り切るdごとに、大きさがφ ( d )の部分集合に分割されます。同様の議論は任意のnにも当てはまります。

メビウス反転を除数和の公式に適用すると、

${\displaystyle \varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},}$

ここで、μはメビウス関数であり、pとk≥2の各素数に対して定義される乗法関数である。この式は積の式から を乗じて次のように導くこともできる。 ${\displaystyle \mu (p)=-1}$ ${\displaystyle \mu (p^{k})=0}$ ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

例： $${\displaystyle {\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\[.5em]&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}}$$

いくつかの値

最初の 100 個の値 ( OEISのシーケンスA000010 ) が以下の表とグラフに示されています。

最初の100個の値のグラフ

φ ( n )（ 1 ≤ n ≤ 100）

＋	1	2		4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	16	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	16	20	16	24	12	36	18	24	16
40	40	12	42	20	24	22	46	16	42	20
50	32	24	52	18	40	24	36	28	58	16
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

右のグラフでは、一番上の線y = n − 1は、1以外のすべてのnに対して成立する上限であり、 nが素数の場合にのみ達成されます。単純な下限は ですが、これはかなり緩いものです。実際、グラフの下限は⁠に比例します。 ${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$n/ログ ログn⁠ . ^[21]

オイラーの定理

これは、aとnが互いに素であれば、

${\displaystyle a^{\varphi (n)}\equiv 1\mod n.}$

nが素数である特殊なケースは、フェルマーの小定理として知られています。

これはラグランジュの定理と、 φ ( n )がnを法とする整数の乗法群の位数であるという事実から導かれます。

RSA暗号システムは、この定理に基づいています。つまり、関数a ↦ a ^e mod n（eは（公開）暗号化指数）の逆関数は関数b ↦ b ^d mod n （ dは（秘密）復号化指数）がe を法とする逆数φ ( n )であることを意味します。 nの因数分解を知らずにφ ( n )を計算することの難しさは、したがってdを計算することの難しさです。これは、n を因数分解することで解決できるRSA 問題として知られています。 RSA 秘密鍵は、 n を2 つの（ランダムに選択された）大きな素数pとqの積として選択することで作成されるため、秘密鍵の所有者は因数分解を知っています。nのみが公開されており、大きな数を因数分解する難しさを考えると、他の誰も因数分解を知らないという保証があります。

その他の公式

• ${\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}$
• ${\displaystyle m\mid \varphi (a^{m}-1)}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}$
  • 特に：
• ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}$
• ${\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
• ${\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}$

これを次の公式と比較してください （最小公倍数を参照）。 ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$

• φ ( n )はn ≥ 3 のとき偶数となる。
  さらに、 n がr 個の異なる奇数の素因数を持つとき、 2 ^r | φ ( n )
• 4 ∤ nとなるような任意のa > 1かつn > 6に対して、l | φ ( a ⁿ − 1)となるl ≥ 2 n が存在する。
• ${\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}$

ここで、rad( n )はnの根号（ nを割り切るすべての異なる素数の積）です。

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$ ^[22]
• ${\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}$
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ （^[23]は[24]で引用）
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$[劉 (2016)]
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ^[23]
• ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}$ ^[25]
• ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)}$ ^[25]
  （ここでγはオイラー・マスケロニ定数である）。

メノンの正体

1965年にP.ケサヴァ・メノンは

${\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),}$

ここで、_d ( n ) = σ0 ( n )はnの約数の個数です。

任意の固定正整数で割り切れる

具体的な結果としては未発表であるが、古くから知られている以下の性質^[26]は重要な帰結をもたらす。例えば、任意の整数 について を法とする等差数列におけるの値が一様分布することは不可能である。 ${\displaystyle \varphi (n)}$ ${\displaystyle q}$ ${\displaystyle q>1}$

• 固定された正の整数 に対して、関係式はほぼすべての に対して成立します。つまり、以外のすべての値に対して成立します。 ${\displaystyle q}$ ${\displaystyle q|\varphi (n)}$ ${\displaystyle n}$ ${\displaystyle o(x)}$ ${\displaystyle n\leq x}$ ${\displaystyle x\rightarrow \infty }$

これは、1 を法として合同な素数の逆数の和が発散するという事実の基本的な帰結であり、それ自体が等差数列に関するディリクレの定理の証明の系である。 ${\displaystyle q}$

生成関数

φ ( n )のディリクレ級数は、リーマンゼータ関数を用いて次のように表すことができます。^[27]

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}$

ここで、左側は について収束します。 ${\displaystyle \Re (s)>2}$

ランバート級数生成関数は^[28]

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}$

これは| q | < 1で収束します。

これらは両方とも、基本的な級数操作とφ ( n )の公式によって証明されます。

成長率

ハーディとライトの言葉によれば、φ ( n )の順序は「常に『ほぼn』である」^[29]

まず^[30]

${\displaystyle \lim \sup {\frac {\varphi (n)}{n}}=1,}$

しかしnが無限大に近づくと、^{[31]すべての}δ > 0に対して

${\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}$

これら2つの式は、 φ ( n )と約数和関数 σ ( n )の式を少し使用して証明できます。

実際、2番目の式の証明の際、不等式

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}$

n > 1 の場合に真であることが証明されています。

また、^[21]

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}$

ここで、γはオイラー定数γ = 0.577215665...であるため、e ^γ = 1.7810724...およびe ^{− γ} = 0.56145948...となります。

これを証明するには素数定理は必ずしも必要ではない。^{[32] [33]} log log nは無限大なので、この式は

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}$

実際、それ以上のことが真実です。^{[34] [35] [36]}

${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}$

そして

${\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}$

2番目の不等式はジャン＝ルイ・ニコラによって示されました。リーベンボイムは「この不等式は、まずリーマン予想が真であるという仮定のもとで示され、次にその逆の仮定のもとで示されるという点で、証明方法は興味深い」と述べています。^{[36] : 173}

平均順序については、^{[23] [37]}

${\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}$

アーノルド・ウォルフィスによるもので、その証明にはIMヴィノグラドフとNMコロボフによる指数和の推定値を利用した。ファン・デル・コープットの方法とヴィノグラドフの方法を組み合わせることで、H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775) は誤差項を次のように改善した。

${\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$

（これは現在、この種の推定値として最もよく知られています）。「Big O」は、括弧内のnの関数の定数倍で制限される量を表します（ n ²と比較すると小さい値です）。

この結果は、ランダムに選ばれた2つの数が互いに素である確率が^{[38] で}あることを証明するために使用できます。6/π ² ⁠

連続値の比率

1950年にソマヤジュルは証明した^{[39] [40]}

${\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}$

1954年にシンツェルと^シェルピンスキーはこれを補強し、集合^が

${\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}}$

は正の実数に稠密である。また、彼らは^[39]集合

${\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}}$

区間 (0,1) では稠密です。

トーティエント数

トーティエント数はオイラーのトーティエント関数の値です。つまり、φ ( n )= mとなるnが少なくとも1つ存在するようなmです。トーティエント数mの価数または重複度は、この方程式の解の数です。^[41]非トーティエント数は、トーティエント数ではない自然数です。1を超えるすべての奇数は、自明に非トーティエントです。また、偶数の非トーティエント数は無限に存在し、^[42]実際、すべての正の整数には、偶数の非トーティエントである倍数が存在します。^[43]

最初のいくつかのトーティエント番号は、シーケンス A002202 を参照してください。 ${\displaystyle 1,2,4,6,8,10,12,16,18,20}$

与えられた限界xまでのトーティエント数の数は

${\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}$

定数C = 0.8178146...の場合。^[44]

重複度に応じて数えると、与えられた限界xまでのトーティエント数の数は

${\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}$

ここで、誤差項Rは最大で⁠x/(log x ) ^k 任意の正のkに対して。 ^[45]

δ < 0.55655の場合には、 mの重複度はm ^δを無限に超えることが知られている。^{[46] [47]}

フォードの定理

フォード（1999）は、任意の整数k ≥ 2に対して、重複度kのトーティエント数mが存在することを証明した。つまり、方程式φ ( n ) = mがちょうどk個の解を持つものである。この結果は、以前にヴァツワフ・シェルピンスキ[ ^48]によって予想されており、シンツェルの仮説H ^[44]の結果として得られたものである。実際、発生する重複度はそれぞれ無限に発生する。^{[44] [47]}

しかし、重複度k = 1となる数mは知られていない。カーマイケルのトーティエント関数予想は、そのようなmは存在しないという主張である。^[49]

完全トーティエント数

完全トーティエント数とは、その反復されたトーティエントの総和に等しい整数です。つまり、トーティエント関数を数nに適用し、その結果得られるトーティエントに再度適用し、これを 1 に達するまで繰り返し、得られた数列を足し合わせます。その合計がnに等しい場合、nは完全トーティエント数です。

応用

円切

『論考^{』 [50] [51]}の最後のセクションで、ガウスは^{[52] 、} φ ( n )が2のべき乗であれば、定規とコンパスを使って正n角形を作図できることを証明しています。nが奇数の素数のべき乗の場合、トーティエントの公式によれば、nが1のべき乗でn - 1が2のべき乗である場合にのみ、そのトーティエントは2のべき乗になります。2のべき乗より1大きい素数はフェルマー素数と呼ばれ、3、5、17、257、65537の5つだけが知られています。フェルマーとガウスはこれらを知っていました。他にもっと素数があるかどうかを証明できた人はいません

このように、正n角形は、 nが異なるフェルマー素数の積と2の任意のべき乗である場合、定規とコンパスで構成できる。そのようなnの最初のいくつかは^[53]である。

2、3、4、5、6、8、10、12、15、16、17、20、24、30、32、34、40、...（OEISのシーケンスA003401）。

等差数列の素数定理

RSA暗号システム

RSAシステムの構築には、大きな素数pとqを選択し、n = pqとk = φ ( n )を計算し、ed ≡ 1 (mod k )となる2つの数eとdを見つけることが含まれます。数nとe（「暗号化鍵」）は公開され、d（「復号鍵」）は非公開にされます

整数m（0 < m < n ）で表されるメッセージは、S = m ^e (mod n )を計算することによって暗号化されます。

これはt = S ^d (mod n )を計算することで復号されます。オイラーの定理を用いると、0 < t < nの場合、t = m であることが示されます。

数値n を効率的に因数分解できる場合、またはnを因数分解せずにφ ( n )を効率的に計算できる場合、RSA システムのセキュリティは危険にさらされます。

未解決問題

レーマーの予想

pが素数ならば、 φ ( p ) = p −1である。1932年、DHレーマーは、 φ ( n )がn −1を割り切るような合成数nが存在するかどうかを問うた。今のところ、知られていない。^[54]

1933年に彼は、もしそのようなnが存在するならば、それは奇数で、平方根を持たず、少なくとも7つの素数で割り切れる（すなわちω ( n ) ≥ 7）必要があることを証明した。1980年にコーエンとハギスは、n > 10 ²⁰とω ( n ) ≥ 14を証明した。^{[55]さらにハギスは、} nを3で割り切れるならばn > 10 ^1937042とω ( n ) ≥ 298848 であることを示した。^{[56] [57]}

カーマイケルの予想

これは、他のすべての数、 、に対して となる性質を持つ数は存在しないことを述べています。上記のフォードの定理を参照してください。 ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle m\neq n}$ ${\displaystyle \varphi (m)\neq \varphi (n)}$

この予想に反例が一つだけあるとすれば、反例は無限に存在するはずであり、最小のものでも10進数では少なくとも100億桁になる。^[41]

リーマン予想

リーマン予想は、不等式が成り立つ場合にのみ真である

${\displaystyle {\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}}$

はオイラー定数であり、最初の120569個の素数の積であるすべての場合に当てはまります。^[58] ${\displaystyle n\geq p_{120569}\#}$ ${\displaystyle \gamma }$ ${\displaystyle p_{120569}\#}$

参照

• カーマイケル関数 (λ)
• デデキントψ関数 (σ)
• 約数関数 (σ)
• ダフィン・シェーファー予想
• フェルマーの小定理の一般化
• 高度に合成された数
• nを法とする整数の乗法群
• ラマヌジャン和
• トーティエント和関数 (𝛷)

注釈

1. 「オイラーのトーティエント関数」。カーンアカデミー。 2016年2月26日閲覧
2. ロング（1972年、85ページ）
3. ペットフレッツォ＆ビルキット（1970年、72ページ）
4. ロング（1972年、162ページ）
5. ペットフレッツォ＆ビルキット（1970年、80ページ）
6. オイラーの定理を参照。
7. L. Euler「新しい方法で証明された算術定理」、Novi commentarii academiae scientiarum imperialis Petropolitanae（サンクトペテルブルク帝国科学アカデミー新紀要）、8（1763年）、74–104。（この作品は1759年10月15日にサンクトペテルブルク科学アカデミーで発表された。同名の作品は1758年6月8日にベルリン科学アカデミーで発表された。オンラインで入手可能：Ferdinand Rudio編、『Leonhardi Euleri Commentationes Arithmeticae』第1巻、『Leonhardi Euleri Opera Omnia』第1巻第2号（ライプツィヒ、ドイツ、BG Teubner、1915年）、531–555ページ。 531 ページで、オイラーは、ファイ関数 φ(N)よりも小さく、互いに素な整数の数として定義します (... aequalis sit multitudini numerorum ipso N minum, qui simul ad eum sint primi, ...)。 ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle N}$
8. サンディファー著、203ページ
9. グラハムら、133ページ、注111
10. L. オイラー、「Speculationes circa quasdam insignes proprietates numerorum」、Acta Academiae Scientarum Imperialis Petropolitinae、vol. 4、(1784)、18 ～ 30 ページ、または Opera Omnia、シリーズ 1、第 4 巻、105 ～ 115 ページ。 (作品は 1775 年 10 月 9 日にサンクトペテルブルクのアカデミーで発表されました)。
11. φ ( n )とϕ ( n )の両方が見られます。これらはギリシャ文字の小文字ファイの2つの形です。
12. ガウス、 Disquisitiones Arithmeticae記事 38
13. カジョリ、フロリアン（1929年）『数学記法の歴史』第2巻、オープンコート出版会社、§409。
14. JJ Sylvester (1879)「特定の三元三次形式方程式について」、American Journal of Mathematics、2  :357-393。Sylvesterは361ページで「トーティエント」という用語を作り出した。
15. "totient".オックスフォード英語辞典（第2版）.オックスフォード大学出版局. 1989年.
16. Weisstein, Eric W. 「トーティエント関数」. mathworld.wolfram.com . 2025年2月9日閲覧。
17. シュラム（2008）
18. ガウス、DA、第39条
19. ガウス、DA アート。 39、芸術。 52-54
20. グラハムら、134-135ページ
21. ハーディ＆ライト 1979年、thm. 328より
22. Dineva（外部参照）、prop. 1
23. ウォルフィス、アーノルド(1963)。Weylsche Exponentialsummen in der neueren Zahlentheorie。 Mathematische Forschungsberichte (ドイツ語)。 Vol. 16. ベルリン: VEB Deutscher Verlag der Wissenschaften。Zbl  0146.06003。
24. Lomadse, G. (1964)、「アーノルド・ウォルフィスの科学的研究」(PDF)、Acta Arithmetica、10 (3): 227– 237、doi :10.4064/aa-10-3-227-237
25. Sitaramachandrarao, R. (1985). 「Landau IIの誤差項について」Rocky Mountain J. Math . 15 (2): 579– 588. doi : 10.1216/RMJ-1985-15-2-579 .
26. Pollack, P. (2023)、「カーマイケルのラムダ関数の分布に関する2つの問題」、Mathematika、69 (4): 1195– 1220、arXiv : 2303.14043、doi : 10.1112/mtk.12222
27. ハーディ＆ライト 1979年、第288頁
28. ハーディ＆ライト 1979年、thm. 309
29. ハーディ＆ライト 1979、§18.4の序文
30. ハーディ＆ライト 1979年、thm. 326
31. ハーディ＆ライト 1979年、thm. 327
32. 実際、チェビシェフの定理（Hardy & Wright 1979、thm.7）とメルテンスの第三定理だけが必要です。
33. ハーディ＆ライト 1979年、thm. 436
34. Rosser, J. Barkley; Schoenfeld, Lowell (1962)の定理15. 「素数の関数の近似式」. Illinois J. Math . 6 (1): 64– 94. doi : 10.1215/ijm/1255631807 .
35. バッハ＆シャリット、thm. 8.8.7
36. Ribenboim (1989). 「素数はどのように分布しているのか？ §IC オイラー関数の値の分布」『素数記録集』（第2版）ニューヨーク：Springer-Verlag. pp.  172– 175. doi :10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5。
37. Sándor, Mitrinović & Crstici (2006) pp.24–25
38. ハーディ＆ライト 1979年、thm. 332
39. リベンボイム、38ページ
40. サンダー、ミトリノヴィッチ、クリスティチ (2006) p.16
41. Guy (2004) p.144
42. サンダー＆クリスティシ (2004) p.230
43. 張明志 (1993). 「非トーティエントについて」.数論ジャーナル. 43 (2): 168– 172. doi : 10.1006/jnth.1993.1014 . ISSN  0022-314X. Zbl  0772.11001.
44. Ford, Kevin (1998). 「トーティエントの分布」. Ramanujan J. 2 ( 1–2 ) : 67–151 . doi :10.1023/A:1009761909132. ISSN  1382-4090. Zbl  0914.11053.ポール・エルデシュ著『解析的および初等数論：数学の伝説へのトリビュート』に再録、数学の発展、第1巻、1998年、doi :10.1007/978-1-4757-4507-8_8、ISBN 978-1-4419-5058-1arXiv：1104.3264、2011年に更新および修正されました
45. サンドール他 (2006) p.22
46. サンドール他 (2006) p.21
47. Guy (2004) p.145
48. サンダー＆クリスティシ (2004) p.229
49. サンダー＆クリスティシ (2004) p.228
50. Gauss, DA. 第7条は336–366条である。
51. ガウスは、 nが特定の条件を満たす場合、 n角形を構成できることを証明した。1837年にピエール・ヴァンツェルは逆のことを証明し、 n角形が構成可能な場合、 nはガウスの条件を満たさなければならないことを明らかにした。
52. ガウス、DA、第366条
53. Gauss, DA, 366条。このリストはDisquisitionesの最後の文である。
54. リベンボイム、36～37ページ。
55. コーエン、グレアム L.;ハギス、ピーター・ジュニア (1980)。 「 φ ( n )がn − 1を割った場合のnの素因数の数について」。ニューアーチ。ウィスクド。 Ⅲシリーズ。28 : 177–185。ISSN 0028-9825  。​ Zbl  0436.10002。
56. ハギス、ピーター・ジュニア (1988)。 「方程式M ·φ( n ) = n − 1について」。ニューアーチ。ウィスクド。 Ⅳシリーズ。6 ( 3): 255–261。ISSN 0028-9825  。Zbl  0668.10006。
57. ガイ（2004）142ページ
58. ケビン・ブローガン（2017年）『リーマン予想の同値類、第1巻：算術的同値類』（初版）ケンブリッジ大学出版局。ISBN 978-1-107-19704-6。系5.35

参考文献

『算術論』はラテン語から英語とドイツ語に翻訳されています。ドイツ語版には、ガウスの数論に関するすべての論文（二次の相互性に関するすべての証明、ガウス和の符号の決定、双二次の相互性に関する考察、そして未発表のノート）が収録されています。

Disquisitionesへの参照は、Gauss, DA, art. nnnの形式になります。

• アブラモウィッツ、M.;ステガン、IA（1964）、数学関数ハンドブック、ニューヨーク：ドーバー出版、ISBN 0-486-61272-4 {{citation}}: ISBN / Date incompatibility (help)24.3.2項を参照。
• エリック・バック著、ジェフリー・シャリット著(1996)、『アルゴリズム的数論（第1巻：効率的なアルゴリズム）』、MITプレス『コンピューティングの基礎シリーズ』、マサチューセッツ州ケンブリッジ：MITプレス、ISBN 0-262-02405-5、Zbl  0873.11070
• ディクソン、レナード・ユージン著、『数論の歴史』第1巻、第5章「オイラー関数、一般化；ファリー級数」、チェルシー出版、1952年
• フォード、ケビン（1999）「φ( x )=  mの解の数」、Annals of Mathematics、150（1）：283–311、doi：10.2307/121103、ISSN  0003-486X、JSTOR  121103、MR  1715326、Zbl  0978.11053。
• ガウス、カール・フリードリヒ（1986年）、Disquisitiones Arithmeticae（第2版、訂正版）、クラーク、アーサー・A.訳、ニューヨーク：シュプリンガー、ISBN 0-387-96254-9
• ガウス、カール・フリードリヒ（1965年）、数論に関する考察（Disquisitiones Arithmeticae & other papers on number theory）（第2版）、Maser, H.訳、ニューヨーク：チェルシー、ISBN 0-8284-0191-8
• グラハム、ロナルド、クヌース、ドナルド、パタシュニック、オーレン(1994)、『具体的数学：コンピュータサイエンスの基礎（第2版）』、マサチューセッツ州レディング：アディソン・ウェスレー、ISBN 0-201-55802-5、Zbl  0836.00001
• ガイ、リチャード・K. (2004)、『数論における未解決問題』、数学の問題集（第3版）、ニューヨーク州ニューヨーク：シュプリンガー・フェアラーク、ISBN 0-387-20860-7、Zbl  1058.11001
• ハーディ、GH、ライト、EM（1979年）、数論入門（第5版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853171-5
• Liu, H.-Q. (2016)、「オイラー関数について」、Proc. Roy. Soc. Edinburgh Sect. A、146 (4): 769– 775、doi :10.1017/S0308210515000682。
• ロング、カルビン・T.（1972年）『初等数論入門（第2版）』レキシントン：DCヒース・アンド・カンパニー、LCCN  77-171950
• ペットフレッツォ、アンソニー・J.; バーキット、ドナルド・R. (1970) 『数論の要素』、エングルウッド・クリフス：プレンティス・ホール、LCCN  77-81766
• リベンボイム、パウロ（1996年）、素数記録の新書（第3版）、ニューヨーク：シュプリンガー、ISBN 0-387-94457-5、Zbl  0856.11001
• サンディファー、チャールズ（2007年）、『レオンハルト・オイラーの初期数学』、MAA、ISBN 978-0-88385-559-1
• ヨージェフ・シャーンドル、ドラゴスラフ・S・ミトリノヴィッチ、ボリスラフ・クリストチ編 (2006) 『数論ハンドブック I』 ドルドレヒト：シュプリンガー出版社、 9～ 36ページ 、 ISBN 1-4020-4215-9、Zbl  1151.11300
• ヨージェフ・シャーンドル、ボリスラフ・クリストチ (2004).数論ハンドブック II . ドルドレヒト: クルーワー・アカデミック. pp. 179–327. ISBN 1-4020-2546-7. Zbl  1079.11001
• シュラム、ヴォルフガング（2008）「最大公約数関数のフーリエ変換」、電子組合せ数論ジャーナル、A50（8（1））。

外部リンク

• 「トーティエント関数」、数学百科事典、EMS Press、2001年 [1994]
• オイラーのファイ関数と中国剰余定理 — φ(n) が乗法的であることの証明 2021年2月28日アーカイブ、Wayback Machine
• JavaScript によるオイラーのトーティエント関数計算機 — 最大 20 桁
• ディネヴァ、ローシカ、オイラー・トーティエント、メビウス、そして約数関数 2021年1月16日アーカイブ、Wayback Machineにて
• プリテージ、ルーミス、ポルヒルによるオイラーのファイ関数のまとめ

Retrieved from "https://en.wikipedia.org/w/index.php?title=Euler%27s_totient_function&oldid=1322447716"