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

この記事では、対数について専門的な数学表記法を使用しています。log

(x)

に添え字の底がない場合、すべて自然対数（一般的に

ln(x)

または

log e (x)

と表記される）として解釈されます。

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

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

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

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

歴史、用語、表記法

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

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

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

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

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

オイラーの積の公式

それは次のように述べています

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

ここで、積は $n$ を割り切る異なる素数について求められます。

同等の定式化は

\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),

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

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

ファイは乗法関数である

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

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

$p$ $が$ 素数で $k\geq1$ ならば、

\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 2, ..., p k$ のみであり、 $gcd(p k, m) > 1$ となる唯一の条件は、 $mが$ $p$ の倍数、つまり $m \in {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$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $r$ が素数で各 $k$ $i$ $\geq 1 と$ なる唯一の式が存在する。（ $n$ $= 1$ の場合は空積となる。） $φ$ の乗法性および $φ$ $($ $p$ $k$ $)$ の公式を繰り返すと、 $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},$

{\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}}

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

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

例

\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 です。

代替式では整数のみを使用します。 $\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]

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

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

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

この式の実部は

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

例えば、とを用いると、オイラー積や約数の和の公式とは異なり、この公式では $nの因数を知る必要はありません。しかし、$ $nと$ $n$ 未満のすべての正の整数の最大公約数を計算する必要があり、これは因数分解には十分です。 $\cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}$ $\cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}$ ${\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]}によって確立された性質は、

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

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

{\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}}.

もっと簡単に言うと、

{\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にも当てはまります。

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

\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\geq2$ $の$ 各素数に対して定義される乗法関数である。この式は積の式からを乗じて次のように導くこともできる。 $\mu (p)=-1$ $\mu (p^{k})=0$ ${\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})}$ ${\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}$

例: ${\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が$ 素数の場合にのみ達成されます。単純な下限はですが、これはかなり緩いものです。実際、グラフの下限は $⁠に比例します。$ $\varphi (n)\geq {\sqrt {n/2}}$ $n / ログログ n ⁠$ .^[21]

オイラーの定理

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

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

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

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

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

その他の式

$a\mid b\implies \varphi (a)\mid \varphi (b)$
$m\mid \varphi (a^{m}-1)$
$\varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)$
- 特に：
$\varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}$
$\varphi \left(n^{m}\right)=n^{m-1}\varphi (n)$
$\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 \geq 3 の$ とき偶数となる。
さらに、 $n が$ $r 個$ の異なる奇数の素因数を持つ $とき、 2 r | φ (n)$
$4 ∤$ $n$ となるような任意の $a > 1$ かつ $n > 6$ に対して、 $l$ $|$ $φ$ $($ $a$ $n$ $- 1)$ となる $l$ $\geq 2$ $n が$ 存在する。
${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$

ここで、

rad(n)は

n

の根号（

n

を割り切るすべての異なる素数の積）です。

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ ^[22]
$\sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1$
$\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]で引用）
$\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）]
$\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]
$\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]
$\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.ケサヴァ・メノンは

\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]は重要な帰結をもたらす。例えば、任意の整数についてを法とする等差数列におけるの値が一様分布することは不可能である。 $\varphi (n)$ $q$ $q>1$

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

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

生成関数

$φ$ $($ $n$ $)$ のディリクレ級数はリーマンゼータ関数を用いて次のように表される: ^[27]

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

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

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

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

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

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

成長率

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

最初^[30]

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

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

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

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

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

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

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

また、^[21]

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

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

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

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

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

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

そして

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

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

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

\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) は誤差項を次のように改善した。

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

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

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

連続値の比率

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

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

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

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

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

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

トーティエント数

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

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

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

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

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

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

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

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

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

フォードの定理

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

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

完全トーティエント数

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

アプリケーション

円切術

ガウスは『論考』^[50]^[51]の最後の部分で、 $φ$ $($ $n$ $)$ が 2 のべき乗であれば定規とコンパスで正 $n$ 角形を作図できることを証明している^[52]。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$ $\equiv 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) \geq 7$ ）必要があることを証明した。1980年にコーエンとハギスは、 $n > 10 20$ と $ω (n) \geq 14$ を証明した。^{[55]さらにハギスは、} $nを$ 3で割り切れるならば $n > 10 1937042$ と $ω (n) \geq 298848 で$ あることを示した。^[56]^[57]

カーマイケルの予想

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

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

リーマン予想

リーマン予想は不等式が成り立つときのみ真である。

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

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

参照

注記

