オイラー関数

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

オイラー関数（オイラーのφ関数）

たとえば $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)$ を求めたいのですが、それにはオイラー関数が乗法的であることを証明する必要があります。

[証明] $1$ ～ $ab$ を次のように並べます。

1 行目において $a$ と互いに素である数は $\varphi (a)$ 個あります。それを小さい順に並べて
\[\{\:a_1,\;a_2,\;\cdots\;a_{\varphi (a)}\:\}\tag{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)\]
のように乗算で表すことができます。すなわち次の定理が成り立ちます。

例として $\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$ と最大公約数が $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\]
で計算することができます。一般に次の定理が成り立ちます。

[証明] $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$ 自身に一致します。このことはもちろん一般にも成り立ちます。

$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$ に一致しています。