ホーム >> 整数 >> オイラーの $\varphi$ 関数の性質

オイラーの定理に表れる,オイラーの $\varphi$ 関数について解説します.




オイラーの $\varphi$ 関数とは

$1$ から $n$ までの自然数のうち,$n$ と互いに素なものの個数を $\varphi (n)$ とかき,関数 $\varphi$ をオイラーの $\varphi$ 関数という.

オイラーの $\varphi$ 関数は,オイラーのトーシェント関数,または単にオイラー関数とも呼ばれます.たとえば,$n=6$ のとき,$1$ から $6$ までの自然数で,$6$ と互いに素なものは,$1,5$ なので,$\varphi (6)=2$ となります.以下の表は,$1$ から $15$ までの数に対するオイラー関数の値です. \begin{array}{c|cccccccccccccccc} n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&\cdots \\ \hline \varphi(n)&1&1&2&2&4&2&6&4&6&4&10&4&12&6&8&\cdots \end{array}
$n$ が小さな値のときは,単純に数えればよいですが,大きくなっていくと数えるのは大変です.一般の $n$ に対して $\varphi(n)$ を与える公式はないのでしょうか.実は,$\varphi(n)$ を計算する公式はあるのです.

特殊な場合の $\varphi$ の値

まずはオイラー関数の値が簡単にわかる場合について考えてみましょう.

$\varphi(p)$ について

素数 $p$ について,$1$ から $p$ までの数のうち,$p$ と互いに素な数は $p$ 以外の $p-1$ 個あります.したがって,$\color{red}{\varphi(p)=p-1}$ となります.

$\varphi(p^k)$ について

次に素数 $p$ のべき乗 $p^k$ について考えてみましょう.($k$ は自然数)
$\varphi(p^k)=$($1$ から $p^k$ のうち,$p^k$ と互いに素な数の個数)
$=$ ($1$ から $p^k$ のうち,$p$ の倍数でないもの)
です.$1$ から $p^k$ のうち,$p$ の倍数は, $$p,2p,3p,\cdots,p^{k-1}p$$ の $p^{k-1}$ 個あります.したがって,$\color{red}{\varphi(p^k)=p^k-p^{k-1}}$ となります.

ここまでで,素数と素数ベキに対して,オイラー関数の値が具体的に得られました.

オイラー関数の乗法性

オイラー関数の乗法性: $n$ と $m$ を互いに素な整数,$\varphi$ をオイラー関数とするとき,次が成り立つ. $$\large \varphi(mn)=\varphi(m)\varphi(n)$$


$\varphi(mn)=\varphi(m)\varphi(n)$ の証明

わかりやすいように $1$ から $mn$ の整数を以下のように表にして並べてます.
\begin{array}{ccccccc} 1&2&\cdots&t&\cdots&m-1&m \\ 1+m&2+m&\cdots&t+m&\cdots&m-1+m&2m \\ \vdots&\vdots&&\vdots&&\vdots&\vdots \\ 1+(n-2)m&2+(n-2)m&\cdots&t+(n-2)m&\cdots&(m-1)+(n-2)m&(n-1)m \\ 1+(n-1)m&2+(n-1)m&\cdots&t+(n-1)m&\cdots&(m-1)+(n-1)m&mn \end{array} 要するに,小さい順に左上から右に向かって整数を並べていき,$m$ 個並べたら下の行に同様に並べていくのです.

さて,$1$ から $m$ までの整数のうち,$m$ と互いに素なものの個数は $\varphi(m)$ 個あるのでそれらを,$a_1,a_2,\cdots,a_{\varphi(m)}$ とします.このうちのひとつを $t$ とすると,$t,t+m,t+2m,\cdots,t+(n-2)m,t+(n-1)m$ の $n$ 個の数はどの $2$ つも $n$ を法として互いに合同ではありません.すなわち,$n$ で割った余りがすべて異なります.実際,ある $2$ つの数 $t+im,\ t+jm$ ($0 \le i < j \le n-1$) が合同だとすると, $$t+im \equiv t+jm  (mnd\ n)$$ より, $$(i-j)m \equiv 0  (mod\ n)$$ となるのですが,$m$ と $n$ は互いに素であること,および $0 \le i < j \le n-1$ より,これは不合理です.これより,$t,t+m,t+2m,\cdots,t+(n-2)m,t+(n-1)m$ の $n$ 個の数のうち,$n$ と互いに素なものの個数は $\varphi(n)$ 個あります.以上の議論を $t$ を $a_1,a_2,\cdots,a_{\varphi(m)}$ すべてにわたって考えると, $$\varphi(mn)=\varphi(m)\varphi(n)$$ が結論づけられます.

一般の場合の $\varphi$ の値

素数ベキの値と,乗法性から,一般の $n$ に対して,オイラー関数の値を求めることができます.自然数 $n$ を素因数分解表示して, $$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$ とすると,オイラー関数の乗法性から, $$\varphi(n)=\varphi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k})=\varphi(p_1^{\alpha_1})\varphi(p_2^{\alpha_2}\cdots p_k^{\alpha_k})=\cdots =\varphi(p_1^{\alpha_1})\varphi(p_2^{\alpha_2})\cdots\varphi(p_k^{\alpha_k})$$ となって,後はオイラー関数の中身が素数ベキなので, $$=(p_1^{\alpha_1}-p_1^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})$$ と結論づけられます.

自然数 $n$ の素因数分解表示を, $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ とすると, $$\large \varphi(n)=(p_1^{\alpha_1}-p_1^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})$$ $$\large =n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)$$

$\underline{Example}$
・$36$ 以下の自然数で,$36$ と互いに素な数の個数は, $$\varphi(36)=\varphi(2^23^2)=\varphi(2^2)\varphi(3^2)=(2^2-2)(3^2-3)=12$$ より,$12$ 個.
・$128$ 以下の自然数で,$128$ と互いに素な数の個数は, $$\varphi(128)=\varphi(2^7)=2^7-2^6=64$$ より,$64$ 個.