オイラーのトーシェント関数

数論において、オイラーのトーシェント関数は、与えられた整数までの正の整数を数える。${\displaystyle n}$比較的優良な${\displaystyle n}$ギリシャ文字のファイを使って次のように書きます。${\displaystyle \varphi (n)}$または${\displaystyle \phi (n)}$、オイラーのファイ関数とも呼ばれる。言い換えれば、それは整数の数である。${\displaystyle k}$範囲内${\displaystyle 1\leq k\leq n}$最大公約数​${\displaystyle \gcd(n,k)}$1に等しい。^{[ 2 ] [ 3 ]}整数${\displaystyle k}$この形式のものは、時として全格と呼ばれる。${\displaystyle n}$。

例えば、${\displaystyle n=9}$1、2、4、5、7、8の6つの数字です。これらはすべて9と互いに素ですが、この範囲の他の3つの数字、3、6、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}$1からまでの範囲で唯一の整数${\displaystyle n}$は1そのものであり、${\displaystyle \gcd(1,1)=1}$。

オイラーのトーシェント関数は乗法関数であり、2 つの数値が${\displaystyle m}$そして${\displaystyle n}$相対的に素数である場合、${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$^{[ 4 ] [ 5 ]} この関数は、nを法とする整数の乗法群の位数(環の単位群)を与えます。${\displaystyle \mathbb {Z} /n\mathbb {Z} }$) ^{[ 6 ]}また、 RSA暗号化システムを定義するためにも使用されます。

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

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

共変量​${\displaystyle n}$は次のように定義される。${\displaystyle n-\varphi (n)}$。以下の正の整数の数を数えます。${\displaystyle n}$少なくとも1つの素因数を持つ${\displaystyle n}$。

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

最初の100個の値（OEISのシーケンスA000010）を以下の表とグラフに示します。

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

これは、aとnが互いに素である場合、

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

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

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

RSA暗号システムは、次の定理に基づいています。すなわち、eが（公開）暗号化指数である関数a ↦ a ^e mod nの逆関数は、 dが（秘密）復号指数である関数b ↦ b ^d mod nであり、eの法φ（n）の乗法逆関数であることを意味します。したがって、 nの因数分解を知らずにφ（n）を計算する難しさは、dを計算する難しさと同じです。これはRSA問題として知られており、 nを因数分解することで解決できます。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 ≥ 3の場合、 φ ( n )は偶数です。さらに、 n がr個の異なる奇素因数を持つ場合、 2 ^r | φ ( n )
• 任意のa > 1およびn > 6に対して4 ∤ nとなるようなl ≥ 2 nが存在し、l | φ ( a ⁿ − 1)となる。
• ${\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 {\varphi (k)}{k^{2}}}={\frac {6}{\pi ^{2}}}\log n+{\frac {6\gamma }{\pi ^{2}}}-{\frac {\zeta '(2)}{\zeta (2)^{2}}}+O\left({\frac {\log n}{n}}\right)}$^{[ 25 ]}
• ${\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)}$ ^{[ 26 ]}
• ${\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)}$ ^{[ 26 ]}（ここでγオイラー・マスケローニ定数である）。

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

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

左辺が収束する${\displaystyle \Re (s)>2}$。

ランベルト級数生成関数は^{[ 29 ]}

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

これは| q | < 1の場合に収束する。

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

ハーディとライトの言葉を借りれば、 φ ( n )の次数は「常に『ほぼn』である」^{[ 30 ]。}

第一に^{[ 31 ]}

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

しかし、nが無限大に近づくと、^{[ 32 ]}すべてのδ > 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...となります。

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

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

実際、それ以上のことが言える。^{[ 35 ] [ 36 ] [ 37 ]}

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

平均次数については、^{[ 23 ] [ 38 ]}

${\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. リュー (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)}$

（これは現在、このタイプの最もよく知られた推定値です）。「ビッグオー」は、括弧内のnの関数の定数倍によって制限される量を表します（これはn ²に比べて小さいです）。

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

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

${\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年にシンツェルとシェルピンスキーはこれを強化して、集合が^{[ 40 ] [ 41 ]であることを証明した。}

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

正の実数で密である。彼らはまた、集合が^{[ 40 ]であることを証明した。}

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

区間(0,1)において密である。

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

最初のいくつかのトーシェント数は${\displaystyle 1,2,4,6,8,10,12,16,18,20}$配列 A002202を参照してください。

与えられた限界xまでのトーシェント数の数は

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

定数C = 0.8178146... . ^{[ 45 ]}

重複度に従って数えると、与えられた限界xまでのトーシェント数の数は

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

ここで、誤差項Rは任意の正のkに対して最大で⁠ x / (log x ) ^k ⁠ のオーダーである。^{[ 46 ]}

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

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

• 「トーシェント関数」、数学百科事典、EMS Press、2001年 [1994年]
• オイラーのファイ関数と中国剰余定理 ― φ ( n )が乗法的であることの証明 2021年2月28日にWayback Machineにアーカイブされました
• JavaScriptで記述されたオイラーのトーシェント関数計算機 ― 最大20桁まで対応
• ディネヴァ、ロシカ、「オイラーのトーシェント関数、メビウスの輪、および除数関数」 2021年1月16日にWayback Machineにアーカイブされました
• Plytage、Loomis、Polhill著「オイラーのファイ関数の要約」