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

オイラーの定理(数論)

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

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

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

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

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

目次

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

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

具体的には、

$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)$

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

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

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

$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$の場合

$1 \equiv 1(\mod 10)$

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

$3 \equiv 3, $ $3^2 \equiv 9,$ $3^3 \equiv 7 ,$ $3^4 \equiv 1(\mod 10)$

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

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

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

$7 \equiv 7,$ $7^2 \equiv 9,$ $7^3 \equiv 3,$ $7^4 \equiv 1 (\mod 10)$

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

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

ふむ。

1が出てくるのはどうやら結構レアなようですね。

最後が1になっている奴だけ拾い出してみると、

$3^4 \equiv 1(\mod 10)$

$7^4 \equiv 1(\mod 10)$

$9^4 \equiv 1 (\mod 10)$

なんか全部4乗じゃね?

あと、3,7,9は全て10と互いに素です。

$n=10$以外の場合も4乗すると1と合同になるのでしょうか?

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

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

$n=14$のとき

$1\equiv 1 (\mod 14)$

$3 \equiv 3,$ $3^2 \equiv 9,$ $3^3 \equiv 13,$ $3^4 \equiv 11,$ $3^5 \equiv 5,$ $3^6 \equiv 1(\mod 14)$

あぁ!4じゃない。

今回は6乗で1になるようですね。

念のため$a=5$も確認しておきましょうか

$5 \equiv 5,$ $5^2 \equiv 11,$ $5^3 \equiv 13,$ $5^4 \equiv 9$ $5^5 \equiv 3,$ $5^6 \equiv 1(\mod 14)$

やはり6乗のようです。

どうやら、

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

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

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

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

は成り立ちそうです。

問題は、4と6は一体何者なの?

という話です。

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

$4=\phi (10)$

$6=\phi(14)$

だったのです!

ヤバくないですか?

つまり、

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

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

だったわけです

なんかすごいですよね!

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

$a$と$n$が互いに素なとき、

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

となる。

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

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

(オイラーの定理)

$a$と$n$が互いに素なとき、

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

となる

~脳内会議~

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

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

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

$\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)$の場合を考えてみましょう。

1,2,3,4,5,6,7,8,9,10

のうち、10と互いに素なのは

1,3,7,9の4つです。

ゆえに

$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$と$n$が互いに素な整数であるとき、

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

が成り立つ

(証明)

1からnまでの整数のうち、$n$と互いに素であるものだけを集めた集合を

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

とおく。

定義より、$A_{\phi(n)}$の要素は$n$を法として全て異なる値をとる$\cdots ①$

ここで、$A_{\phi(n)}$の各要素を$a$倍した集合を$B$とする。

$B=\lbrace ax_1, ax_2, \cdots, ax_{\phi(n)} \rbrace$

ここで、$B$の要素で、

$ax_i\equiv ax_j (\mod n)$となるものが存在したと仮定する。

すると、$a$と$n$が互いに素であることから、両辺を$a$で割ることができ、

$x_i \equiv x_j$となってしまう$\cdots ②$←単射性

しかし、これは①に矛盾。

よって、$B$の要素は$n$を法として全て異なる値をとる。

ここで、$B$のすべての要素$ax_i$に対して、

$ax_i\equiv x_j(\mod n)$

となる$x_j \in A_{\phi(n)}$が存在することを示す。

いま、$a$と$x_i$は$n$と互いに素であるので、$ax_i$も$n$と互いに素である。

したがって、$ax_i$を$n$で割った余りは0になりえない。

この余りを$x_j$とおく。

ユークリッドの互除法より、

$ax_i$と$n$の最大公約数は

$n$と$x_j$の最大公約数に等しい。

故に、①より$x_j$は$A_{\phi(n)}$に含まれていなければならない。

よって、$B$のすべての要素$ax_i$に対して、

$ax_i\equiv x_j(\mod n)$

となる$x_j \in A_{\phi(n)}$が存在する$\cdots ③$←全射性

②と③より、$n$を法として考えると、

$A_{\phi(n)}$と$B$は要素の順番を入れ替えたものとして捉えることができる

したがって、$A_{\phi(n)}$の$\phi(n)$個の要素を全てかけ合わせたものと、

$B$の$\phi(n)$個の要素を全てかけ合わせたものは、

$n$を法として合同であり、

$ax_1×ax_2×\cdots ×ax_{\phi(n)} \equiv x_1×x_2×\cdots ×x_{\phi(n)}(\mod n)$

$a^{\phi(n)}×x_1x_2\cdots x_{\phi(n)}\equiv x_1x_2\cdots x_{\phi(n)} (\mod n)$

$x_1x_2\cdots x_{\phi(n)}$と$n$は互いに素であるので、両辺を$x_1x_2\cdots x_{\phi(n)}$で割ると、

$a^{\phi(n)} \equiv 1(\mod 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$を代入するとフェルマーの小定理になる

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

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

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

ブログランキング参加してます

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

CAPTCHA


目次