1. 高校数学の美しい物語
  2. オイラーのファイ関数のイメージ

オイラーのファイ関数のイメージ

更新日時 2021/03/07
オイラーのファイ関数
  • 自然数 nn に対して,11 から nn までの自然数の中で nn と互いに素なものの数を ϕ(n)\phi(n) と書き,オイラーの ϕ\phi 関数と呼ぶことがある。

  • ϕ\phi 関数は ϕ(n)=ni=1k(11pi)\phi(n)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)という式で計算できる。ただし,pip_inn の素因数。

オイラーの ϕ\phi 関数(トーシェント関数)についての話です。

目次
  • オイラーのファイ関数の計算例

  • オイラーのファイ関数のイメージ

  • ファイ関数の公式の証明

  • ファイ関数の和

  • オイラーの定理

オイラーのファイ関数の計算例

n=p1e1p2e2pkekn=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解できるとき,

ϕ(n)=ni=1k(11pi)\phi(n)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)

となります。この公式を使えば,「自然数 nn と互いに素な nn 以下の自然数の個数」を高速で求めることができます。

1212 と互いに素な 1212 以下の自然数の個数は,

12=22312=2^2\cdot 3 より,12(112)(113)=412\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)=4 個。

実際に全列挙すれば,1,5,7,111, 5, 7, 1144 つで正しいことが確認できる。

180180 と互いに素な 180180 以下の自然数の個数は,

180=22325180=2^2\cdot 3^2\cdot 5 より,

180(112)(113)(115)=48180\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)\left(1-\dfrac{1}{5}\right)=48

実際に全列挙するのは疲れるのでファイ関数の公式が役に立った。

この手の問題は入試問題でたまに出題されます。数学オリンピックの整数問題でも役に立つかもしれません。

オイラーのファイ関数のイメージ

厳密な証明の前に,まずはファイ関数の公式のイメージです。

n=p1e1p2e2pkekn=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解される場合について,11 から nn までの自然数の中で nn と互いに素なものがいくつあるか考えます。

nn と互いに素」⇔「p1p_1 と互いに素,かつ p2p_2 と互いに素,かつ \cdots かつ pkp_k と互いに素」という素数の性質を利用します。

大雑把な説明

オイラーのファイ関数

まず,11 から nn の中で p1p_1 と互いに素なものの割合は,p11p1\dfrac{p_1-1}{p_1}

生き残った n(11p1)n\left(1-\dfrac{1}{p_1}\right) 個の中で p2p_2 と互いに素なものの割合は,p21p2(1)\dfrac{p_2-1}{p_2}\cdots(1)

さらに生き残った n(11p1)(11p2)n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right) 個の中で p3p_3 と互いに素なものの割合は,p31p3\dfrac{p_3-1}{p_3}

これを繰り返すとオイラーのファイ関数の公式を得る。

(1)(1) の部分が厳密ではないです。

ファイ関数の公式の証明

公式のイメージがわかったところで,ϕ(n)=ni=1k(11pi)\phi(n)=n\displaystyle\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right) を証明してみましょう。

3段階にわけて証明します。まずは,n=pkn=p^kpp は素数で kk は正の整数)と表される場合を考えます。

証明(第一段階)

n=pkn=p^k の場合,ϕ(n)\phi(n)nn 以下の正の整数で pp の倍数でないものの数なので ϕ(n)=pk(11p)\phi(n)=p^k\left(1-\dfrac{1}{p}\right) となる。

次は一番難しい第2段階です。オイラーのファイ関数の乗法性を証明します。

証明(第二段階)

m,nm,n が互いに素なとき,ϕ(mn)=ϕ(m)ϕ(n)\phi(mn)=\phi(m)\phi(n) であることを示す。

mnmn 以下の正の整数を mm で割ったあまりごとで mm 個の集合にわける。余りが rr である集合を Ar={r,m+r,2m+r,,(n1)m+r}A_r=\{r,m+r,2m+r,\dots,(n-1)m+r\} とおく。ArA_r ごとに「mnmn と互いに素」なものの数を数える。

  • rrmm が互いに素でない場合。rrmm の最大公約数を dd とおくと,ArA_r に属する整数はすべて dd の倍数なので mnmn と互いに素なものはない。
  • rrmm が互いに素な場合。mnmn と互いに素なものの個数は ϕ(n)\phi(n) 個(なぜなら ArA_r の要素はすべて mm と互いに素であり,さらに ArA_r の要素を nn で割った余りはすべて異なり(→補足)00 から n1n-1 を尽くすので ϕ(n)\phi(n) 個が nn と互いに素)。

