フェルマーの小定理を一般化してオイラーの定理へ

フェルマーの小定理は実は一般化できます。

この記事では、フェルマーの小定理を一般化するに至る思考プロセスを

具体例を基に丁寧に解説します。

丁寧に進めるぞ！という決意が記事の長さという形で出力されているので、

なんでそんな変形するの！？という部分を詳しく知りたい以外はブラウザバックしてください。

フェルマーの小定理のおさらい

前回は等比数列を合同式の視点で観察して３つのグループに分類し、フェルマーの小定理をゲットしました。

具体的には、

$a, a^2, a^3, \cdots$

という等比数列を$\mod n$

で眺めていました。

$a=2$で固定して、$n$の値を色々変えて観察をしたわけです。

観察結果をまとめたものが以下です。

$2 \equiv 0 (\mod 2)$

$2\equiv 2,$　$2^2 \equiv 1 (\mod 3)$

$2 \equiv 0,$　$2^2 \equiv 0, $　$2^3 \equiv 0(\mod 4)$

$2 \equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 3,$　$2^4 \equiv 1(\mod 5)$

$2 \equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 2,$　$2^4 \equiv 4,$　$2^5 \equiv 2(\mod 6)$

$2 \equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 1,$　$2^4 \equiv 2,$　$2^5 \equiv 4,$　$2^6 \equiv 1(\mod 7)$

$2\equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 0,$　$2^4 \equiv 0,$　$2^5 \equiv 0, $　$2^6 \equiv 0 ,$　$2^7 \equiv 0 (\mod 8)$

$2 \equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 8,$　$2^4 \equiv 7,$　$2^5 \equiv 5,$　$2^6 \equiv 1,$　$2^7 \equiv 2,$　$2^8 \equiv 4 (\mod 9)$

$2\equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 8,$　$2^4 \equiv 6 ,$　$2^5 \equiv 2,$　$2^6 \equiv 4,$　$2^7 \equiv 8,$　$2^8 \equiv 6,$　$2^9 \equiv 2 (\mod 10)$

$2\equiv 2,$　$2^2 \equiv 4,$　$2^3 \equiv 8,$　$2^4 \equiv 5,$　$2^5 \equiv 10,$　$2^6 \equiv 9,$　$2^7 \equiv 7 ,$　$2^8 \equiv 3,$　$2^9 \equiv 6$　$2^{10} \equiv 1 (\mod 11)$

青マーカーは０が出てくるグループ

黄色マーカーは最後が１で終わるグループ

青マーカーの結果から、法が素数の場合は

$a^{p-1}\equiv 1 (\mod p)$

が成り立つのではないかという予想が立ち、それを証明してフェルマーの小定理を得た、

というのが前回のあらすじでした。

今回はオレンジマーカーの部分に切り込んでいきます。

フェルマーの小定理については以下の記事をご覧ください

観察を深めてオイラーの定理を見出す

前回は

$a, a^2, a^3, a^4, \cdots$

という等比数列と$\mod n$

のうち、$a$を固定して$n$の値を色々変えて観察しました。

今回は、逆の観察をしてみましょう。

すなわち、$n$を固定して$a$を色々変えてみる作戦です。

$n$はほどほどに大きい値で、かつ素数ではなく合成数がよいので、

$n=10$あたりで考えてみましょう。

$n=10$以外の場合も４乗すると１と合同になるのでしょうか？

次は$n=14$くらいでいってみましょう。

$a$としては、14と互いに素なもののみ観察すればよさそうです。

どうやら、

$a$が$10$と互いに素な時

$a^4 \equiv 1 (\mod10)$

と

$a$が$14$と互いに素な時

$a^6 \equiv 1 (\mod 14)$

は成り立ちそうです。

問題は、４と６は一体何者なの？

という話です。

実はここでオイラー関数が登場します。

$4=\phi (10)$

$6=\phi(14)$

だったのです！

ヤバくないですか？

つまり、

$a^{\phi(10)}\equiv 1 (\mod 10)$

