オイラーの関数 (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$ 個あるということです。
 

(a, x) = d を満たす x

 $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)$ 個存在します。

[定理 D7 の証明] $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$ に一致しています。

コメントをどうぞ

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

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