next up previous 次: フェルマの小定理 上: フェルマの小定理 前: フェルマの小定理

オイラーの関数

自然数 $1,\ 2,\ \cdots,\ n$のなかにある$n$と互いに素な整数$x$の個数を$\varphi(n)$で表す.例えば,
\begin{displaymath}
\begin{array}{lll}
\varphi(1)=1,\ (x=1)&\varphi(2)=1,\ (...
...\ (x=1,\ 2,\ 3,\ 4)&
\varphi(6)=2,\ (x=1,\ 5)
\end{array}
\end{displaymath}

この$\varphi(n)$オイラーの関数という. これは自然数を定義域とする関数である. $p$ が素数ならば,明らかに
\begin{displaymath}
\varphi(p)=p-1
\end{displaymath}

である.

入試問題21のように,オイラーの関数を題材とする問題がある.まずこれを解いてみよう. この問題の(2)の解は異なる素数$p$$q$に対して $\varphi(pq)=\varphi(p)\varphi(q)$が成り立つことを意味している. 一般的に次のことが成り立つ.


定理 13       $a$$b$ が互いに素ならば, $\varphi(ab)=\varphi(a)\varphi(b)$である.

証明     $m=\varphi(a)$とし, $\alpha_1,\ \alpha_2,\ \cdots,\ \alpha_m$を 1以上$a$以下で$a$と互いに素な整数とする. $n=\varphi(b)$とし, $\beta_1,\ \beta_2,\ \cdots,\ \beta_n$ もまた同様に選ばれているとする.

$\alpha_i,\ \beta_j$の組は $mn=\varphi(a)\varphi(b)$ 個ある.その一つをとる. $a$$b$が互いに素なので

\begin{displaymath}
ak+\alpha_i=bl+\beta_j
\end{displaymath}

となる整数$k$$l$がとれる. この式の値は, $\alpha_i$$a$と互いに素なので$a$と互いに素で, $\beta_j$$b$と互いに素なので$b$と互いに素. つまり$ab$ と互いに素である.

この式の値を$ab$で割った余りを$\gamma_{ij}$とする. $\gamma_{ij}$

\begin{displaymath}
\gamma_{ij}\equiv \alpha_i\ (\bmod.\ a)\ ,\quad
\gamma_{ij}\equiv \beta_j\ (\bmod.\ b)
\end{displaymath}

となる1以上$ab$以下の数である.

$i$$i'$に変え同様にして$\gamma_{i'j}$をとる. $\gamma_{ij}\equiv ak+\alpha_{i}\quad (\bmod.\ a)$ $\gamma_{i'j}\equiv ak'+\alpha_{i'}\quad (\bmod.\ b)$ より$\gamma_{ij}$$\gamma_{i'j}$$a$を法として合同でない. よって$ab$を法として合同でない. $j$が異なる場合も,両方異なる場合も同様である. $ab$と互いに素で互いに合同でない整数が少なくとも $mn$個存在した.つまり

\begin{displaymath}
\varphi(a)\varphi(b)\le \varphi(ab)
\end{displaymath}

逆に $(\gamma,\ ab)=1$ とすると,$\gamma$$a$とも$b$とも互いに素なので $a$を法として$\alpha_i$に, $b$を法として$\beta_j$に合同となる$i,\ j$が存在する. $\gamma$$\gamma'$$ab$に関して合同でなければ $a$または$b$の少なくとも一方に関しても合同でない. よって異なる$\gamma$に対する $\alpha_i,\ \beta_j$の組はすべて異なる.

\begin{displaymath}
\varphi(a)\varphi(b)\ge \varphi(ab)
\end{displaymath}

あわせて等号が成立し定理が示された. (証明終わり)

例 3        $a=14,\ b=15$として上記の推論をたどってみよう.
\begin{displaymath}
\varphi(14)=\varphi(2)\varphi(7)=6,\
\varphi(15)=\varphi(3)\varphi(5)=8
\end{displaymath}

であり,それぞれ $\alpha_i,\ \beta_j$として
\begin{eqnarray*}
&&\alpha_1=1,\ \alpha_2=3,\
\alpha_3=5,\ \alpha_4=9,\
\al...
...eta_4=7,\
\beta_5=8,\ \beta_6=11,\
\beta_7=13,\ \beta_8=14
\end{eqnarray*}

である. $\alpha_4=9,\ \beta_6=11$をとってみよう.
\begin{displaymath}
14k+9=15l+11
\end{displaymath}

となる整数$k$$l$$k=-2,\ l=-2$がとれる. 式の値が$-19$なので $\gamma_{46}=210-19=191$である.
\begin{displaymath}
191\equiv 9\ (\bmod.\ 14)\ ,\quad
191\equiv 11\ (\bmod.\ 15)
\end{displaymath}

となっている.191は確かに$ab=210$と互いに素である.

$\alpha_6=13,\ \beta_5=8$をとってみよう.

\begin{displaymath}
14k+13=15l+8
\end{displaymath}

となる整数$k$$l$$k=5,\ l=5$がとれる. 式の値が83なので $\gamma_{65}=83$である.
\begin{displaymath}
83\equiv 13\ (\bmod.\ 14)\ ,\quad
83\equiv 8\ (\bmod.\ 15)
\end{displaymath}

となっている.これは確かに$ab=210$と互いに素である.

そして$191$$83$については$191-83=108$$ab$の倍数ではないので $ab$を法として合同でない.

このようにして得られる$6\cdot 8=48$個の$\gamma_{ij}$が 1以上210以下で210と互いに素な数の全体となる.


Aozora
2015-03-02