オイラーのφ関数

オイラーのトーシェント関数（オイラーのトーシェントかんすう、英: Euler's totient function）とは、正の整数 n に対して、 n と互いに素である 1 以上 n 以下の自然数の個数 φ(n) を与える数論的関数 φ である。これは φ ( n ) = ∑ 1 ≤ m ≤ n ( m , n ) = 1 1 {\displaystyle \varphi (n)=\textstyle \sum \limits _{1\leq m\leq n \atop (m,n)=1}1} と表すこともできる（ここで (m, n) は m と n の最大公約数を表す）。慣例的にギリシャ文字の φ（あるいは ϕ {\displaystyle \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 までの値は以下の通りである。 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 から pk の中で p を因子として含むもの、すなわち p の倍数は pk − 1 個あるから、次が成立することが確かめられる。 定理 ―  φ ( p k ) = p k − p k − 1 = p k − 1 ( p − 1 ) = p k ( 1 − 1 p ) {\displaystyle \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 における値を知ることができる。実際に、pk はどの二つも相異なる素因数であるとして、以下のように φ(n) を計算することができる。 定理 ― n の素因数分解が次のように n = ∏ k = 1 d p k e k {\displaystyle n=\textstyle \prod \limits _{k=1}^{d}{p_{k}}^{e_{k}}} と与えられているならば、 φ ( n ) = ∏ k = 1 d ( p k e k − p k e k − 1 ) = n ∏ k = 1 d ( 1 − 1 p k ) {\displaystyle \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 との最大公約数が n/d であるものの数は φ(d) 個である。特に、1 から n までの自然数は n との最大公約数によって類別されるから、d が n の正の約数全てをわたる和に関して等式 ∑ d ∣ n φ ( d ) = n {\displaystyle \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 ≤ a < m) とするとき、剰余環 Z/mZ に属する剰余類 a + mZ が既約、つまり Z/mZ の単数である必要十分な条件は代表元 a が m と互いに素であることであるから、既約剰余類の数は φ(m) に等しい。同じことだが、群 G の位数を #G, 環 R の単数群を R× で表すとき、等式 φ ( m ) = # ( Z / m Z ) × {\displaystyle \varphi (m)=\#(\mathbb {Z} /m\mathbb {Z} )^{\times }} が成立する。これは特に、オイラーの定理 a φ ( m ) ≡ 1 ( mod m ) {\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}} の成立を意味する。また同じ式から、1 の m 乗根で原始的であるものの一つを ζ とし、既約剰余類群 (Z/mZ)× を円分拡大 Q(ζ)/Q のガロア群と見れば φ(m) が円の m 分多項式の次数に等しいことも従う。 n > 1 ならば φ(n) < n である。また、n > 3 ならば φ ( n ) ≥ e − γ n log ⁡ log ⁡ n + 2.50637 e γ log ⁡ log ⁡ n {\displaystyle \varphi (n)\geq e^{-\gamma }{\cfrac {n}{\log \log n+{\cfrac {2.50637}{e^{\gamma }\log \log n}}}}} が成り立つ。ここで γ はオイラー定数である。もし n ≠ 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 ⋅ 17 ⋅ 19 ⋅ 23 であれば 2.50637 のかわりに 2.5 とおくことができる。一般に任意の ε > 0 に対して φ ( n ) > n 1 − ε {\displaystyle \varphi (n)>n^{1-\varepsilon }} が十分大きな n に対して成り立つ。簡明な下界として φ ( n ) ≥ n 2 {\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}} がある。 σ(n) を約数関数とすると、n > 1 において、 6 n 2 π 2 < φ ( n ) σ ( n ) < n 2 {\displaystyle {\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 は無数に存在することが知られている。