…つ．また についてのフェルマーの小定理よりであり，合わせると より、 は を割り切る． は奇素数より は を割り切る．（証明終わり） 定理の実際の使い方を紹介しましょう。 として、 を を素因数に持つ極大超プーレ数とします。このとき、 の とは異なる素因数 は、定理によれば を割り切るわけです。 すなわち、 の素因数だけが「 を素因数に持つ極大超プーレ数」の素因数になる資格があるというわけです。実際、 を素因数分解するととなります。 あとは の素因数の中から、相異なるペアがす…

…の約数は であるが、フェルマーの小定理より も成り立つので、式 とあわせて が超プーレ数であることが示された。（証明終わり） 具体例を挙げたいのですが、現在知られているヴィーフェリッヒ素数は の２つだけです！したがって、上の定理１よりがどちらも超プーレ数であるということがわかります。実際が成り立ちます。ぜひ確認してみてください。 ・・・といって、確認するのはなかなか難しいでしょうから、Pythonだと次のように確認できます。 a = 2 m = 1093**2 x = pow…

…19年のことですが、フェルマーの小定理の逆に関する における最初の反例だったという訳です。じゃあなんで「サラス数」ではなくて「プーレ数」という名前がついているのかと疑問に思うかと思います。実は、Poulet（プーレ）さんは1926年に 以下のすべての擬素数を決定しているのだそうです。1938年には まで擬素数表を拡張したそうで、その意味で彼が研究した数ということでプーレ数と呼ばれるのだと思います。 さらにいえば、 は超プーレ数でもあります。実際、 の約数はの4つであることが直…

…られています。これはフェルマーの小定理から言えます。つまりというわけですね。ここで、さらにもう一度 で割ることを考えてみましょう。は一般に成り立ちませんが、これが成り立つような特別な素数をヴィーフェリッヒ素数といいます。 例： はヴィーフェリッヒ素数 はヴィーフェリッヒ素数 実は、ヴィーフェリッヒ素数はこの二つしか見つかっていません！ これ以上あるかどうかもまだ不明です。超レアな存在というわけですね！ このような素数が脚光を浴びたのは、またもや フェルマーの最終定理 です。ア…

…成り立つ、というのがフェルマーの小定理でした。 逆に、 を正の整数として、 未満の をランダムにいくつか取りがいずれの でも成り立たないのであれば、 は素数「だろう」と判定するのがフェルマーテストです。 が成り立つ が一つでもあれば、（フェルマーの小定理の対偶により）合成数であることが確定します。 一方で、フェルマーの小定理の逆任意の と互いに素な について は素数は必ずしも成り立ちません。たとえば、 という数は互いに素な任意の について条件を満たしますが、 となり素数ではあ…

…ない整数 について、フェルマーの小定理によりが成り立ちます。よって、 の位数は の約数となります。そこで、位数が に一致する特別な のことを の原始根と言います。 以上をまとめるとこうなります： の循環節の長さが が の原始根 今回の場合、「 が の原始根であるような素数 」を考えたいというわけですね。原始根を固定して素数を動かすイメージです（下図）。 が原始根であるような素数全体の集合を と呼ぶことにしましょう。 はいったいどのような集合なのでしょうか？ の素数を何かわかり…

…す素数 のことです。フェルマーの小定理により、一般にが成り立つことはわかりますが、１回だけでなくさらにもう１回 で割れるような素数のことをヴィーフェリッヒ素数と呼ぶわけですね。参考： integers.hatenablog.com なお、基数 のヴィーフェリッヒ素数は、今現在の３つが知られています。たまたま がフルサイクルだったというのが今回の状況だったというわけです。ちなみに、ヴィーフェリッヒ素数が無限にあるかどうかは、未解決問題です。 このように考えると、基数10のヴィー…

