合同式の逆元からオイラー関数へ

大学で習う初頭整数論の便利屋さん、

オイラーの$\varphi$関数

今回は、そんな便利屋さんについて学んでいきましょう！

合同式の方程式について

合同式シリーズの前の記事では、合同式の方程式が解けるための条件を考えました。

$ax\equiv b(\mathrm{mod}k)$

を満たす整数$x$について考えてきたわけです。

詳しくはこちらの記事を参照ください。

そして、例えば

$2x\equiv 1(\mathrm{mod}5)$

の解は、$x\equiv 3$でした。

前回はこれを代入作戦と一次不定方程式を用いて解きましたが、

この計算過程には、

逆元という考え方が本質的に隠れています。

まずは逆元について深めていきましょう。

逆元とは？

ある数$a$に対して、

$a\mathrm{・}b=1$

となる数$b$が存在するとき、

$b$は$a$の逆元である、といいます。

実数の世界では、例えば

$2\times {\displaystyle \frac{1}{2}}=1$

なので、$2$の逆元は${\displaystyle \frac{1}{2}}$です。

実数の世界では、$0$以外の数には必ず逆元が存在します。

（これは結構すごい事実です）

ここで、合同式の世界で同じようなことを考えてみましょう。

例えば、$\mathrm{mod}5$で考えてみます。

$a$に対して、$a\mathrm{・}b=1$となる$b$を探します。

１，２，３，４　を順に処理していきましょう。（０は除いています）

$1\times 1=1\equiv 1(\mathrm{mod}5)$

なので、１の逆元は１自身です。

２はちょっと複雑ですが、

$2\times 3=6\equiv 1(\mathrm{mod}5)$なので、

２の逆元は３になります。

同様に、３の逆元は２です。

では４は？

$4\times 4=16\equiv 1(\mathrm{mod}5)$

なので、４の逆元は４自身です。

ということで、$\mathrm{mod}5$の世界では、

０を除いた１，２，３，４ すべてに逆元が存在しました！

他の例も考えてみましょう。

$\mathrm{mod}4$ではどうでしょうか？

$1\times 1=1\equiv 1(\mathrm{mod}4)$より、

１の逆元は１自身です。これは先ほどと同じですね。

では２は？

$2\times 1=2\equiv 2(\mathrm{mod}4)$

$2\times 2=4\equiv 0(\mathrm{mod}4)$

$2\times 3=6\equiv 2(\mathrm{mod}4)$

逆元、ないじゃん！！！

なんと、$\mathrm{mod}4$の世界では逆元が存在しない数があります。

しかしこれはよくよく考えてみると当たり前のことです。

合同式の世界では、

そもそも割り算は互いに素という条件がなければできませんでした。

詳しくはこちらの記事をご覧ください。

なので、例えば、$\mathrm{mod}4$の世界では、

４と互いに素である１と３しか逆元は持たないのです。

このように、

合同式の世界の逆元を考える際には、

互いに素な奴らがどの程度いるか

ということがとても重要な情報になります。

そこで登場するのがオイラー関数です。

具体例を考えてみましょう

例えば$\varphi (5)$

１，２，３，４，５のうち、５と互いに素なのは

１，２，３，４なので、$\varphi (5)=4$

です。

$\varphi (4)$は、

１，２，３，４のうち、４と互いに素なのは

１，３なので、$\varphi (4)=2$

です。

しかし、$\varphi (720)$とかになるとちょっと数え上げるのは大変すぎます。

そこで、$\varphi (n)$を求めるための計算法則はないかな？

ということが気になります。

さて。

我々は今、オイラー関数の計算規則を見つけようとしています。

何をするか？

観察です！！

オイラー関数の値を観察

観察のステップでは、データの数がモノを言います。

ひとまず、オイラー関数の値を求めまくってみましょう。

$\varphi (1)=1$

$\varphi (2)=1$

$\varphi (3)=2$

