今回はオイラー関数の値を求める公式を証明します。
前回証明したオイラー関数の乗法性が大活躍するので、必見です。
公式を得るための準備
オイラー関数とは、１からｎまでの数のうち、ｎと互いに素なものの個数を数えるものです。
$\phi(5)$を考えると、
１，２，３，４，５のうち、５と互いに素なのは１，２，３，４の４つなので、
$\phi (5)=4$
です。
一般に$p$が素数の時、$p$は１と自分自身以外に約数を持たないので
$p$は$1,2,3,\cdots, p-1$と互いに素となり、
$\phi(p)=p-1$
が成り立ちます。
素数でなくとも、$n$の値が小さい場合は、具体的に書き出して数え上げればよいですが、
例えば$\phi(105)$など、大きな数はちょっと大変です。
ここで、前回の記事で手に入れたオイラー関数の乗法性を使うと、
驚くほど簡単に$\phi(105)$を計算することができます。
（オイラー関数の乗法性）
$m, n$が互いに素な時、
$\phi (mn)=\phi(m)\phi(n)$
が成り立つ
オイラー関数の乗法性の証明が気になる方は、
前回の記事をご覧ください
では、オイラー関数の乗法性を用いて$\phi(105)$を実際に求めてみましょう。
$\phi(105)=\phi(3×35)=\phi(3)×\phi(35)=\phi(3)×\phi (5×7)$
$=\phi (3)×\phi(5)×\phi(7)=(3-1)×(5-1)×(7-1)=48$
といった具合です。
しかし、$m, n$が互いに素でない場合は途中までしか変形できません。
例えば、$m=36, n=24$を考えましょう
$\phi(36×24)=\phi(2^2・3^2×2^3・3)=\phi (2^5×3^3)=\phi(2^5)\phi(3^3)$
乗法性を発動するには互いに素という条件が必要なので、
$2^5$と$3^3$はこれ以上掛け算に分解できません。
したがって、ここから先の計算は定義に基づいて進めるしかなくなってしまいますが、
あまりにも面倒です。
そこで、
$p$を素数$e$を自然数としたとき、
$\phi(p^e)$の値を計算する法則はないか？
ということを考えてみます。
$\phi(p^e)$は、
$1, 2, 3, \cdots, p^e$までの$p^e$個の数のうち、
$p$と互いに素なものの個数です。
ゆえに、
$1, 2, 3, \cdots, p^e$の中に$p$の倍数がいくつあるか数え上げて引き算すればよいです。
いきなり考えるのは難しく感じるものなので、具体例で考えましょう。
例えば、
$1, 2, 3, \cdots, 2p$
までの$p$の倍数の個数を考えましょう。
$1, 2, \cdots, $ $p$, $\cdots, $ $2p$ つまり２個です
同様に、例えば
$1, 2, 3, \cdots, 5p$ならば、 $p$の倍数は５個です
$1, 2, 3, \cdots, p×p$なら、$p$の倍数は$p$個です。
$1, 2, 3, \cdots, p^2×p$なら、$p$の倍数は$p^2$個です。
ということは、
$1, 2, 3, \cdots, p^e$なら、$p^e=p^{e-1}×p$なので、
$p$の倍数は$p^{e-1}$個です。
よって、
$1, 2, 3, \cdots, p^e$の中で、$p$と互いに素なものの個数は、
$p^e-p^{e-1}$です。
したがって、$\phi (p^e)=p^e-p^{e-1}$となります。
$\phi (p^e)=p^e-p^{e-1}$
を次の見出しで使いますので、覚えておいてください。
オイラー関数を求める公式
$n$が一般の自然数の場合の$\phi(n)$を求める公式を導出しようと思います。
先に結果だけ示しておきましょう
（定理）
$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$と素因数分解されるとき、
$\phi (n) =n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots (1-\dfrac{1}{p_k})$
です。
$n$は素因数分解された形で使います。
例えば、$360=2^33^25$です。このように、
$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$
と素因数分解されるとして公式を作ることになります。
ただし、$p_i$ $(i=1, 2, \cdots, k)$は素数、$e_i$ $(i=1, 2, \cdots, k)$は自然数です。
導出の際には、
$\phi(mn)=\phi(m)\phi(n)$
と
$\phi(p^e)=p^e-p^{e-1}$
を用います。
$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$と素因数分解されるとき、
$\phi (n) =n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots (1-\dfrac{1}{p_k})$
（証明）
$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$
と素因数分解されるとき、$\phi(n)$を求める。
$\phi (n)=\phi(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})$である。
$p_i$ $(i=1, 2, \cdots, k)$はそれぞれ素数であるので、
$p_1^{e_1}, p_2^{e_2}, \cdots, p_k^{e_k}$は、共通の因数を１しか持たない。
よって、
$\phi(p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k})=\phi(p_1^{e_1})\phi (p_2^{e_2}) \cdots \phi (p_k^{e_k})$
である。
いま、$\phi (p_i^{e_i})=p_i^{e_i}-p_i^{e_i -1}$であるので、
$\phi(n)=(p_1^{e_1}-p_1-{e_1 -1})(p_2^{e_2}-p_2^{e_2 -1})\cdots (p_k^{e_k}-p_k^{e_k -1})$
$= \lbrace p_1^{e_1}(1-\dfrac{1}{p_1})\rbrace \lbrace p_2^{e_2}(1-\dfrac{1}{p_2})\rbrace\cdots \lbrace p_k^{e_k}(1-\dfrac{1}{p_k})\rbrace$
$=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots (1-\dfrac{1}{p_k})$
となり、$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$
から、
$\phi (n)=n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\cdots (1-\dfrac{1}{p_k})$
となる。
（証明終了）
まとめ
いかがでしたか？
今回はオイラー関数$\phi(n)$の値を計算するための公式を証明しました。
オイラー関数については、ほかにメビウスの反転公式と呼ばれるものとの関係性など、
面白い内容の宝庫なので、また機会があったらどんどん記事にしていこうと思います。
ご期待ください。
ではまた次回の記事でお会いしましょう！
コメント