…と思います。 まず、フェルマーの小定理という、合同式を考える上で大変有用な定理から話を始めます。定理（フェルマーの小定理） を で割り切れない任意の整数とする。このときが成り立つ。 つまり、この定理は と互いに素な について、 が必ず で割り切れると言っているわけですね。 の剰余も十分面白いのですが、今回はさらに話を進めて の合同式を考えてみたいと思います。 これは、整数 を 進展開すると自然に出てくる発想です。 をと表せたとしましょう。フェルマーの小定理によりということなの…

…よりと表せる。また、フェルマーの小定理より である。 より が言えるので を得る。よって、 よりが得られる。したがって、 である。（定理1の証明終わり） ところで、定理1では「 の桁数 と割り切る素数 が一致する場合」を考えました。それ以外の の素因数 は、どのような形の素数になるのでしょうか。 となる素数 （）の条件を考えてみましょう。 なので自動的に であることに注意します。 のとき、次が言えます： よって、次の定理が示されました： 定理2 を素数とする。このとき、次が成…

…と を得ます。一方、フェルマーの小定理よりです。両辺 乗するとが得られ、再度 乗するとが得られます。繰り返し適用するとが得られます。 と を合わせると を得ますが、これは の仮定に反します。よって、 が示されました。 (ii) のとき： のとき を示します。 のとき であり、 よりこれは と同値です。 ここで、 と仮定すると、① であるか ② かつ であるかのいずれかです。①のとき、 より です。すなわち です。一方、①の条件から は偶数であり、これは であるから矛盾です。②…

…えます。この場合は、フェルマーの小定理より が成り立ちます。これを両辺 乗すると、指数が になります。 の場合は、一個前と同様なので とおくと 同様に、 かつ の場合は、 とおくととなり、 かつ の場合は、 とおくとが成り立ちます。結局、 を が割り切るかどうかのパターンに応じての4通りの値を取ることになります。 ここで、中国剰余定理により、以上の4通りそれぞれに対して、 が一意的に定まり、しかも相異なる数となります。したがって、 より は4通りの値を取る事が示されました。 …

…(ii) の場合： フェルマーの小定理よりである。両辺 乗するとであり、両辺 をかけてが成り立つ。したがって、 より が得られる。 以上 (i), (ii) の議論より、いずれの場合も である事がわかった。同様の議論を に対しても行うと、 がわかる。したがって、 は でも でも割り切れるので、が言えたことになる。すなわちが示された。（証明終わり） 類似例：カーマイケルの定理 実はカーマイケルの定理も、同様の事実を示す事ができます。カーマイケル数 の定義と、カーマイケルの定理は…

…と互いに素である。 フェルマーの小定理が適用できて が成立する。したがってであるが、これを満たす整数 は存在しない（ は法 の平方非剰余）。よって、矛盾が生じるから、①に整数解が存在するという仮定は誤り。②に条件を満たす整数解がないことの証明： ②に整数解があると仮定すると、 である。右辺が3の倍数より、 も3の倍数。したがって、 も3の倍数なので とおくとである。これに対し をとると、なる合同式が成立する。一方で、 の条件より、 は と互いに素である。ここにフェルマーの小定…

…です。したがって、 フェルマーの小定理を使うととなります。したがって合同式が得られますが、これは明らかに解を持ちません（ は の平方剰余なので）。したがって、元の方程式の整数解もないことになります。 以上により、①②には条件（☆）を満たす整数解がありませんので、 となります。したがってが言えました。 ランク r の決定： 以上により、 が分かりましたので、公式となり、ランクはであることが分かりました。つまり、 の無限位数の点は、ある1点によって生成されるということですね！ 続…

…つに合同」の意味）。フェルマーの小定理により で循環することに注意します。また、以下ずっと原始根 は同じものを固定します。 どちらのケースの も で割って あまるので、 は で割り切れます。よって 個の数を、以下の4つの剰余類に分類します： に属する数は、すべて で の形をした数であることに注意すると、今回の問題に関係しそうだということがわかります。 に属する任意の元 と に属する任意の元 の積 は、ある の元 が存在して と表せます。したがって、剰余類の間の積 がwell-…