^ 「オイラーのトーティエント関数」カーンアカデミー。 2016年2月26日閲覧。
^ ロング（1972年、85ページ）
^ ペットフレッツォ＆ビルキット（1970年、72ページ）
^ ロング（1972年、162ページ）
^ ペットフレッツォ＆ビルキット（1970年、80ページ）
^ オイラーの定理を参照。
^ 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, ...)より小さく、互いに素な整数の数として定義します。 $n$ $N$ $N$
^ サンディファー著、203ページ
^ グラハムら、133ページ、注111
^ 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 日にサンクトペテルブルクのアカデミーで発表されました)。
^文献には $φ$ $($ $n$ $)$ と $ϕ$ $($ $n$ $)$ の両方が見られます。これらはギリシャ文字の小文字ファイの2つの形です。
^ ガウス、Disquisitiones Arithmeticae記事 38
^ カジョリ、フロリアン（1929年）『数学記法の歴史』第2巻、オープンコート出版会社、§409。
^ JJ Sylvester (1879)「特定の三元三次形式方程式について」、American Journal of Mathematics、2 :357-393。Sylvesterは361ページで「トーティエント」という用語を作り出した。
^ "totient".オックスフォード英語辞典（第2版）.オックスフォード大学出版局. 1989年.
^ Weisstein, Eric W. 「トーティエント関数」. mathworld.wolfram.com . 2025年2月9日閲覧。
^ シュラム（2008）
^ ガウス、DA、第39条
^ ガウス、DA アート。 39、芸術。 52-54
^ グラハムら、134-135ページ
^ ハーディ＆ライト 1979年、thm. 328より
^ Dineva（外部参照）、prop. 1
^ abc ウォルフィス、アーノルド(1963)。Weylsche Exponentialsummen in der neueren Zahlentheorie。 Mathematische Forschungsberichte (ドイツ語)。 Vol. 16. ベルリン: VEB Deutscher Verlag der Wissenschaften。Zbl 0146.06003。
^ Lomadse, G. (1964)、「アーノルド・ウォルフィスの科学的研究」(PDF)、Acta Arithmetica、10 (3): 227– 237、doi :10.4064/aa-10-3-227-237
^ ab Sitaramachandrarao, R. (1985). 「Landau IIの誤差項について」Rocky Mountain J. Math . 15 (2): 579– 588. doi : 10.1216/RMJ-1985-15-2-579 .
^ Pollack, P. (2023)、「カーマイケルのラムダ関数の分布に関する2つの問題」、Mathematika、69 (4): 1195– 1220、arXiv : 2303.14043、doi : 10.1112/mtk.12222
^ ハーディ＆ライト 1979年、thm. 288
^ ハーディ＆ライト 1979年、thm. 309
^ ハーディ＆ライト 1979、§18.4の序文
^ ハーディ＆ライト 1979年、thm. 326
^ ハーディ＆ライト 1979年、thm. 327
^ 実際、チェビシェフの定理（Hardy & Wright 1979、thm.7）とメルテンスの第三定理だけが必要です。
^ ハーディ＆ライト 1979年、thm. 436
^ Rosser, J. Barkley; Schoenfeld, Lowell (1962)の定理15. 「素数の関数の近似式」. Illinois J. Math . 6 (1): 64– 94. doi : 10.1215/ijm/1255631807 .
^ バッハ＆シャリット、thm. 8.8.7
^ ab Ribenboim (1989). 「素数はどのように分布しているのか？ §IC オイラー関数の値の分布」『素数記録集』（第2版）ニューヨーク：Springer-Verlag. pp. 172– 175. doi :10.1007/978-1-4684-0507-1_5. ISBN 978-1-4684-0509-5。
^ サンダー、ミトリノヴィッチ、クリスティチ (2006) pp.24–25
^ ハーディ＆ライト 1979年、thm. 332
^ abc リベンボイム、38ページ
^ ab サンダー、ミトリノヴィッチ、クリスティチ (2006) p.16
^ ab Guy (2004) p.144
^ サンダー＆クリスティシ (2004) p.230
^ 張明志 (1993). 「非トーティエントについて」.数論ジャーナル. 43 (2): 168– 172. doi : 10.1006/jnth.1993.1014 . ISSN 0022-314X. Zbl 0772.11001.
^ abc 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-1 arXiv：1104.3264、2011年に更新および修正されました。
^ サンドール他 (2006) p.22
^ サンドール他 (2006) p.21
^ ab Guy (2004) p.145
^ サンダー＆クリスティシ (2004) p.229
^ サンダー＆クリスティシ (2004) p.228
^ Gauss, DA. 第7条は336–366条である。
^ ガウスは、 $nが$ 特定の条件を満たす場合、 $n$ 角形を構成できることを証明した。1837年にピエール・ヴァンツェルは逆のことを証明し、 $n$ 角形が構成可能な場合、 $n$ はガウスの条件を満たさなければならないことを明らかにした。
^ ガウス、DA、第366条
^ Gauss, DA, 366条。このリストはDisquisitionesの最後の文である。
^ リベンボイム、36～37ページ。
^ コーエン、グレアム L.;ハギス、ピーター・ジュニア (1980)。「 $φ$ $($ $n$ $)が$ $n$ $- 1$ を割った場合の $n$ の素因数の数について」。ニューアーチ。ウィスクド。 Ⅲシリーズ。28 : 177–185。ISSN 0028-9825 。 Zbl 0436.10002。
^ ハギス、ピーター・ジュニア (1988). 「方程式 $M$ $\cdotφ($ $n$ $) =$ $n$ $- 1$ について」。ニューアーチ。ウィスクド。 Ⅳシリーズ。6 ( 3): 255–261。ISSN 0028-9825 。Zbl 0668.10006。
^ ガイ（2004）142ページ
^ ケビン・ブローガン（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年）、Untersuchungen uber hohere Arithmetik（Disquisitiones Arithmeticae & other papers on number theory）（第2版）、Maser, H.訳、ニューヨーク：チェルシー、ISBN 0-8284-0191-8
グラハム、ロナルド、クヌース、ドナルド、パタシュニック、オーレン（1994年）、Concrete Mathematics : a foundation for computer science（第2版）、Reading、MA：Addison-Wesley、ISBN 0-201-55802-5、Zbl 0836.00001
ガイ、リチャード・K.（2004）、数論における未解決問題、数学の問題集（第3版）、ニューヨーク、NY：シュプリンガー・フェアラーク、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、ドルドレヒト: Springer-Verlag 、 9 ～ 36ページ、 ISBN 1-4020-4215-9、Zbl 1151.11300
サンダー、ジョゼフ。クリスティチ、ボリスラフ (2004)。整数論ハンドブック II．ドルドレヒト: クルーワー学者。 179–327ページ。ISBN 1-4020-2546-7. Zbl 1079.11001。
シュラム、ヴォルフガング（2008）「最大公約数関数のフーリエ変換」、電子組合せ数論ジャーナル、A50（8（1））。

外部リンク

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