いう因子が残っているので)。連中、いかにややこしい形をしてようが実際に計算してやるまでもなく瞬殺できるザコキャラっす。n)ここまで来たらフェルマーの定理を手に入れたも同然でしょう。p)これでフェルマーの小定理は下の数が2について証明されました。1ずつ増加させながら数学的帰納法で楽勝です。ことは、既に分かっています。1pは1なんか何乗しても1だから1です。以下同様に、4=3+1の場合を考えると3の場合に帰着され、5を考えると4の場合に帰着され......となります。p)......こんなのはpが素数じゃなくても成り立ちます。0は何乗しようが0だし、何で割っても商は0余り0。以上によって、次の定理が得られました。割った形で参照されることが多いです。互いに素でなければいけません。と1以外の公約数を持つような(pとなれあった秘密の関係のある)数で割ったら、余りの計算が狂って≡が成り立たなくなってしまうからです。等式についても0で割ることは許されませんが、それと同じように合同式の場合は、法となれあった数で割ることは許されません。互いに素である「無関係」な数でなら割って良いです。(RSA暗号についての解説で、秘密の指数βを求めるとき互いに素であることを確認したりしてたのは、この点と関係あります。)フェルマーの定理の場合、この制限は、実際には難しい問題じゃありません。「どんな自然数でもp-1回かけあわせてpで割ると余りは1だ」ということ。(ただし、pは素数で、かけあわせる自然数とは互いに素。)以下の実例をみれば、だんだん納得がいくと思います。123という数と素数7を考えると、「123を6回かけあわせて7で割ったら余りは1」ということが、実際に計算しなくても予言できるわけです。1てなわけで、フェルマーの定理の通りです。定理の両辺から1を引くと、またおもしろいことが出てきます。11で割れてしまいます。1023=11×93。43046720この4304万6720という数は指数の16に1たした17で割り切れるはずです。実際、17×2532160です。9999この9が24個ならんだでかい数は13で割り切れる......はずです。指数の12に1たした13が素数ですからね。76923076923076923076923×13実例の研究フェルマーの定理は、「pを法とする世界で考えると、どんな数もp乗すれば自分自身に戻る」というようなことを意味しています。13で割ると余り5...上の各行の左端には3とか4とか5があって、右端には、ふたたびその左端の数が現れてます。このことを公開鍵暗号系のイメージと重ねると、エンクリプト変換とデクリプト変換の合成写像がちょうど上の計算になるようにエンクリプトとデクリプトをうまく定義すると、受信者は暗号化された文章をもとの文章に復元できることになるでしょう......あくまでイメージ的な説明であり、予備知識がないと、この説明では、かえって分かりにくと思います。詳しくは「高校数学で遊ぶ公開鍵暗号RSA」以下の一連の記事をみていただくとして、この計算は、「もとに戻ることが保証されている」ってところがミソです。解読が難しい暗号文を作っても元に戻せなければだれにも読めない無意味な暗号文になってしまいますからね。それはそれとして、aをp乗するとaに戻るってことは、p-1乗した時点での値は1と合同になっているわけです。p-1乗で1と合同なので、もういっかいaをかけるとaと合同になるってわけです。13で割ると余り1...どんな数でもp-1乗すると1と合同になるわけです。それがフェルマーの小定理の意味です。13で割ったあまりというのは、0~12の13通りがあるわけですけど、どんな数にせよ12乗したら余りが1になるのはそれとして、12乗よりもっと小さいべき乗で≡1になる可能性はないのでしょうか。可能性がないどころか、おおありです。なってしまうことのほうが多いです。13で割ると余り1ごらんのように、3乗した時点ですでに≡1です。1になってしまえば、それに元の数をかけると2乗のときと同じ話になって、以下同じパターンのループになります。3について、≡1になる最小指数は3です。このような最小指数は、必ずp-1の約数になります。整数回ループしてp-1の地点で≡1で着地するためには、ループの周期はp-1の約数じゃなければならないからです。「≡1になる最小指数がp-1の約数だ」というのはフェルマーの定理の系です。そんなことはどうでもいいのですが、逆に、p-1乗して初めて≡1になるようなケースもあるのでしょうか。13で割ると余り1残念ながら、p-1=12にいたる道の中間地点の6乗ですでに1になって、ループしてしまいます。13で割ると余り1ごらんのように、1~12乗するあいだに1~12のそれぞれに合同な数がもれなく重複なくちょうど1回ずつ現れました。このような性質を持つ2は、13を法とする原始根である、と言われます。生成することができます。原始根をめぐっては、おもしろい性質がいろいろあります。実際の計算の話としては、13を法としてp-1=12だとすると、6乗した時点で≡1にならなければ、その時点で原始根だと分かります。説明したように、≡1となる最小指数は12の約数なので6じゃないとしたら、もう12まで可能性は無いわけです。乗においては≡-1です。うえの例では、26≡12≡-1となっています。p-1乗したら≡1になることはフェルマーの定理から確定してます。乗のときは「2乗すると1になる数」じゃなきゃいけないってことです。(このことは厳密には証明を必要としますが、法が素数であるときは成り立つ)。-1"のような感じです......。原始根2を「底(てい)」とすることで、1~12のすべての数を生成できるわけですから、これらの数は、それぞれ「自分は2の何乗か?」という形で参照することもできます。13)"のような離散対数のようなものを考えることもできるでしょう......たとえば......この世界において、3と6の積を求めたいとしましょう。5このようにして、3と6の積がこの世界では5であることを知ることができます。3×6=18≡5(18を13で割ると余り5)と計算すると、たしかに一致します。いまやった計算は、104=10000と105=100000の積を求めるとき、実際に掛け算を行うことなく4+5=9であることから答は109だ、と計算するのと似ています。上記くらいの大きさの数では、このような「指数・対数」の計算が実用上べんりということはありませんが、こういうことができる、ってこと自体がちょっとおもしろい。どのような素数に対しても、それを法とする原始根は1つ以上存在します。このことは証明を必要とします。一般に、与えられた素数の最小原始根を求めるのは(手動でやるのは)面倒です。プログラミングをなさるかたは「原始根の表を作るスクリプト」を書いてみるとおもしろいかもしれません。この記事や関連するほかの記事では、「剰余類」と「余りの整数」をわざとあいまいに同一視しています。演算子の対象となる要素は本当は整数でなく抽象的な「類」です。類を「点化」して二項演算を入れているわけです。8+9≡4を厳密にいうと「8を含む類」と「9を含む類」に演算+をほどこした結果は「4を含む類」だ、ということですし、12≡-1を厳密にいうと「12を含む類」と「-1を含む類」は同じ要素の別名だ、ということです。nこのページに関するご連絡は、下記メールアドレスへお願いします。メールでのサポートはできませんので、質問がある場合、掲示板をご利用ください。このウェブサイトは、都合により、まもなく終了します。書いてあった情報は、特に断り書きがない限り、自由に使ってください。そのまま転載しても、書き換えたりして再利用してもかまいません。記事の中には情報が古くて現状と合っていないものや、不正確な点を含むものがあるかもしれません。修正が必要と思われる点がありましたら、お気軽にお知らせください。