…色々見えてきますね。フェルマーの小定理 を使いましょう。フェルマーの小定理は、整数の合同式における議論で頻繁に用いられる定理ですので、ご存じない方はこれを機にぜひ覚えていってください。フェルマーの小定理整数 と 素数 に対し、 と が互いに素であれば、次の合同式が成り立つ：つまり、 と互いに素な は、 で 乗すると と合同になるということですね。 今回の問題は、 を で 乗したとき に合同になるような は存在するかという問題でした。 のとき、 と は互いに素なので、 としてフ…

…みようと思います。 フェルマーの小定理っぽい？ まずは、具体的に計算していきましょう。以下すべて有限体 上で考えます。４行目あたりで「おっ」って思いますよね。結果だけまとめるとこれが繰り返されます。4回合成するごとに、 となっていることが観察できます。つまり、（恒等写像）が成り立つということです。 この現象はさながら フェルマーの小定理 のようです。フェルマーの小定理とは、 を素数として に対して が成り立つというものでした。状況はそっくりですね。しかも、今回は 上の多項式を…

…乗法群なので、群論のフェルマーの小定理により、 に対して が成り立ちます。したがって が言えました。両辺に をかけると が成り立ちます。よって、左辺と右辺の差 は で（少なくとも） 回割れるとわかるので が言えます。よって、式 が成り立ち、 が のコーシー列であることが示せました。（証明終わり） 少し長かったですが、これにて が の元に収束することが示せました。これで問題は半分くらい解決です。 を示す これまでの議論で は示せました。最後に を示して終わりましょう。 を考察し…

…義されます。有限体のフェルマーの小定理を考えると、これは明らかに の元を固定することがわかります。フロベニウス作用素は、このフロベニウス自己同型を、そのまま曲線 の座標に適用させる作用素で、 と表します。 フロベニウス作用素 は絶対ガロア群 の生成元になっていることから、 の作用を考えれば、 の作用がすべてわかることになります。先ほどのロジックで、 の代わりに、コホモロジー を考え、 に対する の作用、すなわち行列を考えている、というのがこの式の意味するところです。 長かった…

… のことです。群論のフェルマーの小定理より，群 の任意の元は 乗すると単位元になりますが，位数と指数は一致するとは限りません。 tsujimotter.hatenablog.comたとえば， は指数 ですが， も指数 です。この場合は，位数は になりますね。逆に，指数 のアーベル拡大 があったとすると， として が得られます。 は「 の 乗数」かつ「 の数」であるような数です。 は の元を含みますから，上の集合は の 乗数を含みます。 の 乗数以外で， 乗して になる の数は…

…は，倍数の判定なら「フェルマーの小定理」だろう，と思ってそればかり考えていたのですが・・・。中途半端な知識は，人を頭でっかちにさせることもあるのですね。気をつけないと。フェルマーの小定理といえば「循環小数」関連の話題も面白いです。よかったらこちらもご覧になってください。 tsujimotter.hatenablog.com 最後に，もう一つ重要な事実を指摘しておきたいと思います。この判定法を教えてくれた方は「s(数学)k(くそほど)d(できない) 」というスクリーンネームの方…

…す素数 のことです。フェルマーの小定理により，mod において と互いに素な に対しが成り立ちますので，さらに のときを考えたものがヴィーフェリッヒ素数といえます。mod を考えると，mod を考えたくなるのは，数論においてはよくあることなのだそうです。 ヴィーフェリッヒ素数は，フェルマーの最終定理に関連していることでもよく知られていますね。 integers.hatenablog.com ヴィーフェリッヒ素数が，カタラン予想にどうつながるのかを，エッセンスだけお伝えしましょ…

…回投稿したばかりの「フェルマーの小定理」と非常に縁が深いのです。これはよいタイミングだなと思いましたので、今回はカーマイケル数についてご紹介したいと思います。 フェルマーの小定理，オイラーの定理（復習） まず、フェルマーの小定理の復習です。フェルマーの小定理といっても、前回ご紹介した群論的な方です。 tsujimotter.hatenablog.com （群論的な）フェルマーの小定理 を（有限の要素をもつ）群としたとき， に対して，以下が成り立つ．ただし， は の単位元． 任…

