2014/04/17

オイラーのファイ関数のイメージと性質

分野: 整数問題  レベル: 数学オリンピック

オイラーのファイ関数:
自然数 $n$ に対して,$1$ から $n$ までの自然数の中で $n$ と互いに素なものの数 $\phi(n)$ は,
$\phi(n)=n\displaystyle\prod_{i=1}^k(1-\dfrac{1}{p_i})$
ただし,$p_i$ は $n$ の素因数。

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

オイラーのファイ関数

この公式を使えば自然数 $n$ と互いに素な $n$ 以下の自然数を高速で求めることができます。この手の問題は入試問題でたまに出題されます。また,数学オリンピックの整数問題でも役にたつかもしれません。(残念ながら数オリに直接役立つ例は発見できていません)

$12$ と互いに素な $12$ 以下の自然数の個数は,
$12=2^2\cdot 3$ より,$12(1-\dfrac{1}{2})(1-\dfrac{1}{3})=4$ 個。
実際に全列挙すれば,$1, 5, 7, 11$ の $4$ つで正しいことが確認できる。

$180$ と互いに素な $180$ 以下の自然数の個数は,
$180=2^2\cdot 3^2\cdot 5$ より,$180(1-\dfrac{1}{2})(1-\dfrac{1}{3})(1-\dfrac{1}{5})=48$ 個
実際に全列挙するのは疲れるのでファイ関数の公式が役に立った。

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

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ について,$1$ から $n$ までの自然数の中で $n$ と互いに素なものがいくつあるか考えます。

「 $n$ と互いに素」⇔「 $p_1$ と互いに素かつ $p_2$ と互いに素かつ・・・ $p_k$ と互いに素」という素数の性質を利用します。

大雑把な説明

オイラーのファイ関数

まず,$1$ から $n$ の中で $p_1$ と互いに素なものの割合は,$\dfrac{p_1-1}{p_1}$ 。
生き残った $n(1-\dfrac{1}{p_1})$ 個の中で $p_2$ と互いに素なものの割合は,$\dfrac{p_2-1}{p_2}\cdots(1)$
さらに生き残った $n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})$ 個の中で $p_3$ と互いに素なものの割合は,$\dfrac{p_3-1}{p_3}$
これを繰り返すとオイラーのファイ関数の公式を得る。

厳密には$(1)$ の部分を中国剰余定理を用いて証明する必要がありますが,イメージとしては上記の説明が分かりやすいと思います。

乗法性

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

$m,n$ が互いに素なとき,
$\phi(mn)=\phi(m)\phi(n)$

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

ファイ関数の和

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

$\displaystyle\sum_{d\mid n}$ とは,$n$ の全ての約数 $d$ について和を取るという意味です。例えば $n=6$ とすると,
$\phi(1)+\phi(2)+\phi(3)+\phi(6)=1+1+2+2=6$
となります。

(証明)
$A=\{1,2,\cdots,n\}$ とする。 $a\in A$ と $n$ の約数 $d$ について,
$a$ と $n$ との最大公約数が $d$
$\iff$ $\dfrac{a}{d}$ が整数かつ $\dfrac{a}{d}$ と $\dfrac{n}{d}$ は互いに素
$\iff$ $\dfrac{a}{d}$ が $1,2,\cdots,\dfrac{n}{d}$ のいずれか,かつ $\dfrac{a}{d}$ と $\dfrac{n}{d}$ は互いに素

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

よって,$A$ の要素を $n$ との最大公約数 $d$ でグループ分けすることにより,
$n=\displaystyle\sum_{d\mid n}\phi(\dfrac{n}{d})$
が分かる。 $d$ が $n$ の約数 $\iff \dfrac{n}{d}$ が $n$ の約数であることに注意すると目標の式を得る。

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

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

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

分野: 整数問題  レベル: 数学オリンピック