当サイトではアフィリエイトプログラムを利用して商品を紹介しています。

オイラー関数

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

オイラー関数(オイラーのφ関数)

【定義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)\]を満たす。

[証明] $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$ 個あるということです。

約数のオイラー関数の和

$15$ 以下の数について、それぞれ $15$ との最大公約数を求めて下の表に並べてみます(左の列です)。

$(15,\:x)$ $(5,\:x/3)$
$(15,\:1)=1$
$(15,\:2)=1$
$(15,\:3)=3$ $(5,\:1)=1$
$(15,\:4)=1$
$(15,\:5)=5$
$(15,\:6)=3$ $(5,\:2)=1$
$(15,\:7)=1$
$(15,\:8)=1$
$(15,\:9)=3$ $(5,\:3)=1$
$(15,\:10)=5$
$(15,\:11)=1$
$(15,\:12)=3$ $(5,\:4)=1$
$(15,\:13)=1$
$(15,\:15)=15$

この中から $15$ と最大公約数が $3$ になる数、すなわち
\[(15,\:x)=3\]
を満たす $x$ は
\[x=3,\;6,\;9,\;12\]
の計 4 個あります。またこれは右列を見ると
\[\left(\frac{15}{3},\:\frac{x}{3}\right)=\left(5,\:\frac{x}{3}\right)=1\]すなわち $(5,\:t)=1$ をみたす $t$ の数と一致しています。
その数はオイラー関数を用いて
\[\varphi (5)=4\]
で計算することができます。一般に次の定理が成り立ちます。

【定理D7】$d\:|\:a$ であるとき
\[(a,\:x)=d\;(1\leq x\leq a)\]を満たす $x$ は $\varphi (a/d)$ 個存在する。

[証明] $x=kd$ とおくと
\[(a,\:kd)=d\quad (1\leq kd\leq a)\]
となるので、
\[\left(\frac{a}{d},\:k\right)=1\quad (1\leq kd\leq a)\]
このような $k$ は $\varphi (a/d)$ 個存在するので、$(a,\:x)=d$ を満たす $x$ も $\varphi (a/d)$ 個存在します。(証明終)

$15$ の約数を並べると
\[\{\;1,\;3,\;5,\;15\:\}\]
となります。先ほどの表から $15$ との最大公約数がそれぞれの約数になるように $x$ を分類すると(定理 D7 を使って計算することもできます)、
\[\begin{align*}(15,\:x)&=1\qquad \varphi (15)=8\\[6pt](15,\:x)&=3\qquad \varphi (5)=4\\[6pt](15,\:x)&=5\qquad \varphi (3)=2\\[6pt](15,\:x)&=15\qquad \varphi (1)=1\end{align*}\]
となります。これらは $15$ 以下の数について全て数え上げているのですから、
\[\varphi (1)+\varphi (3)+\varphi (5)+\varphi (15)=15\]
が成り立ちます。すなわち $15$ の約数のオイラーの関数の和が $15$ 自身に一致します。このことはもちろん一般にも成り立ちます。

【定理D8】正整数 $n$ のすべての約数について、オイラー関数の和をとると $n$ に等しくなる。すなわち
\[\sum_{d|n}\varphi (d)=n\]

$n=12$ でも試してみます。$12$ の約数は
\[\{\;1,\;2,\;3,\;4,\;6,\;12\:\}\]
なので、
\[\begin{align*}\sum_{d|12}\varphi (d)&=\varphi (1)+\varphi (2)+\varphi (3)+\varphi (4)+\varphi (6)+\varphi (12)\\[6pt]&=1+1+2+2+3+2+1=12\end{align*}\]
となって確かに $12$ に一致しています。

エクセルや数学に関するコメントをお寄せください