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

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

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

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

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

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

nの係数はn − φ ( n )と定義されます。これは、 nと少なくとも 1 つの共通の素因数を持つ、n以下の正の整数の数を数えます。

φ ( 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以下のそのような倍数がp ^{k − 1}個ある場合です。したがって、他の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で評価される。[ ^16]

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

ここで、k ∈ {1, ..., n }に対してx _k = 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}}}$$

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

${\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 )元によって生成されるので、式は次式に従う。^{[18]同様に、この式は}n乗根の乗法群と原始d乗根に同じ議論を適用することによって導くことができる。

この式は初等算術からも導くことができる。^[19]例えば、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の分数はすべて正の分数です。け/d⁠ ≤ 1 で、分母が約数d = 1, 2, 4, 5, 10, 20である分数。分母が 20 である分数は、分子が 20 と互いに素である分数、すなわち⁠1/20⁠、⁠3/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 ) が以下の表とグラフに示されています。

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

これは、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)}}}$ ^[21]
• ${\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)}$ （^[22]は[23]で引用）
• ${\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)}$ ^[22]
• ${\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)}$ ^[24]
• ${\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)}$ ^[24]

  （ここでγはオイラー・マスケロニ定数である）。

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の約数の数です。

次の性質は「民間伝承」の一部である（つまり、具体的な結果としては明らかに公表されていない：^[25]この論文の序文では「古くから知られていた」と述べられている）が、重要な結果をもたらす。例えば、任意の整数 について を法とする等差数列におけるの値の一様分布を排除する。 ${\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 )のディリクレ級数はリーマンゼータ関数を用いて次のように表される: ^[26]

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

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

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

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

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

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

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

まず^[29]

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

しかしnが無限大に近づくと、^[30] δ > 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 の場合に真であることが証明されています。

また、^[20]

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

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

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

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

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

${\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番目の不等式はジャン＝ルイ・ニコラによって示された。リーベンボイムは「不等式はまずリーマン予想が正しいという仮定のもとで示され、次にその逆の仮定のもとで示されるという点で証明方法は興味深い」と述べている。^{[35] : 173}

平均順位は^{[22] [36]}

${\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.・リウ（オイラー関数について。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つの数が互いに素である確率が次の式で表されることを証明するために使用できる^[37]。6/π ²⁠ .

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

${\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年にシンツェルとシェルピンスキーはこれを補強し、^{[38] [39]}集合が

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

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

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

区間(0,1)では密である。

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

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

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

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

重複度に応じて数えると、与えられた限界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に対して。 ^[44]

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

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

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

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

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

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

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

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が存在するかどうかを尋ねた。そのような数はまだ知られていない。^[53]

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

これは、他のすべての数m、m ≠ n、φ ( m ) ≠ φ ( n )という性質を持つ数n は存在しないことを述べています。上記のフォードの定理を参照してください。

本稿で述べたように、この予想に対する反例が1つしかない場合、反例は無限に存在するはずであり、最小のものでも10進数で少なくとも100億桁ある。^[40]

リーマン予想は不等式が成り立つ場合にのみ成立する。

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

はn ≥ p ₁₂₀₅₆₉ # のすべてに対して真であり、γはオイラー定数、p ₁₂₀₅₆₉ # は最初の 120569個の素数の積である。^[57]

• カーマイケル関数 (λ)
• デデキント psi 関数 (𝜓)
• 除数関数（σ）

• ダフィン・シェーファー予想
• フェルマーの小定理の一般化
• 高度に合成された数

• nを法とする整数の乗法群
• ラマヌジャン和
• トーティエント総和関数 (𝛷)

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