オイラーの関数 (n と互いに素となる n 以下の数の個数)

 今回は数論の中でも極めて重要な役割を担う オイラーの関数 について解説します。

オイラーの関数

[定義 D3] 正整数 $n$ と互いに素な $n$ 以下の正整数の個数を $\varphi (n)$ と書き、これをオイラーの関数 (Euler's function) と定義します。

 たとえば $n=10$ 以下の正整数
 
\[\{\:1,\;2,\;3,\;4,\;5,\;6,\;7,\;8,\;9\:\}\]
のうち $10$ と互いに素である要素は
 
\[\{\;1,\;3,\;7,\;9\:\}\]
の 4 個なので $\varphi (10)=4$ となります。$n$ が素数 $7$ であるとき、$7$ 以下の正整数
 
\[\{\:1,\;2,\;3,\;4,\;5,\;6,\;7\:\}\]
のうち $7$ 自身を除く要素は全て $7$ と互いに素なので、$\varphi (7)=7-1=6$となります。一般に素数 $p$ について
 
\[\varphi (p)=p-1\]
が成り立ちます。また $n=5^4$ の場合を考えると、$1$ ~ $5^4$ のうち、$5$ の倍数は $5$ つごとに現れるので、その個数は
 
\[5^4/5=5^3\]
あって、それ以外の数は $5$ と互いに素です。すなわち
 
\[\varphi (5)=5^4-5^3=5^3(5-1)=500\]
となります。一般に $n=p^k$ のときは
 
\[\varphi (p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right)\]
によって与えられます。
 

オイラーの関数は乗法的関数です

 ここからさらに一般化して $n=p_1^{a_1}\,p_2^{a_2}\,\cdots\,p_k^{a_k}$ の場合の $\varphi (n)$ を求めたいのですが、それにはオイラー関数が乗法的であることを証明する必要があります。

[定理 D6] オイラー関数は乗法的関数です。すなわち正整数 $a,\;b$ について
\[\varphi (ab)=\varphi (a)\,\varphi (b)\]を満たします。

[定理 D6 の証明] $1$ ~ $ab$ を次のように並べます。

$1$ $2$ $\cdots$ $t$ $\cdots$ $a$
$1+a$ $2+a$ $\cdots$ $t+a$ $\cdots$ $2a$
$1+2a$ $2+2a$ $\cdots$ $t+2a$ $\cdots$ $3a$
$\cdots$ $\cdots$ $\cdots$ $\cdots$ $\cdots$ $\cdots$
$1+(b-2)a$ $2+(b-2)a$ $\cdots$ $t+(b-2)a$ $\cdots$ $(b-1)a$
$1+(b-1)a$ $2+(b-1)a$ $\cdots$ $t+(b-1)a$ $\cdots$ $ba$

 1 行目において $a$ と互いに素である数は $\varphi (a)$ 個あります。
 それを小さい順に並べて
 
\[\{\:a_1,\;a_2,\;\cdots\;a_{\varphi (a)}\:\}\tag{1}\]
とします。この中の1つを $t$ とすると、
 
\[\{\:t,\;t+a,\;\cdots\;t+(b-1)a\:\}\tag{2}\]
はいずれも法 $b$ について合同ではありません。実際、
 
\[t+ka\equiv t+la\;(\mathrm{mod}\;b),\quad (0\leq k\lt l\leq b-1)\]
とおいてみると
 
\[(l-k)a\equiv 0\;(\mathrm{mod}\;b)\]
となりますが、$0\lt l-k\lt b,\;(a,b)=1$ なので、この合同式は成り立ちません ($l-k$ が $b$ より小さいので $b$ で割り切れるはずがありません)。したがって (2) は完全剰余系をなしていることになり、$b$ と互いに素な数は $\varphi (b)$ 個あることになります。このことは (1) の $\varphi (a)$ 個の数それぞれについていえるので、$ab$ より小さくて $ab$ と互いに素である数は全部で $\varphi (a)\,\varphi (b)$ 個あることになります。すなわちオイラー関数は乗法的関数です。(証明終)

 オイラー関数が乗法的であることがわかっったので $n$ が
 
\[n=p_1^{a_1}\,p_2^{a_2}\,\cdots\,p_k^{a_k}\]
のように素因数分解されるとき $\varphi (n)$ は
 
\[\varphi (n)=p_1^k\left(1-\frac{1}{p_1}\right)\,p_2^k\left(1-\frac{1}{p_2}\right)\,\cdots\,p_k^k\left(1-\frac{1}{p_k}\right)\]
のように乗算で表すことができます。すなわち次の定理が成り立ちます。

[定理 D6] 正整数 $n$ が $n=p_1^{a_1}\,p_2^{a_2}\,\cdots\,p_k^{a_k}$ のように素因数分解されるとき、
\[\varphi (n)=n\left(1-\frac{1}{p_1}\right)\,\left(1-\frac{1}{p_2}\right)\,\cdots\,\left(1-\frac{1}{p_k}\right)\]

 例として $\varphi (4500)$ を計算してみます。
 $4500=2^2\,3^2\,5^3$ と素因数分解できるので、
 
\[\varphi (4500)=4500\left(1-\frac{1}{2}\right)\,\left(1-\frac{1}{3}\right)\,\left(1-\frac{1}{5}\right)=1200\]
となります。すなわち $4500$ 以下の数で $4500$ と互いに素である数は $1200$ 個あるということです。

 ≫ 約数のオイラーの関数の和 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください