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

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

更新日時 2021/03/07

オイラーのファイ関数:

自然数 nn に対して,11 から nn までの自然数の中で nn と互いに素なものの数 ϕ(n)\phi(n) は,

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

ただし,pip_inn の素因数。

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

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

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

  • 乗法性

  • ファイ関数の和

オイラーのファイ関数

この公式を使えば,「自然数 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=p1a1p2a2pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_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) の部分を中国剰余定理を用いて証明する必要がありますが,イメージとしては上記の説明が分かりやすいと思います。

乗法性

上記の公式から「オイラーのファイ関数の乗法性」が成立することが分かります。

m,nm,n が互いに素なとき,

ϕ(mn)=ϕ(m)ϕ(n)\phi(mn)=\phi(m)\phi(n)

m,nm,n が互いに素でないと成立しません。

ファイ関数の和

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

    \iff

ad\dfrac{a}{d} が整数かつ ad\dfrac{a}{d}nd\dfrac{n}{d} は互いに素

    \iff

ad\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 の約数であることに注意すると目標の式を得る。

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

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

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

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