オイラー関数

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

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

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

$$\phi (p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$$
によって与えられます。

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

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

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

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

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

約数のオイラー関数の和

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

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

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

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

$n=12$ でも試してみます。$12$ の約数は
$$\{1,2,3,4,6,12\}$$
なので、
$$\begin{array}{rl}\sum _{d|12}\phi (d)& =\phi (1)+\phi (2)+\phi (3)+\phi (4)+\phi (6)+\phi (12)\\ & =1+1+2+2+3+2+1=12\end{array}$$
となって確かに $12$ に一致しています。