オイラーのφ関数

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

\varphi (n)=\textstyle \sum \limits _{1\leq m\leq n \atop (m,n)=1}1

と表すこともできる（ここで $(m, n)$ は $m$ と $n$ の最大公約数を表す）。慣例的にギリシャ文字の $φ$ （あるいは $\phi$ ）で表記されるため、オイラーの $φ$ 関数（ファイかんすう、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$ から $p k$ の中で $p$ を因子として含むもの、すなわち $p$ の倍数は $p k - 1$ 個あるから、次が成立することが確かめられる。

定理 ― $\varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)$

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

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

n=\textstyle \prod \limits _{k=1}^{d}{p_{k}}^{e_{k}}

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

\varphi (n)=\textstyle \prod \limits _{k=1}^{d}\left({p_{k}}^{e_{k}}-{p_{k}}^{e_{k}-1}\right)=n\prod \limits _{k=1}^{d}\left(1-{\dfrac {1}{p_{k}}}\right)

自然数 $n, d$ で $d$ が $n$ を割り切るものとすると、 $1$ から $n$ までの自然数のうち $n$ との最大公約数が $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}n/d$ であるものの数は $φ (d)$ 個である。特に、 $1$ から $n$ までの自然数は $n$ との最大公約数によって類別されるから、 $d$ が $n$ の正の約数全てをわたる和に関して等式

\textstyle \sum \limits _{d\mid n}\varphi (d)=n

が成り立つ（ $d | n$ は $d$ が $n$ を割り切るの意）。

$G$ を位数 $n$ の巡回群とすれば、 $n$ の約数 $d$ に対して $G$ の位数 $d$ の元は $φ (d)$ 個存在する。特に、巡回群 $G$ の生成元になりうる元は $φ (n)$ 個存在する。

自然数 $a, m (1 \leq a < m)$ とするとき、剰余環 $Z / m Z$ に属する剰余類 $a + m Z$ が既約、つまり $Z / m Z$ の単数である必要十分な条件は代表元 $a$ が $m$ と互いに素であることであるから、既約剰余類の数は $φ (m)$ に等しい。同じことだが、群 $G$ の位数を $# G$ , 環 $R$ の単数群を $R \times$ で表すとき、等式

\varphi (m)=\#(\mathbb {Z} /m\mathbb {Z} )^{\times }

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

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

\varphi (n)\geq e^{-\gamma }{\cfrac {n}{\log \log n+{\cfrac {2.50637}{e^{\gamma }\log \log n}}}}

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

\varphi (n)>n^{1-\varepsilon }

が十分大きな $n$ に対して成り立つ^[4]。簡明な下界として $\varphi (n)\geq {\sqrt {\frac {n}{2}}}$ がある^[5]。

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

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

が成り立つ。

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

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

脚注

[脚注の使い方]

^ 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
^ 英語のtotientはラテン語のtotに由来する^[1]。
^ オンライン整数列大辞典の数列 A000010
^ M. B. Nathanson (1996). Additive Number Theory: The Classic Bases. Springer. p. 315. ISBN 0-387-94656-X
^ “Is the Euler phi function bounded below?”. Mathematics Stack Exchange. 2020年3月26日閲覧。

外部リンク

『オイラーのファイ関数のイメージと性質』 - 高校数学の美しい物語
Weisstein, Eric W. "Totient Function". mathworld.wolfram.com (英語).
Kevin Ford, The number of solutions of φ(x)=m, Ann. of Math. 150(1999), 283--311.
D. Miyata & M. Yamashita, Note on derived logarithmic functions of Euler's functions

[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

[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日閲覧。

[2]

[3]

[4]

[5]

[1]

例

性質

脚注

関連項目

外部リンク