…りの記事のテーマは「フェルマーの小定理」です。フェルマーの小定理と言っても、よく知られるような数論的なものではなく、群論的 なフェルマーの小定理の類似物です。実は、フェルマーの小定理は群論的にも考えることができるんです。しかも、その証明の方法が巧妙で面白い。 今回の記事は、群論をちょっとだけかじったことがある、少し前の私のような人を想定した記事です。知らない人にはちょっと難しいかもしれませんが、雰囲気だけ追ってもらって、数学的な発想の面白さを共感してもらえたら嬉しいです。 な…

… とおきます。群論のフェルマーの小定理より，両辺に をかけて，が成り立ちます。したがって の元は によって不変です。また， は明らかに不変なので， が を固定することがわかりました。 話を代数体に戻すと， によって と が同型です。したがって， もによって生成される巡回群になります。 いやぁ，すごいですね！ 群の対応関係のイメージはこのような感じでしょうか。 ここから不分岐に限定した話をします。不分岐の場合は がつぶれるので，に対応する の元がただ１つ定まります。この元ただ１…

…に注意してください。フェルマーの小定理より，が成り立ち，以降は同じ数が繰り返し現れるためです。 少し用語を整理しておきましょう。 を整数としたとき， における同値類を剰余類と呼び，その集合を と表記します。また のうち， と互いに素である剰余類を既約剰余類といい，その集合を と書きます。 が素数のとき， には を除く より小さいすべての元に対応した剰余類が入ります。また， は乗法について群をなすことが知られています。したがって，これを 既約剰余類群ともいいます。一方， は加法…

…。これは群論におけるフェルマーの小定理です。つまり、 における の属する類を とすると、以下が成り立ちます。 の単位元は、単項イデアルの属する類 ですね。 一方 式より、 は単項イデアルです。したがって、となるでしょう。 さぁここで、 が正則素数 なら、すなわち が を割り切らないのであれば、 と は互いに素 です。互いに素な２整数に対しては、ユークリッドの互除法より、となるような整数 が存在します。よって、が成り立ちます。 を 式に代入することにより、が得られます。すなわち…

…★☆☆☆） 方法３：フェルマーの小定理を使う（難易度：★★★☆☆） 方法４：平方剰余の相互法則を使う（難易度：★★★★★） 単に解法を紹介するだけでなく、問題へのアプローチを通して、tsujimotter が思う整数論の魅力も併せてお伝えできればと思っています。 書き終わった今改めて読み返してみると、書きたいことがあまりにも多すぎて、文章がとてつもなく長くなっています。このへんは反省しないといけませんね。 とはいえ、どれも伝えたいことですし、できるだけわかりやすく丁寧に書いた…

…類環」の中で起きる「フェルマーの小定理」「原始根定理」「オイラーの基準」「平方剰余の相互法則」といった一見小難しい定理群を、「時計の世界」という言葉を一貫して使って平易に解説することを目指した発表になっています。実は、上の文面は、佐野さんのレポートのほぼ丸写しなのですが、改めて考えると上のように集約されるような内容の話をしていたのです。他の人にレポートをまとめてもらうと、気づかされることが多いので面白いですね。あと、今回は新しい試みとして「配布資料」を作りました。スライド内の…

…が素数であるときは、フェルマーの小定理と関連しますから、この結果は非常に重要です。 が２つの素数の積で表される数のとき さて、最後です。 が という２つの素数の積で表される数のときを考えましょう。すなわち、この状況は、RSA 暗号で重要な役割を果たしましたね。 さて、先ほどと同様に より小さい数を考えると、それは の 個です。 ここで、 より、上で挙げた数が素因数 と を約数に持つかを考えます。 を素因数に持たない数が、私たちが求める と互いに素な数です。 イメージしやすいよ…