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

オイラーの関数

自然数 $1,\ 2,\ \cdots,\ n$のなかにある$n$と互いに素な整数$x$の個数を$\varphi(n)$で表す．例えば，

$$\begin{array}{lll} \varphi(1)=1,\ (x=1)&\varphi(2)=1,\ (... ...\ (x=1,\ 2,\ 3,\ 4)& \varphi(6)=2,\ (x=1,\ 5) \end{array}$$

この$\varphi(n)$をオイラーの関数という． これは自然数を定義域とする関数である． $p$ が素数ならば，明らかに

$$\varphi(p)=p-1$$

である．

入試問題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$が互いに素なので

$$ak+\alpha_i=bl+\beta_j$$

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

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

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

となる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$個存在した．つまり

$$\varphi(a)\varphi(b)\le \varphi(ab)$$

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

$$\varphi(a)\varphi(b)\ge \varphi(ab)$$

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

例 3        $a=14,\ b=15$として上記の推論をたどってみよう．

$$\varphi(14)=\varphi(2)\varphi(7)=6,\ \varphi(15)=\varphi(3)\varphi(5)=8$$

であり，それぞれ $\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$をとってみよう．

$$14k+9=15l+11$$

となる整数$k$と$l$は$k=-2,\ l=-2$がとれる． 式の値が$-19$なので $\gamma_{46}=210-19=191$である．

$$191\equiv 9\ (\bmod.\ 14)\ ,\quad 191\equiv 11\ (\bmod.\ 15)$$

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

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

$$14k+13=15l+8$$

となる整数$k$と$l$は$k=5,\ l=5$がとれる． 式の値が83なので $\gamma_{65}=83$である．

$$83\equiv 13\ (\bmod.\ 14)\ ,\quad 83\equiv 8\ (\bmod.\ 15)$$

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

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

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