$a^{\phi (14)}　\equiv 1(\mod 14)$

だったわけです

なんかすごいですよね！

一般に、次が成り立ちそう、という予想が立ちます

これがオイラーの定理です。

オイラーの定理の証明のアイデア

～脳内会議～

いつものことながら、どこから手を付ければよいのやらさっぱりです。

このような時は、定義に立ち返ることが一番。

まずはオイラー関数の定義に立ち返りましょう。

$\phi (n)$は

$1, 2, 3, 4,\cdots, n$のうち、$n$と互いに素なものの個数を表しています。

なので、

$1, 2, 3, 4,\cdots, n$のうち、$n$と互いに素なもの

だけ集めて集合をつくると、

元の個数は$\phi(n)$個となります。

$A_{\phi(n)}=\lbrace x_1, x_2, x_3, \cdots, x_{\phi(n)} \rbrace$

と置きましょう。

いきなり文字で置かれた集合を出されても分かりにくいので、

$\phi (10)$の場合を考えてみましょう。

１，２，３，４，５，６，７，８，９，１０

のうち、１０と互いに素なのは

１，３，７，９の４つです。

ゆえに

$A_{\phi(10)}=\lbrace 1, 3, 7, 9 \rbrace$

となります。

この場合、

$x_1=1, x_2=3, x_3=7, x_4=x_{\phi(10)}=9$

となっています。

さて。

$A_{\phi(n)}=\lbrace x_1, x_2, x_3, \cdots, x_{\phi(n)} \rbrace$

をもってきたら、次は何をしましょう？

定義に立ち戻ったら、

次のアクションは条件に着目です。

いま、$a$と$n$は互いに素です。

これをどう使うか、それが問題。

いま、$A_{\phi(n)}$を考えていますが、これは$a$と$n$のうち$n$に着目している状況です。

ここに$a$の情報も加えていきましょう。

いま$n=10$としているので、$a$は$10$と互いに素でなければなりません。

例えば$a=3$とすることとします。

$A_{\phi(10)}$と$3$を紐づけたいので、

$A_{\phi(10)}=\lbrace 1, 3, 7, 9 \rbrace$

の各要素を$3$倍した集合を$B$とおきます。

$B=\lbrace 1×3, 3×3, 7×3, 9×3 \rbrace$

$=\lbrace 3, 9, 21, 27 \rbrace$

これを$\mod 10$で考えてみます。

$3\equiv 3(\mod 10)$

$9 \equiv 9(\mod 10)$

$21 \equiv 1 (\mod 10)$

$27 \equiv 7(\mod 10)$

ヤバくないですか？

$A_{\phi(10)}=\lbrace 1, 3, 7, 9 \rbrace$

$B=\lbrace 1×3, 3×3, 7×3, 9×3 \rbrace$

$\equiv \lbrace 3, 9, 1, 7 (\mod 10)\rbrace $←この表し方は通常しません。このブログだけの表し方です。

順番が変わっているだけで、

$\mod 10$の世界では$A_{\phi (10)}$と$B$は同じものとみなせるのです！

どうしてこんな不思議な現象が起きるのか？

そこがオイラーの定理の証明の一番のポイントです。

これを示すには、$A_{\phi(10)}$の各要素と

$B$の要素を$n$で割った余りたちが

一対一対応することを示さねばなりません。

では、実際の証明を進めていきましょう！

オイラーの定理の証明

オイラーの定理

$a^{\phi(n)}\equiv 1(\mod n)$

について、$n=p$　（$p$は素数）を代入すると、

$\phi(p)=p-1$であることから

$a^{p-1}\equiv 1(\mod p)$

となり、フェルマーの小定理が得られます。

この意味で、オイラーの定理はフェルマーの定理の一般化と捉えることができます。

まとめ

いかがでしたか？

・$a^{\phi(n)} \equiv 1(\mod n)$

・オイラーの定理に$n=p$を代入するとフェルマーの小定理になる

・故にオイラーの定理はフェルマーの小定理の一般化

以上を押さえていただければと思います。

ではまた次回の記事でお会いしましょう！