後者のようなグループは ϕ(m)\phi(m) 個あるので,結局 ϕ(mn)=ϕ(m)ϕ(n)\phi(mn)=\phi(m)\phi(n)

補足:im+rim+rjm+rjm+rnn で割った余りが同じと仮定すると (ij)m(i-j)mnn の倍数となり矛盾。

最後は簡単です。

証明(第三段階)

n=p1e1p2e2pkekn=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} と素因数分解されるとき,乗法性を繰り返し使うと

ϕ(n)=ϕ(p1e1)ϕ(p2e2)ϕ(pkek)\phi(n)=\phi(p_1^{e_1})\phi(p_2^{e_2})\cdots\phi(p_k^{e_k})

ここで右辺の各項に第一段階の結果を使うと,求めたい公式を得る。

ファイ関数の和

dnϕ(d)=n\displaystyle\sum_{d\mid n}\phi(d)=n

dn\displaystyle\sum_{d\mid n} とは,nn の全ての約数 dd について和を取るという意味です。例えば n=6n=6 とすると,

ϕ(1)+ϕ(2)+ϕ(3)+ϕ(6)=1+1+2+2=6\phi(1)+\phi(2)+\phi(3)+\phi(6)=1+1+2+2=6

となります。

証明

A={1,2,,n}A=\{1,2,\cdots,n\} とする。 aAa\in Ann の約数 dd について,

aann との最大公約数が dd    \iffad\dfrac{a}{d} が整数かつ ad\dfrac{a}{d}nd\dfrac{n}{d} は互いに素    \iffad\dfrac{a}{d}1,2,,nd1,2,\cdots,\dfrac{n}{d} のいずれか,かつ ad\dfrac{a}{d}nd\dfrac{n}{d} は互いに素

一番最後の条件を満たす aa の個数は,ϕ(nd)\phi\left(\dfrac{n}{d}\right) である。

よって,AA の要素を nn との最大公約数 dd でグループ分けすることにより,

n=dnϕ(nd)n=\displaystyle\sum_{d\mid n}\phi\left(\dfrac{n}{d}\right)

が分かる。 ddnn の約数     nd\iff \dfrac{n}{d}nn の約数であることに注意すると目標の式を得る。

実は,この性質とメビウスの反転公式を使って冒頭の公式をきちんと証明することもできます。→メビウスの反転公式の証明と応用

オイラーの定理

ファイ関数に関連する定理として以下の「オイラーの定理」が知られています。

オイラーの定理

nn を自然数,aann と互いに素な正の整数としたとき,aϕ(n)1(modn)a^{\phi(n)}\equiv 1 \pmod{n}

nn が素数の場合はフェルマーの小定理になります。フェルマーの小定理の証明と例題

証明

11 以上 nn 以下で aa と互いに素な整数を {m1,m2,,mϕ(n)}\{m_1,m_2,\dots,m_{\phi(n)}\} とおく。

nn で割った余りで見ると, {am1,am2,,amϕ(n)}\{am_1,am_2,\dots,am_{\phi(n)}\} という集合は {m1,m2,,mϕ(n)}\{m_1,m_2,\dots,m_{\phi(n)}\} と一致する(→補足)。よって,すべて掛け算すると

aϕ(n)m1m2mϕ(n)m1m2mϕ(n)(modn)a^{\phi(n)}m_1m_2\cdots m_{\phi(n)}\equiv m_1m_2\cdots m_{\phi(n)} \pmod{n}

ここで,各 mim_inn と互いに素なので,合同式の両辺を m1m2mϕ(n)m_1m_2\cdots m_{\phi(n)} で割って

aϕ(n)1(modn)a^{\phi(n)}\equiv 1\pmod{n}

補足:以下の2つの主張よりわかります。

  • amiam_iamjam_jnn で割った余りは異なる(同じだと仮定すると a(mimj)a(m_i-m_j)nn の倍数になり矛盾)。
  • amiam_inn と互いに素

オイラーのファイ関数の公式は徐々にふるい落とすイメージです。

Tag:オイラーの公式・定理まとめ

人気記事
  1. 高校数学の美しい物語
  2. オイラーのファイ関数のイメージ