こんにちは。Inishie Once-in-a-Lifetime Chanceブログのいにしえ時渡です。前回は、ドラゴンゲームのためのキーワードの説明をしました。それによると、一次合同式というa ≡ b (mod m)についての説明で、aとbは法mによって合同であり、a – b = myということでした。つまり、aとbはmで割った余りが同じであると言えるのです。
ここで、一つ説明を付け加えますが、myというのはmの倍数を表し、m=18であれば18yという数になります。ここで、yを使ったのは、基本的にそこに至るまでの式に同じアルファベットを意味する記号がなければ、好きな変数を使ってもいいということです。例えば、スゴく極端に言えば、18yを18時とおいてy=時としても、それで自分や見てもらう人にとって不便でなければ問題ないということです。
さて、フェルマーの小定理ですが、まずa x a x a=a^3という表し方を覚えておきましょう。aが3回掛かっています。フェルマーの小定理は、a^(p – 1) ≡ 1 (mod p)が成り立つことを意味します。少し難しい表現なので、実際に数値を代入してみましょう。p=7は素数とします。p=7をフェルマーの小定理の式に代入してみると、a^(7-1) = a ^ 6 ≡ 1 mod 7となります。a^6はaを6回掛けたことを意味します。
この前の復習として、mod 7は7を一つの周期として7で割った余りを求めるものです。つまり、a=0,1,2,3,4,5,6が候補として挙がり、a=7は、7で割ったら余りが0なので7 ≡ 0 mod 7となり、a=0とかぶるので除外します。マイナスの値も同じようにaの値に変換できます。
1 ^ (7 – 1) ≡ 1 ^ 6 ≡ 1 mod 7
2 ^ (7 – 1) ≡ 2 ^ 6 ≡ 64 ≡ 1 mod 7
3 ^ (7 – 1) ≡ 3 ^ 6 ≡ 729 ≡ 1 mod 7
4 ^ (7 – 1) ≡ 4 ^ 6 ≡ 4096 ≡ 1 mod 7
5 ^ (7 – 1) ≡ 5 ^ 6 ≡ 15625 ≡ 1 mod 7
6 ^ (7 – 1) ≡ 6 ^ 6 ≡ 46656 ≡ 1 mod 7
ここで、一つ注意しておく点は、a=0は何回0を掛けても0なので0^(7-1)=0となります。0を6回掛けても0です。つまり、mod 7 であれば、それより一つ少ない数(7-1)=6を指数としてもa=0以外は1になることがわかります。
ここで、電卓の使い方なのですが、109÷8の余りを計算してみたいと思います。まず、「１０９」「÷」「８」「＝」を代入します。電卓の画面には「１３．６２５」と表示されます。ここで、小数点より大きい整数、この場合では１３を引きます。「ー」「１３」「＝」。画面には「０．６２５」と表示されるので、元の割った値の８を掛けます。「ｘ」「８」「＝」と押すと画面には求めたい値の「５」が表示されます。この５は109÷8の余りとなります。検算すると(109-5)÷8=13余り0で正しい計算であったことが分かります。
次に、もう一つ念のためにこのフェルマーの小定理が正しいか確認しておきましょう。今度の数値は、mod9とします。
0 ^ 8 ≡ 0 mod 9
1 ^ 8 ≡ 1 mod 9
2 ^ 8 ≡ 4 mod 9
3 ^ 8 ≡ 0 mod 9
4 ^ 8 ≡ 7 mod 9
5 ^ 8 ≡ 7 mod 9
6 ^ 8 ≡ 0 mod 9
7 ^ 8 ≡ 5 mod 9
8 ^ 8 ≡ 1 mod 9
mod9の結果は散々でしたが、先程のmod7は7が素数でした。今回の9は3×3なので合成数となり、素数ではありません。ここで、mod9は1が2つですが、なぜでしょうか。まず9は互いに素であるか確かめてみましょう。互いに素とは最大公約数が1であることです。前回のドラゴンゲームの説明では、最大公約数とは16=2x2x2x2と24=3x2x2x2があるとき、両方の重なる部分のことを意味していました。つまり、24と16は2x2x2が互いに共通であるので、最大公約数は2x2x2=8となります。
ここまで書いてみて一次合同式とフェルマーの小定理を合体したところまで説明するとかなりの長文になりそうなので、今回の記事は、今、説明した互いに素と9の関係にふれて次回に持ち越したいと思います。おそらく僕もドラゴンゲームを利用し始めたばかりなので、感覚が鈍いですが、一つのキーワードにつき一記事、まとめとして一記事。今回は2つのキーワードを混ぜるので記事数2+1が良いと思います。さて続きと行きましょうか。
9までの値を順番に9と互いが素か確認していきましょう。
9と1は最大公約数が3×3と1なので1となります。まず、1つ目の最大公約数が1で互いに素★の値です。9と2は3×3と2なので互いに素★です。つまり、2個目の最大公約数が1の値です。9と3は3×3と3なので、最大公約数が3になって互いに素ではありません。4と5は互いに素★★です。6は2×3なので最大公約数が3になって互いに素ではありません。7と8は互いに素★★です。
よって、互いに素であるのは、1,2,4,5,7,8の6個です。ここで、9と互いに素な6つの数をφ（読み方：ファイ）で表して、オイラーのファイ関数と呼ばれています。
φ(9)=6となります。
先程の素数である7を使ったmod7は0以外互いに素なので6個の最大公約数が1の値が存在します。素数はφ(p) = p – 1で表します。
φ(7) = 7 -1 = 6
話は戻りますが、整数と整数の掛け算である合成数の9はa ^ φ(m) ≡1 mod mとなり、aとmは互いに素である必要はありますが、a ^ φ(9) = a ^ 6 =1 mod 9となります。
先程、1でなかった4と5を例に取ると、次のようになります。
4 ^ 6 ≡ 4096 ≡ 1 mod 9
5 ^ 6 ≡ 15625 ≡ 1 mod 9
6 ^ 6 ≡ 46656 ≡ 0 mod 9
7 ^ 6 ≡ 117649 ≡ 1 mod 9
ここで、6= 0 mod 9であるのは、6と9が互いに素でないからです。
僕が読んでいる数論の教科書にはこのフェルマーの小定理の説明が載っています。詳しく知りたい方はジョセフ・H・シルヴァーマン著『はじめての数論』を読んでみてください。
さて、次回は一次合同式とフェルマーの小定理を合成しますが、良ければ期待して待っていてください。僕は、一日掛けてこの2つのキーワードを合成したものを研究しましたが、チンハプニングがありました。乞うご期待。読んでくれてありがと
コメント