フェルマーの小定理は実は一般化できます。
この記事では、フェルマーの小定理を一般化するに至る思考プロセスを
具体例を基に丁寧に解説します。
丁寧に進めるぞ!という決意が記事の長さという形で出力されているので、
なんでそんな変形するの!?という部分を詳しく知りたい以外はブラウザバックしてください。
フェルマーの小定理のおさらい
前回は等比数列を合同式の視点で観察して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$を代入するとフェルマーの小定理になる
・故にオイラーの定理はフェルマーの小定理の一般化
以上を押さえていただければと思います。
ではまた次回の記事でお会いしましょう!
コメント