$\varphi (4)=2$

$\varphi (5)=4$

$\varphi (6)=2$

$\varphi (7)=6$

$\varphi (8)=4$

$\varphi (9)=6$

$\varphi (10)=4$

$\varphi (11)=10$

$\varphi (12)=4$

$\varphi (13)=12$

$\varphi (14)=6$

$\varphi (15)=8$

どうでしょう。

なにか気になる点や、規則性は見いだせましたか？

僕の感想としては、

なんか、偶数が多いということがまず目に留まります。

もうこの時点で、実は結構面白いんです。

例えば、$\varphi (n)=3$となる$n$は存在するのかどうかとか。

$\varphi (n)$の値には、全ての自然数は出現するのか？

もし$\varphi (n)$の値として出現しない数があるのなら、

出現する数と出現しない数の違いは何なのか？

判定条件はないのか？

など、興味が尽きません。

オイラー関数はまじで研究ポイントの宝庫というか、

本当に思いがけないような場面で色々登場する便利屋さんです。

記事にしたいことが沢山あるのですが、余白が足りないので（フェルマー並感）

今回はオイラー関数の最特徴的な性質だけ紹介し、

残りはまた別の記事でまとめようと思います。

ご期待ください。

やたら偶数が多いという点を除くと、次に注目すべきポイントは、

周りの値と比べて急に大きくなるポイントがあるということです。

例えば、１０，１１，１２の並びを見てみましょう。

$\varphi (10)=4,\varphi (11)=10,\varphi (12)=4$

で、$\varphi (11)$だけやたら大きい値になってます。

このような感じで、周囲より大きい値になっている奴らだけ取り出してみましょう

$\varphi (5),\varphi (7),\varphi (11),\varphi (13)\cdots$

素数です

例えば、$p$が素数の時、

$\varphi (p)=p-1$が成り立っています。

素数の定義と$\varphi (n)$の定義をよくよく考えれば実はこれは当り前のことですが、

結構驚きの結果ではないですか？

素数とは、１と自身以外に約数を持たない数です。

$\varphi (n)$とは、$1$から$n$までの数のうち、$n$と互いに素なっものの個数です。

$p$を素数とすると、$1,2,3,\cdots ,p$までのうち、$p$と互いに素なのは

$1,2,\cdots ,p-1$の$p-1$個です。

よって$\varphi (p)=p-1$となります。

素数がなにか特別っぽい動きをしていると、

それだけでちょっと嬉しい気持ちになるのが数学ジャンキーです。

では、合成数の場合はどうでしょうか？

合成数は、約数に着目するのがセオリーです。

例えば、$\varphi (15)=8$に着目しましょう

いま、$15=3\times 5$です。

ここで、$\varphi (3)=2,\varphi (5)=4$

なにか神秘を感じませんか？

$\varphi (15)=\varphi (3)\times \varphi (5)$です！！

ヤバくないですか？

$\varphi (mn)=\varphi (m)\varphi (n)$

これはいつでも成り立つのでしょうか？

例えば$\varphi (9)=6$ です

$9=3\times 3$です。

$\varphi (3)=2$でした

ふむ

$\varphi (mn)=\varphi (m)\varphi (n)$

はいつでも成り立つわけではないようです。

どういうときに成り立つかというと、

互いに素な時です

$$\varphi (mn)=\varphi (m)\varphi (n)$$

この性質を、オイラー関数の乗法性と言います。

まとめ

いかがでしたか？

・合同式の世界では、逆元はいつも存在するわけではない。

・逆元を考える際には互いに素という条件が大切

・互いに素なやつらがどの程度いるか、数えることができたら便利

・オイラー関数登場

という流れを楽しんでいただけたらと思います。

次回の記事では、今回観察したオイラー関数の乗法性

$\varphi (mn)=\varphi (m)\varphi (n)$

を証明しようと思うので、ご期待ください。