メモ（数論7）: 素数の無限

チラ裏　＞　数論　＞　メモ7

「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです。誤字脱字・間違いがあるかもしれません。

小学生の「フェルマーの小定理」　身近な曜日の話題から

• 2022-05-31　数えてびっくりガウス素数　100以下の素数は25個だが…
• 2022-06-03　数えてびっくりガウス素数（2）　素数レースはイカサマだらけ
• 2022-06-09　数えてびっくりガウス素数（3）　チェビシェフ・バイアスからの逆算
• 2022-06-12　「2・4・6・8・10・12・14日」は曜日が違う　フェルマーの小定理への道①
• 2022-06-14　パラレルワールドの足し算・掛け算　フェルマーの小定理への道②
• 2022-06-17　パラレルワールドの割り算　フェルマーの小定理への道③
• 2022-06-24　小学生の「ユークリッドの補題」　フェルマーの小定理への道④
• 2022-06-28　フェルマーの小定理で遊んじゃえっ！　小学生の「フェルマーの小定理」
• 2022-08-16　パラレルワールドの割り算 Part 2
• 2022-06-29　フェルマーの小定理のスパイシーな話題　4k+1型素数は無限個
• 2022-07-01　Hardy & Wright の古典的名著　その魅力と短所
• 2022-07-03　4k+1型素数の無限　Hardy & Wrightバージョン
• 2022-07-04　4k+1型素数の無限（続き）
• 2022-07-05　何となくフラクタル　3k+1, 9k+1, 27k+1…型素数の無限
• 2022-07-06　何となくフラクタル（続き）
• 2022-07-09　5k+1型素数の無限　再び素数レースのイカサマ
• 2022-07-11　乗乗の奇妙な冒険　「2 の乗乗は 2 と合同」
• 2022-07-15　乗乗の奇妙な冒険（その2）　数値例
• 2022-07-17　春素数と秋素数　高木の逆襲？

2022-05-31　数えてびっくりガウス素数　100以下の素数は25個だが…

2, 3, 5, 7 などの普通の素数は数直線上にある。ガウス素数は複素平面上にある。当然、後者の方が多いように思えるが、本当にそうだろうか？

【1/4】　100以下の素数は25個、200以下の素数は46個だが、単数倍の違いを無視すると、ノルム100以下・200以下のガウス素数もそれぞれ25個・46個。

えっ、ガウス素数って、普通の素数と同じ個数なの？！

そうとは限らないんだけど、上の数え方の場合、両者は近い数値になり、一致することもある。400以下の素数は78個だが、ノルム400以下のガウス素数は79個。この場合、ガウス素数の方がちょっと多い。500以下の素数は95個だが、ノルム500以下のガウス素数は93個。この場合、ガウス素数の方がちょっと少ない。

多少の誤差はあるにせよ、2次元的に散らばってる複素素数が、1次元の普通の素数と同じくらいの数しかないとは、びっくり！

【2/4】　10以下の素数は4個（2, 3, 5, 7）。ノルム10以下のガウス素数も4個。

具体的に数えてみよう。

まずノルム2のガウス素数。2 = (1 + i)(1 − i) だが、これは「ラミファイド」（因子が互いに単数倍の関係）なので、単数倍の違いを無視すると 1 + i と 1 − i は同じ1個のガウス素数。

次にノルム5のガウス素数。5 = (2 + i)(2 − i)。これは「スプリット」（因子が互いに単数倍の関係ではない）なので、2 + i と 2 − i は別々の2個のガウス素数。

これで計3個見つかった！　あと1つは何だろ？

「ラミファイド」は 2 だけだし、「スプリット」されるためには 4k+1 型の素数（バニラ素数）でなければならない。2番目に小さなバニラ素数は 13 なので、「ノルム10以下」という制限を超えてしまう。

残された唯一の可能性は「イナート」な素数、つまり 4k+3 型（チョコレート素数）。このタイプの素数は、ガウス整数としてもそのまま素数になるのだった。そしてガウス素数としての 3 は
　　norm(3) = norm(3 + 0i) = 3² + 0² = 3² = 9
なので、ぎりぎり「ノルム10以下」の範囲に入る。

ノルム10以下のガウス素数（4個）　1 + i, 2 + i, 2 − i, 3

単数倍の違いを区別するなら、それぞれ ±1倍、±i倍 のオプションがあるので、個数は4倍の16個になる！

【3/4】　この考え方を整理すると…。ノルム n 以下のガウス素数を数えるには、まず n 以下のバニラ素数を数えればいい。それが a 個だとすると、その一つ一つがスプリットされて2個のガウス素数に分裂するのだから、2a 個のガウス素数が生じる（単数倍の違いまで区別するなら 8a 個）。

一方、チョコレート素数だが…。チョコレート素数 q のノルムは q² なので、ノルム n 以下の範囲に限るのなら q² ≤ n つまり q ≤ √n の範囲のチョコレート素数を数えればいい。それが b 個だとすると、そこから b 個（単数倍の違いまで区別するなら 4b 個）のガウス素数が生じる（チョコレート素数は2個に分裂せず、普通の素数がそのままガウス素数になるので、個数が2倍にならない）。

最後に「ラミファイド」素数 1 + i をお忘れなく！　n が2以上である限り、必ずこれがあるので、ガウス素数の個数はあと1つ（単数倍の違いまで区別するなら4つ）増える。

ノルム n 以下（ただし n は2以上）のガウス素数の個数 = 2a + b + 1　ここで a は n 以下のバニラ素数の個数、b は √n 以下のチョコレート素数の個数。

〔例〕　ノルム100以下のガウス素数の個数。100以下の素数25個のうち、バニラ素数（4で割って1余る）に v 印を付けると…

2,  3,  5v, 7,

11,  13v, 17v, 19,
     23,       29v,
31,       37v,

41v, 43,  47,
     53v,      59,
61v,      67,

71,  73v,      79,
     83,       89v,
          97v

…11個あるので a = 11。一方 √100 = 10 以下のチョコレート素数（4で割って3余る）は、3 と 7 の2個、つまり b = 2。だから求める個数は:
　　2a + b + 1 = 2 × 11 + 2 + 1 = 25

4で割った余りが分かりにくいときは、適宜 20, 40, 60, or 80 を引いてから判断してもいい。例えば 73 は 60 を引くと 13、この数を4で割ると1余ることは簡単に分かる。もし3桁以上の数（例＝389）なら、下2桁だけを考えればいい（例＝389の下2桁は89で、80を引くと9なので、4で割ると1余る）。

【4/4】　n が4以上のときは、次のように少し簡単化することもできる。

ノルム n 以下（ただし n は4以上）のガウス素数の個数 = 2a + b　ここで a は n 以下のバニラ素数の個数、b は √n 以下の非バニラ素数の個数。

くどいようだが、これらのカウントは「単数倍の違いを無視した場合」。無視しないなら、個数は4倍になる。

Ramified, split, inert ――無味乾燥な概念のようだが、「素数が何個あるか数える」といった単純なことにまで、もろに影響してきやがる。日本語では ramify が「分枝・分岐」、inert が「惰性」だったと思うが split の正式訳語は何だろ…。教科書の用語はどうせ分かりにくいので、「奇妙に砕ける、普通に砕ける、砕けない」とでも呼ぶことにしよう:
　　〔教科書的？表現〕
　　　　ℤ[i] では、2 は分枝（分岐？）し、5 は分解し、3 は惰性的。
　　〔平明な言い換えの例〕
　　　　ガウス整数の世界では、2 は奇妙に砕け、5 は普通に砕け、3 は砕けない。

5 = (2 + i)(2 − i), 13 = (3 + 2i)(3 − 2i), 17 = (4 + i)(4 − i) などは普通に砕けて（2個の因子に分解されて）いるが、
　　2 = −i(1 + i)²
は奇妙に砕けている（因子に「重複」がある）。一方、3 は砕けない――ガウス素数の積として、
　　3 = (○ + □i)(○ − □i)
のような形で書くことはできない。同様に 7, 11 などは砕けない。（続く）

2022-06-03　数えてびっくりガウス素数（2）　素数レースはイカサマだらけ

前回、ノルム100以下のガウス素数の個数を数え、25という値を得た（単数倍の違いを無視）。これは100以下の普通の素数の個数と同じ。

同様に考えて、ノルム1000以下のガウス素数の個数を数えると、167。これは1000以下の普通の素数の個数168と、ほとんど同じだ。

「ノルム n 以下のガウス素数の個数は、だいたい n 以下の普通の素数の個数と等しいんだな」と予想したくなる。数値的にこの仮説を検証してみる。

n=10^1 : G(n)=4, S(n)=4 : (0)
n=10^2 : G(n)=25, S(n)=25 : (0)
n=10^3 : G(n)=167, S(n)=168 : (-1)
n=10^4 : G(n)=1232, S(n)=1229 : (+3)
n=10^5 : G(n)=9601, S(n)=9592 : (+9)
n=10^6 : G(n)=78438, S(n)=78498 : (-60)
n=10^7 : G(n)=664586, S(n)=664579 : (+7)
n=10^8 : G(n)=5761628, S(n)=5761455 : (+173)

例えば 10^3 は 10³ = 1000 のこと。G(n) はノルム n 以下のガウス素数の個数。S(n) は n 以下の（普通の）素数の個数（S は Sosū のイニシャル）。丸かっこ内は、両者の差 G(n) − S(n)。多少の誤差はあるが、近似的に G(n) = S(n) と考えても良さそうだ。

これは、とても不思議な現象だ。

【1】　まず最も素朴な観点として、2次元の複素平面上に散らばっているガウス素数が、1次元の数直線上の素数と同じくらいの個数…というのは、不思議な気がするかもしれない。

100以下の素数は25個だが、原点を中心に半径100の円を描けば、この大きな円の内にあるガウス素数は、25個よりはるかに多い（単数倍の違いを無視しても1000個以上ある）。一方、ノルムは距離の2乗なので、「ノルム100以下のガウス整数」とは、原点を中心にする半径10の円内にあるガウス素数。この円の面積は約314。しかも、単数倍の違いを無視することは、円を4等分した扇形の中だけを考えることに当たる。数直線の100以下と大ざっぱに「同じくらい」の範囲。

ガウス素数の個数が「意外と少ない」と感じられた一つの原因は、原点からの「距離」ではなく、ノルムを基準に範囲を指定したことだった。分かり切ったことかもしれないが…。

【2】　さて、2以上の整数 n を選択したとしよう。前回の考察によれば、ノルム n 以下のガウス素数の個数を G(n) とすると:
　　《ア》　G(n) = 2V(n) + C(√n) + 1
…ここで V(x) と C(x) は、それぞれ x 以下のバニラ素数・チョコレート素数の個数。

一方、n 以下の普通の素数の個数を S(n) とすると、次が成り立つ（右辺では、素数をバニラ、チョコレート、偶素数に分けて数えている）:
　　《イ》　S(n) = V(n) + C(n) + 1

直観的には、奇素数がバニラ（4で割って1余る）になるかチョコレート（4で割って3余る）になるかはランダムな現象で、特に「どちらかになりやすい」ことはない…ように思える。実際、素数定理というものによって、n が大きくなるとき V(n) も C(n) も同じ値 x / (2 log x) に近づくことが、保証されている。身近な100以下の素数で考えても、V(100) = 11 と C(100) = 13 は、だいたい等しい。従って
　　《ウ》　近似的に　C(n) = V(n)
これを《イ》に代入すると
　　《エ》　近似的に　S(n) = V(n) + V(n) + 1 = 2V(n) + 1

《ア》と《エ》を比較すると: G(n) と S(n) が近似的に等しいわけない。G(n) の方が C(√n) の分だけ大きいはず！

計算上はそうだが、現実の数値を観察すると G(n) と S(n) はほぼ等しい。一体どうなってるんだ？

【3】　すぐに思い付く作業仮説は「C(√n) は無視できるような小さな数なんじゃないの？」ということだろう。その可能性を検討するため、C(√n) の値を角かっこに入れて付記してみる。

n=10^1 : G(n)=4, S(n)=4 : (0) [1] -1
n=10^2 : G(n)=25, S(n)=25 : (0) [2] -2
n=10^3 : G(n)=167, S(n)=168 : (-1) [6] -7
n=10^4 : G(n)=1232, S(n)=1229 : (+3) [13] -10
n=10^5 : G(n)=9601, S(n)=9592 : (+9) [34] -25
n=10^6 : G(n)=78438, S(n)=78498 : (-60) [87] -147
n=10^7 : G(n)=664586, S(n)=664579 : (+7) [225] -218
n=10^8 : G(n)=5761628, S(n)=5761455 : (+173) [619] -446
n=10^9 : G(n)=50848691, S(n)=50847534 : (+1157) [1708] -551
n=10^10 : G(n)=455051359, S(n)=455052511 : (-1152) [4808] -5960
n=10^11 : G(n)=4118054228, S(n)=4118054813 : (-585) [13667] -14252
n=10^12 : G(n)=37607888003, S(n)=37607912018 : (-24015) [39322] -63337
n=10^13 : G(n)=346065532257, S(n)=346065536839 : (-4582) [113890] -118472
n=10^14 : G(n)=3204941899743, S(n)=3204941750802 : (+148941) [332398] -183457
n=10^15 : G(n)=29844570447060, S(n)=29844570422669 : (+24391) [976091] -951700

《ア》《エ》の比較によれば、G(n) − S(n) は、角かっこ内の数値 C(√n) にほぼ等しくなるはず。けれど、この差は実際には丸かっこ内の数値であり、予期される値よりかなり小さい（右端の負の数がこのずれを表す）。n が大きくなるにつれて、ずれも大きくなり、偶発的な誤差の範囲ではないようだ。

相対的な割合でいえば、G(n) や S(n) が大きくなる速度（n が10倍になるとき、ざっと1桁増える）に比べて、C(√n) が大きくなる速度は小さいので、無限のかなたでは、結局ずれを無視できるだろう。

けれど n = 100, 1000, 10000 などの比較的小さい数に対しては、C(√n) は、G(n) や S(n) と比べてざっと1%～10%くらいの大きさであり、無視できない影響があるはずだ。

にもかかわらず、実際の数値は「G(n) の方が S(n) よりおよそ C(√n) だけ大きいはず」という理論に反して、むしろ G(n) の方が小さくなるケースさえ散見される。絶対何かおかしい！

【4】　実は、ランダムに見える素数の分布には、ある種の「イカサマ」が存在している。具体的には《ウ》の
　　近似的に　C(n) = V(n)
という主張の解釈に問題が…。確かに n が限りなく大きくなるとき C(n) と V(n) は五分五分になるが、実際には n を選んで C(n) と V(n) を比べると、C(n) > V(n) になっている可能性が高い。

これは直観に反する現象だ。トータルでの個数の分布は五分五分のはずなのに、n を選んで「チョコレート素数チーム」と「バニラ素数チーム」がメンバー数を比較してみると、大抵は「チョコレート素数チーム」が勝つ。確率に似たある尺度を使うと、約99.5%の場合、チョコレート素数チームが優位になる。素数を4で割って余りが1か3かで勝負する「素数サイコロ」には、あたかも微妙に3が出やすくなるかのような、細工が施されている！

身近な100以下の素数における C(100) = 13, V(100) = 11 にも、既にこの微妙な偏りが忍び込んでいる。

この偏りをチェビシェフのバイアス、別名素数競争と呼ぶ。

バニラとチョコの個数の違いについては、19世紀ロシアの数学者チェビシェフが、ある人に宛てた手紙の中で最初に指摘したらしい。「素数の数についての新しい定理」というような題名で、フランス語の論文が発表されたようだ。

上の表・右端の −1, −2, −7, −10, −25, … は、まさにこのバイアスが検出されたもの。

「n が巨大になるとやがて五分五分になるけど、n が小さいときは、たまたまチョコレートが多いのだろう」と思いたくなるかもしれない。

ところが n が巨大になっても、上記の「99.5%チョコレート側が有利」という偏りは永遠に解消されない。偏ってるのに、チョコレート素数とバニラ素数の存在密度は五分五分なんだよね…不思議でしょ？

あ…ありのまま　今起こった事を話すぜ！
「おれは　五分五分と証明された個数を数えていた
と思ったら　いつも同じ片方の側が多かった」
何を言っているのかわからねーと思うが
おれも　何が起きたのかわからなかった…

本当に「サイコロが細工されている」のなら、無限に試行を続ければ結果は五分五分にならず、必ず偏りが発覚する。ところがこの場合、無限に続けると五分五分になるのだから、サイコロに細工はない（？）はず。なのに、何度試しても特定の目が出やすいように感じられる（実際にある種の偏りがある）。

一方、例えば n = 26861 を選択すると C(n) = 1472, V(n) = 1473 となり、バニラチームが勝つ。100%チョコレート側を勝たせるような「単純なイカサマ」でもない。

【5】　これだけでもびっくりだが、同様の「イカサマ」は素数分布の至る所に仕込まれている。例えば、1000以下の素数を「4で割った余り」で分類すると、余り1が80個、余り3が87個…。目立たない程度に、だがあからさまに、「余り1」側が冷遇されている。では、同じ1000以下の素数を「3で割った余り」で分類すると、どうなるか。余り1が80個、余り2が87個（4で割ったときとほぼ同じ結果）。やはり「余り1」側が不利になるような、何かの仕掛けがある…。素数レースは、平方剰余が非剰余より不利になるように「仕組まれている」のだ！

なぜこんなことが起きるのだろうか？　本質的な理由は、今のところ誰にも説明できない。というのも、これは「一般化されたリーマン仮説」という未解決の難問と、結び付いているので…。「とある関数 f(x) が f(x) = 0 になるような入力 x は、非常に特徴的なパターンを持っているようだが、なぜだろうか？」ということを知りたい。パターンがあるなら、そのパターンが生じる原因があるはずだ。ところが、その「なぜ」を説明する以前に「その一定パターンが本当にある」という証明すらできていない。けれど「素数の分布はランダムではなく、非常に深いところに、隠された規則がある」ということは確からしい。

この現象を感覚的にイメージすることは、難しくない。プラスの側から緩やかに0に近づく曲線と、マイナスの側から緩やかに0に近づく曲線を思い浮かべてみよう。どちらも漸近的には 0 だが、途中のどこで両者を比べても、プラス側の方が大きい。この2本の曲線に不規則なでこぼこを付加して、まれに上下が逆転する場所もあるようにしてみると…。C(n) と V(n) の挙動は、大ざっぱには、そんな感じだろう。

バイアスは、C(n) と V(n) のどちらが大きくなりやすいか？に関するもので、直接的に「チョコレート素数はバニラ素数より多い」という意味ではないし、「ランダムに選んだ素数はチョコレートである確率が高い」という意味でもない。あたかもそう感じられることも、あるだろうけど…

「素数の個数を数える」といった「たわいもないこと」でも、隅々まで検討すると、意外な事実が出てくるものだ！

文献
- Andrew Granville, Greg Martin: Prime Number Races (2004)　初等的・総合的な紹介
https://arxiv.org/abs/math/0408319
- Daniel Pareja: Prime Number Races　数学専攻の学生向け
https://www.math.ubc.ca/~gerg/teaching/613-Winter2011/PrimeNumberRaces.pdf
- Michael Rubinstein and Peter Sarnak: Chebyshev’s Bias (1994)　ブレークスルーとなった論文
https://projecteuclid.org/journals/experimental-mathematics/volume-3/issue-3/Chebyshevs-bias/em/1048515870.full
- Marc Deléglise, Pierre Dusart, and Xavier-Francois Roblot: Counting primes in residue classes (2004)
https://www.ams.org/journals/mcom/2004-73-247/S0025-5718-04-01649-7/home.html
- Adel Alamadhi, Michel Planat, Patrick Solé: Chebyshev’s bias and generalized Riemann hypothesis (2011)
https://hal.archives-ouvertes.fr/hal-00650320

2022-06-09　数えてびっくりガウス素数（3）　チェビシェフ・バイアスからの逆算

前回の続き。

【1】　ノルム x 以下のガウス素数の個数（単数倍の違いを無視）を G(x) とすると:
　　G(x) = 2V(x) + C(√x) + 1

x = 10ⁿ (n = 1, 2, …, 16) に対する G(x) の値は https://oeis.org/A091100 に載っている（単数倍の違いを無視せずに、4倍された値）。

x = 10¹⁸, 10²⁰ に対する G(x) の値は https://oeis.org/A091134 の第9項・第10項に当たる。

実質的に欠けているのは、A091100 の n = 17, 19。これを求めよう。V(x) は https://oeis.org/A091098 に、C(x) は https://oeis.org/A091099 に、それぞれ与えられているが、x が10の奇数乗の場合の C(√x) は自力で計算するしかなさそうだ。10¹⁷ についてベタでやってみる（PARI）。

c=0; forprime(p=2, sqrt(10^17), if(p%4==3,c++)); c

3秒ほどで 8541578 が返った。すると…
　　G(10¹⁷) = 2 × 1311778575685086 + 8541578 + 1 = 2623557159911751　「ア」

PARI の forprime は良い考えだったのだろうか。次のようにすると、どうなるか。

c=0; forstep(q=3, sqrt(10^17), 4, if(isprime(q),c++)); c

同じ答えが出たが、20秒以上かかってしまった！　forprime は9桁くらいの数に対しては、非常に速いようだ。

他方、10桁くらいの数に対する下記の検索では forstep の方が圧倒的に速い。環境にもよるだろうけど、やはり一般論として、算術級数中の素数を抜き出したい場合、forprime で全部の素数をたどるのは損になる。
c=75939612; forstep(p=3162277691, 10^10, 4, isprime(p)&&c++); c \\ 227529235 ~40min
c=75939612; forprime(p=3162277660, 10^10, bittest(p,1)&&c++); c \\ 227529235 ~70min

制御構造のコストも見ておこう。

c=0; forprime(p=2, sqrt(10^17), if(p%4==3,c++)); c

c=0; forprime(p=2, sqrt(10^17), p%4==3&&c++); c

c=0; forprime(p=2, 316227766, p%4==3&&c++); c

if文より論理ANDの方が微妙に速いかもしれないが、ハッキリしない。sqrt の部分は直接、整数値で書いて損はないはず。さて、4で割るのは無駄なので、ビットテストに切り替えてみる。この場合 p=2 から始めると 2 もカウントされてしまうので、必ず p=3 から始める。

c=0; forprime(p=3, 316227766, bittest(p,1)&&c++); c

約15%高速化した！　よし、これでいくか。n = 19 は30秒くらいで決着がつくはず…

c=0; forprime(p=3, 3162277660, bittest(p,1)&&c++); c

75939612 が返った。従って:
　　G(10¹⁹) = 2 × 117028833597800689 + 75939612 + 1 = 234057667271540991　「イ」

「使えるものは何でも使う」というアグレッシブな高速化のためには、A091099 の C(10⁹) = 25424042 を利用できる。ループ区間が約2/3になり、30%ほど高速化する。

c=25424042; forprime(p=10^9, 3162277660, bittest(p,1)&&c++); c

【2】　x 以下の普通の素数の数を S(x) とすると、次の関係も成り立つ。
　　G(x) = S(x) + C(√x) − δ(x)
ここで δ(x) はチェビシェフ・バイアス https://oeis.org/A091295 の大きさ。
　　G(10¹⁷) = 2623557157654233 + 8541578 − 6284060 = 2623557159911751　「ア」と一致
　　G(10¹⁹) = 234057667276344607 + 75939612 − 80743228 = 234057667271540991　「イ」と一致

「ア」「イ」をそれぞれ4倍することにより、A091100 の第17項～第20項は、
10494228639647004,
98959817242332844,
936230669086163964,
8883278410114778600 となる（要検算）。OEIS に貢献したい方は、これらの数値を投稿すればたぶん名前が載るだろうが、「A091100 は A091295 を経由して普通の素数の個数 https://oeis.org/A006880 と結び付いている」という事実も（言われてみれば当たり前だが…）コメントに値する。

ところで、チェビシェフ・バイアス A091295 を見ると 10¹⁸ に対する値が、異様に小さい。

15 951700
16 3458334
17 6284060
18 2581691 <--
19 80743228
20 259753425

V(x) が C(x) より大きくなる逆転領域のうち、9番目のものが 10¹⁸ 付近に存在するという（2004年に発見された^*）。同様の理由から、n が大きくなるとき…例えば n が100万までの範囲を考えると、δ(10ⁿ) が一瞬 0 や負の数になる可能性がある。

*Marc Deléglise et al. (2004): Counting primes in residue classes

2022-06-12　「2・4・6・8・10・12・14日」は曜日が違う　フェルマーの小定理への道①

ある月の「1日・2日・3日・4日・5日・6日・7日」が全部別々の曜日で、各曜日が1回ずつ現れることは当然だろう。

日付を2倍した「2日・4日・6日・8日・10日・12日・14日」についても、同じことが言える。なぜだろうか？

【1】　ある月の x 日の曜日は、x を 7で割った余りで決まる（余り1が何曜日に当たるかは、月によって異なる）。曜日は7日周期なので、「ある月の x 日と y 日が同じ曜日」ということは、「x − y が7の倍数」（0と負の倍数を含む）というのと、同じ意味。

月の1日～7日を「7個の日付の集合」と考えてみる。
　　A = {1, 2, 3, 4, 5, 6, 7}
一方、それを2倍した日付の集合は:
　　B = {1 × 2, 2 × 2, 3 × 2, 4 × 2, 5 × 2, 6 × 2, 7 × 2} = {2, 4, 6, 8, 10, 12, 14}
この A と B が曜日として等しいことを示したい。

具体的に直接計算してみる。7で割った余りを考えると、8, 10, 12, 14 は、それぞれ 1, 3, 5, 7 と同じなので
　　B = {2, 4, 6, 8, 10, 12, 14} は {2, 4, 6, 1, 3, 5, 7} と曜日が等しい
つまり、全体として、確かに A と曜日が等しい。

もうちょっと理論的に考えてみよう。もし A と B が曜日の集合として同じでないとすると…。A は各曜日1回ずつなのだから、それと等しくないのなら B には抜けてる曜日があるはず。日付が7個あって、抜けてる曜日があるということは、必ず曜日に重複があるはず（例えば「月火火木金土日」なら水曜日が抜けて、火曜日が重複）。その場合、A の要素のどれか（それを x とする）の2倍と、A の別の要素のどれか（それを y とする）の2倍が、同じ曜日にならなければならない。
　　2x と 2y は同じ曜日　【？！】
　　つまり 2x − 2y = 2(x − y) は7の倍数
…そんなことが可能だろうか？

2(x − y) が素数7で割り切れるのなら、2 と (x − y) の少なくとも一方が7で割り切れる必要がある。

とすると、2 は 7 で割り切れないので、(x − y) が 7 で割り切れる必要がある。

けれど、x と y は集合 A = {1, 2, 3, 4, 5, 6, 7} の要素なので、1 から 7 までの数のどれか。(x − y) が 7 で割り切れる可能性があるとしたら、(x − y) = 0 つまり x = y しかない。

逆に言うと、集合 A から違う曜日の日付 x と y を選んだ場合…つまり x ≠ y の場合には、(x − y) が 7 で割り切れることは、あり得ない。だから今の議論を逆にたどると【？！】は無理。これが証明したいことだった。

【2】　同様に考えると、A の日付を3倍した「3日・6日・9日・12日・15日・18日・21日」も全部別々の（7種類の）曜日となる。

A の日付を4倍した「4日・8日・12日・16日・20日・24日・28日」も、そうなる。

便宜上、月の末日というものを無視して、例えば、その月の25日の10日後を「その月の35日」などと解釈することにすれば（現実には翌月の日付だが）、5倍や6倍でも、全く同じ議論が成り立つ。

けれど、もちろん7倍ではいけない！　「7日・14日・21日…」は、差が7の倍数なので、全部同じ曜日になってしまう。

そこで b を 1 以上 6 以下のどれかの数とすると、上記の便宜上の規約の下で、次の二つは「曜日として同じ集合」になる。
　　C = {1, 2, 3, 4, 5, 6}
　　D = {1b, 2b, 3b, 4b, 5b, 6b}
A と違って C では、7で割って0余る「7日」が除去されている。「7日」の b 倍は、当然「7日」と同じ曜日だが、その日付は D から除去されている。だから、どちらの集合も、7の倍数を含まない。

曜日（つまり各要素を7で割った余り）を考えた場合、C の要素と D の要素は、全く同じなのだから、それらの積も等しいはず:
　　「Cの積」　1 × 2 × 3 × 4 × 5 × 6
　　「Dの積」　1b × 2b × 3b × 4b × 5b × 6b = (1 × 2 × 3 × 4 × 5 × 6)b⁶

この二つが「7で割った余り」として等しい…つまり「Cの積」を7で割った余りと、「Dの積」を7で割った余りは等しい:
　　1 × 2 × 3 × 4 × 5 × 6 ≡ (1 × 2 × 3 × 4 × 5 × 6)b⁶ (mod 7)
ここで □ ≡ ■ (mod 7) というのは、□ を7で割った余りと ■ を7で割った余りが等しいという意味。

実は、上の式の両辺を 1 × 2 × 3 × 4 × 5 × 6 で割ることが許される。結果は:
　　1 ≡ b⁶ (mod 7)
その意味は: 「左辺の 1 を7で割った余り（もちろん 1 である）と、右辺の b⁶ を7で割った余りが等しい」。b は 1 から 6 の任意の数だった。要するに「b を6乗して7で割ると1余る」。これはフェルマーの小定理に他ならない。

【3】　曜日の数が 7 ではなくて、5 や 11 であるパラレルワールドを考えてみよう。曜日の数が11個あるパラレルワールドでは、新しい曜日の名前が4個増えるはず。土曜日の後に、「天曜日・海曜日・冥曜日・穀曜日」を追加しよう…。土曜日は土星なので、その外側に天・海・冥を追加するのは妥当だろう（冥王星の地位は微妙だが、まぁ日曜日・月曜日もあるのだから、惑星であってもなくてもいいのだ）。もう1個必要なので、小惑星1番のケレス＝穀神星の穀を採用する。

ここで重要なのは、曜日の名前ではなく、「曜日の数」が素数であること（理由は後述）。8, 9, 10 ではなく 11 を例にするのは、そのため。

上記と全く同様の議論が成り立って、b を1～10の任意の数とするとき、b¹⁰ ≡ 1 (mod 11) が成り立つ。

そんなこと急に言われたって分かんねぇよーと感じるのは、まぁ自然だろう…曜日の数が11個で土曜日と日曜日の間に「天曜日・海曜日・冥曜日・穀曜日」があるだなんて、そんなクレイジーな話…。信じられなければ、このパラレルワールドのカレンダーを書いて、順を追って具体的に確かめてみよう！

より一般的に、p を 3 以上の任意の素数として、b を 1 以上 p 未満の整数とするとき、
　　b^p−1 ≡ 1 (mod p)
が成り立つ。証明法は【2】とほとんど同じだが、p が素数という仮定は、どこで利いているのだろうか？

「p で割った余りの世界」では、普通の世界と同じように足し算・引き算・掛け算ができる。割り算については、普通の世界と同様、0 での割り算はできないのだが、それだけでなく「p と互いに素でない数」での割り算は、微妙にややこしい。

その点、p が素数なら、1 以上 p 未満の因子は全部 p と互いに素なので、0 で割ることを別にすれば、気兼ねなく自由に割り算ができる。

このことが「実は、上の式の両辺を 1 × 2 × 3 × 4 × 5 × 6 で割ることが許される」といった話と結び付いてくる。さらに「2(x − y) が素数7で割り切れるのなら、2 と (x − y) の少なくとも一方が7で割り切れる必要がある」といった主張も、曜日の数が素数であればこそなのだ…。（続く）

2022-06-14　パラレルワールドの足し算・掛け算　フェルマーの小定理への道②

ある月の「2日・4日・6日・8日・10日・12日・14日」は全部曜日が違う…という素朴な観察を出発点に、フェルマーの小定理を導ける。前回は、細かいことにこだわらず、その議論の流れを大ざっぱに眺めた。細かい部分のギャップを埋めて、厳密化していきたい。

【1】　例えば 3 ≡ 24 (mod 7) というのは、ある月の「3日」と「24日」が同じ曜日という意味だった。それは、「3 も 24 も、7で割った余りが同じ」とも解釈できるし、「24 − 3 は7の倍数」とも解釈できる（経過日数が7の倍数なら曜日は同じ）。一般に
　　a ≡ b (mod m)
　　（a と b は m を法として合同）
というのは「a も b も m で割った余りが同じ」という意味だが「a − b は m の倍数」という意味でもある（「m で割る」というコンセプトが基本であり、0 での割り算は定義されないので、m ≠ 0 とする）。a − b と b − a は符号が違うだけで、m で割り切れるかどうかに違いはないので、「a − b は m の倍数」の代わりに「b − a は m の倍数」と言っても構わない。◎ が ○ の倍数なら、○ は ◎ の約数なので、「m は a − b の約数」と言うこともできる。

〔例〕　5 ≡ 13 (mod 4)　なぜなら 13 − 5 = 8 は 4 の倍数。同じことだが、4 は 13 − 5 の約数。

5 ≡ 13 (mod 4) のような式を合同式という。mod 4 の 4 を「法」という。典型的には法は 2 以上の整数だが、それ以外のもの（例えば、複素整数や多項式）を法とすることもある。

〔例〕　−3 + 4i ≡ 1 (mod −2 + 2i)　なぜなら (−3 + 4i) − 1 = −4 + 4i は −2 + 2i の倍数。

法の値が文脈から明らかな場合、mod m の表記を省いて単に a ≡ b のように書くこともある。

【2】　合同式が成り立っているとき、その両辺に同じ数を足しても、引き続き合同式が成り立つ。

〔例〕　5 ≡ 13 (mod 4) は正しい（13 − 5 = 8 は 4 の倍数）。その両辺に 2 を足した 5 + 2 ≡ 13 + 2 つまり 7 ≡ 15 (mod 4) も正しい（15 − 7 = 8 は 4 の倍数）。

証明　a ≡ b (mod m) とは「両辺の差が m の倍数」という意味だった。その場合、両辺に同じ数を足しても、両辺の差は変わらず、引き続き m の倍数。□

より一般的に a ≡ b (mod m) と c ≡ d (mod m) が成り立つなら、左辺同士・右辺同士を足し算した a + c ≡ b + d (mod m) も成り立つ。

証明　(a + c) − (b + d) が m の倍数であることを示せばいい。仮定から、a − b を M₁ として c − d を M₂ とすると、M₁ も M₂ も m の倍数。
　　(a + c) − (b + d) = (a − b) + (c − d) = M₁ + M₂
は、m の倍数を2個、足し合わせたものなので、m で割り切れる。□

なぜなら M₁ = m × 整数、M₂ = m × 整数なので、M₁ + M₂ = m × (整数 + 整数)。

要するに、足し算については、合同式を普通の等式のように扱うことができる。合同式の引き算についても、普通の等式のように扱うことができる（引き算は、符号を反転させた数の足し算にすぎないので）。

【3】　掛け算についても、合同式を普通の等式のように扱うことができる。

〔例〕　2 ≡ 9 (mod 7) と 3 ≡ 10 (mod 7) は正しい。左辺同士・右辺同士を掛け合わせた次の式も正しい。
　　2 × 3 ≡ 9 × 10　つまり　6 ≡ 90 (mod 7)
実際 90 − 6 = 84 は 7 の倍数。

一般に、一定の法 mod m について a₁ ≡ b₁ と a₂ ≡ b₂ が成り立てば、a₁a₂ ≡ b₂b₂ も成り立つ。

証明　仮定から a₁ を m で割った余りと、b₁ を m で割った余りは等しい。それを r₁ とすると、こう書ける:
　　a₁ = m × 整数 + r₁
　　b₁ = m × 整数 + r₁
同様に、a₂ を m で割った余りを r₂ とすると:
　　a₂ = m × 整数 + r₂
　　b₂ = m × 整数 + r₂
だから:
　　a₁a₂ = (m × 整数 + r₁)(m × 整数 + r₂)
　　= (m × 整数)(m × 整数) + (m × 整数)r₂ + r₁(m × 整数) + r₁r₂
は、m の整数倍 + r₁r₂ と書ける。同様に b₁b₂ も m の整数倍 + r₁r₂ と書ける。前者から後者を引くと、r₁r₂ の部分は消えて
　　(m の整数倍) − (m の整数倍) = m の整数倍
が残る。これは
　　a₁a₂ − b₁b₂ = m の整数倍
　　つまり　a₁a₂ ≡ b₁b₂ (mod m)
を意味する。□

3個以上の数が掛け算される場合も同様。例えば、a₁ ≡ b₁, a₂ ≡ b₂, a₃ ≡ b₃ のとき、a₁a₂ ≡ b₂b₂ は証明済みなので、その式と a₃ ≡ b₃ について、左辺同士・右辺同士を掛け合わせれば:
　　a₁a₂a₃ ≡ b₂b₂b₃

【4】　このことは「曜日を使ったフェルマーの小定理の証明」において、重要な鍵となる。前回観察したように、
　　C = {1, 2, 3, 4, 5, 6}
　　D = {1b, 2b, 3b, 4b, 5b, 6b}
の二つの集合の要素間に、mod 7 において6組の合同式が成り立つことから（ただし b ≡ 0 ではないとする）:
　　「Cの積」と「Dの積」は合同　すなわち
　　《あ》　1 × 2 × 3 × 4 × 5 × 6 ≡ 1b × 2b × 3b × 4b × 5b × 6b (mod 7)

《あ》の両辺を 1 × 2 × 3 × 4 × 5 × 6 で割れば
　　1 ≡ b⁶ (mod 7)
これは、実質的にフェルマーの小定理なのだが、依然として証明にギャップがある！

第1に「二つの集合の要素間に…6組の合同式が成り立つ」という部分をもう少しきちんと分析して、すっきり解明したい。第2に「《あ》の両辺を同じ数で割っていい」というのは、この文脈では結論としては正しいものの、理論的に微妙な点がある。

例えば 8 ≡ 18 (mod 10) は正しい合同式だが（18 − 8 は 10 の倍数）、両辺を 2 で割って 4 ≡ 9 (mod 10) とすると、もはや正しくない（9 − 4 は 10 の倍数ではない）。足し算・引き算・掛け算までは等式と同様だが、合同式の割り算に関しては、必ずしも等式と同様には扱えないことが分かる。その点があやふやなまま「両辺を 1 × 2 × 3 × 4 × 5 × 6 で割れば…」と、のん気に議論するわけにもいかないだろう。（続く）

2022-06-17　パラレルワールドの割り算　フェルマーの小定理への道③

ある月の曜日…という身近な話から、フェルマーの小定理を導く。

前回は「合同式」というものを紹介して、その世界でも、足し算・掛け算などが普通にできることを確かめた。フェルマーの小定理の証明では、ある種の「割り算」が必要になるので、今回はそれを…。

【1】　a ≡ b (mod m) の一つの解釈は「b − a が m で割り切れる」というものだった（前回参照）。そうすると、4 ≡ 22 (mod 9) は正しい（なぜなら 22 − 4 = 18 は 9 で割り切れる）。両辺を2で割った 2 ≡ 11 (mod 9) も正しい（なぜなら 11 − 2 = 9 は 9 で割り切れる）。ここまでは簡単に見える。ところが…

6 ≡ 24 (mod 9) は正しいのに、その両辺を6で割った 1 ≡ 4 (mod 9) は正しくない！

ちょっとトリッキー…？

【2】　といっても、両辺を同じ数で割る方法は、難しくない。次のシンプルな規則に従う。

今、a ≡ b (mod m) が成り立っているとすると…

割り算の規則1
　　a と b がどちらも c で割り切れるとき…
　　もし c と法 m が互いに素なら、
　　a ≡ b (mod m)　の両辺を c で割って　a/c ≡ b/c (mod m)　とすることが許される。

〔注〕　「互いに素」とは「最大公約数が 1」という意味だが、この場合、「2以上の公約数を持たない」と言い換えることもできる。前提として、法 m は 0 ではない（前回参照）。さらに c で割るのだから、もちろん c も 0 ではない。

〔例〕　上の例で 4 ≡ 22 (mod 9) の両辺を「2」で割ってもOKだったのは、「2」が法9と互いに素だから。6 ≡ 24 (mod 9) の両辺を「6」で割っちゃ駄目だったのは、「6」が法9と互いに素でないから（公約数3を持つ）。

規則1に当てはまらない場合…つまり c と m の最大公約数 G が2以上の場合…は、こうなる。

割り算の規則2（参考。フェルマーの小定理の証明には必要ない）
　　a と b がどちらも c で割り切れるとき…
　　もし c と法 m の最大公約数 G が2以上なら、
　　a ≡ b (mod m)　の両辺を c で割る場合には
　　法が変わって　a/c ≡ b/c (mod m/G)　となる。

〔例〕　6 ≡ 24 (mod 9) の両辺を「6」で割りたいなら、法9も G = 3 で割って
　　1 ≡ 4 (mod 3)　としなければならない。
ここで G = 3 は、割る数「6」と、もともとの法「9」の最大公約数。

規則1が成り立つ理由は、次の奥義（？）から説明される。

奥義「絞り込みの術」　2個の整数 X, Y の積 XY が、整数 Z で割り切れる状況において…
もし X と Z が互いに素なら、Y が Z で割り切れる。

〔例〕　X = 5, Y = 12。積 XY = 60 は Z = 6 で割り切れる。ところが X = 5 と Z = 6 は互いに素なので、Y が Z で割り切れる。事実、12 は 6 で割り切れる！

解説　XY にせよ (u − 1)(u² + u + 1) にせよ、数論では2個の因子の積が「何か」（それを Z としよう）で割り切れる状況がよくある。このとき、因子の一方が Z と互いに素であることを示せれば、他方の因子が Z で割り切れる――「XY は Z で割り切れる」という大ざっぱな話から、状況分析を精密化して「Y は Z で割り切れる」と絞り込める。

〔参考〕　Z が素数の場合、「絞り込みの術」はいわゆる「ユークリッドの補題」と同値。ところで、ここで考えている「割り算」は、合同式の両辺を普通の整数で“約分”する単純計算。「合同式の世界における逆数」の話ではない。

【3】　奥義の証明は難しくないが、見掛け以上に深い…。それは次回以降のお楽しみとして、先に「この奥義を使って、規則1の正しさを証明できる」ことを見ておきたい。今、規則1の前提に従って、a と b がどちらも c で割り切れるとする。このとき…
　　a/c = A と b/c = B はどちらも整数（割り切れるのだから！）
両辺を c 倍して分母を払うと:
　　《え》　a = Ac
　　《お》　b = Bc

合同式 a ≡ b (mod m) が成り立つとき、その左辺を《え》、右辺を《お》で置き換えると Ac ≡ Bc (mod m) だが、それは
　　Bc − Ac = c(B − A)　が m で割り切れる
という意味を持つのだった。さて、規則1の条件によると c と m は互いに素。この状況は、奥義「絞り込みの術」において、
　　X = c
　　Y = B − A
　　Z = m
とした場合に当たる（X と Z が互いに素）。奥義の教えによれば、このとき Y が Z で割り切れる。すなわち…
　　B − A が m で割り切れる。

ところが「B − A が m で割り切れる」ということは、A ≡ B (mod m) とも書けるので、上記の内容を整理すると…
　　《か》　a ≡ b (mod m)　つまり　Ac ≡ Bc (mod m)
が成り立つなら、
　　《き》　A ≡ B (mod m)
も成り立つ（c と m が互いに素ということを前提として）。《き》は《か》の両辺を c で割ったもの。要するに、規則1の条件では、このように合同式の両辺を同じ数 c で割ることが許される。□

【4】　曜日を使った「フェルマーの小定理の証明」では、
　　《く》　1 × 2 × 3 × 4 × 5 × 6 ≡ (1 × 2 × 3 × 4 × 5 × 6)b⁶ (mod 7)
の両辺を 1 × 2 × 3 × 4 × 5 × 6 で割る必要があった。より一般的に（後で整理し直すが）、3 以上の素数 p を法とする合同式…
　　《け》　1 × 2 × … × (p − 1) ≡ [1 × 2 × … × (p − 1)]b^p − 1 (mod p)
の両辺を 1 × 2 × … × (p − 1) で割る必要がある。前回までは、この割り算が許されるのかあやふやだったけど、今このギャップを埋めることができる。

〔注意〕　「曜日」というのは、説明の便宜上の観点であり、フェルマーの小定理は、別にカレンダーと関係あるわけではない。現実世界の p = 7 に限らず、曜日の数 p は素数であれば何でもいい。ここまできたら「曜日」のイメージにこだわらず、素直に「数論の定理」と考えた方がすっきりする。

《く》において、「2」は法 7 と互いに素なので、規則1から、両辺を「2」で割ることが許される。「3」も法 7 と互いに素なので、両辺を「3」で割ることも許される。同様に「4」で割ることも、「5」で割ることも「6」で割ることも許される。さらに、両辺を「1」で割ることは（1 で割っても値は変わらないのだから）もちろん許される（理屈を言えば 1 と 7 も互いに素なので、これも規則1に従っている）。要するに 1 で割っても、2 で割っても、3 で割っても、…、6 で割ってもいいのだから、それらで順に割ってもOK。あるいは（同じことだが）まとめて一気に
　　c = 1 × 2 × 3 × 4 × 5 × 6
で割ることが許される。理屈を言えば、この積 c は法 7 と互いに素なので、規則1を使える。

全く同様にして、《け》において、両辺を 1 × 2 × … × (p − 1) で割ることが許される。

これで「フェルマーの小定理」の証明の穴が一つ埋まった！

法を変えずに両辺を割り算したけりゃ、規則1に従う必要がある。だから、フェルマーの小定理では「p は素数」という条件が付く。法が素数でない場合…例えば mod 6 の場合には、法を変えずに 2 で割ることや 3 で割ることができず（割る数が法と互いに素でないので規則1が使えない）、《く》《け》みたいには扱えない。「規則2」はとりあえず必要ないが、別のメモに解説・証明が記されている。（続く）

2022-06-24　小学生の「ユークリッドの補題」　フェルマーの小定理への道④

前回の続き…。フェルマーの小定理の証明を完成させるぜ！

パズルの最後のピースは、「絞り込みの術」の証明だった。

「奥義」絞り込みの術（ユークリッドの補題）　整数 X, Y の積 XY が、整数 Z で割り切れるとき、もし X と Z が互いに素なら、Y が Z で割り切れる。

〔例〕　X = 10, Y = 14, Z = 7 とすると、XY = 140 は Z = 7 で割り切れるが、X = 10 と Z = 7 は互いに素。このとき Y = 14 が Z で割り切れる。

「優等生タイプ」の人は、上記について「素因数分解を考えれば当たり前」と感じるかもしれない。その感覚は間違ってはいないのだが、通常「素因数分解ができること」自体が「絞り込みの術」を使って証明されるので、素因数分解を使って「絞り込み」を証明すると、論理的に堂々巡りになってしまう。公式を暗記して適用するような学校的発想では、この奥義の会得は難しいかもしれない…。

【1】　「奥義」を証明するエレガントな方法は、Hardy & Wright がやったようにバシェ／ベズの定理を使うことだろう。だが、その方法は、高い視点がないと、真意が分かりにくい。

以下では、小学生の算数のような、シンプルで愚直なショートカットを紹介する――「特別な知識」も「高度な理解力」も要らない。若干の「粘り強さ」と「繊細さ」があればいい。とりあえず必要なのは、次の基本性質だけ。

倍数の基本性質　整数 a, b の公倍数は、どれも a, b の最小公倍数 L = lcm(a, b) の倍数。ただし a も b も 0 以外とする。

〔例〕　2 と 3 の公倍数 0, ±6, ±12, ±18, … は、どれも L = lcm(2, 3) = 6 の倍数（最小公倍数 L の、そのまた倍数）。0 も L の倍数だし（0倍）、L = 6 自身も L の倍数（1倍）。

〔注〕　ここでは「正の公倍数のうち最小のもの」を最小公倍数と呼ぶことにする（0 も公倍数だが、正でないので「最小公倍数」とは認めない）。「倍数の基本性質」の正しさについては、下記【4】で証明する。

【2】　「倍数の基本性質」から、次の補助定理が出る。

補助定理　2個の整数 X, Z が互いに素なら、X, Z の最小公倍数は |XZ| に等しい。ただし X も Z も 0 以外とする。

〔注〕　整数の世界において、2個の数が「互いに素」ってゆーのは「±1 以外の公約数を持たないこと」。「正の公約数のうち最大のもの」を最大公約数と呼ぶことにすると、「互いに素」とは「最大公約数が 1」という意味。

〔例〕　X = 6 と Z = 5 は互いに素なので、それらの最小公倍数は |6 × 5| = 30。

「最小の正の公倍数」を最小公倍数と定義しているので（そして、倍数であるかないかは正負と無関係なので）、負の数が含まれる場合、単に符号を無視すればいい。

〔例〕　a = 6 と b = −5 の最小公倍数も |6 × (−5)| = |−30| = 30。絶対値記号は「符号を無視する」という意味。

補助定理の証明　X, Z の最小公倍数を L = lcm(X, Z) とする。L は X の倍数なので、何らかの整数 a を使って
　　《さ》　L = aX
と書ける。L は Z の倍数でもあるので、何らかの整数 b を使って
　　《し》　L = bZ
とも書ける。さて XZ は、もちろん X と Z の公倍数だが、果たして最小公倍数だろうか。倍数の基本性質によれば、公倍数（この場合 XZ）は最小公倍数（この場合 L）の倍数なので、何らかの整数 k を使って
　　《す》　XZ = kL
と書ける。

《す》の右辺の L に《し》を代入しよう。
　　XZ = k(bZ)　その両辺を Z で割ると:
　　《せ》　X = kb

《す》の右辺の L に《さ》を代入しよう。
　　XZ = k(aX)　その両辺を X で割ると:
　　《そ》　Z = ka

《せ》《そ》から、X も Z も k の倍数であることが分かる。言い換えれば k は X, Z の公約数。ところが、定理の仮定によれば X, Z は互いに素なので、それらの公約数は k = ±1 に限られる。これを《す》に代入すると:
　　XZ = (±1)L = ±L
つまり XZ と L = lcm(X, Z) は、プラスマイナスの違いを無視すれば値が等しい。最小公倍数の定義から L は正なので、L = |XZ|。これが証明したいことだった。□

【3】　上の補助定理を使って「奥義」を証明できる。証明したい内容を整理すると:

• 《た》　XY が Z で割り切れると仮定する。従って Z ≠ 0。
• 《ち》　X と Z が互いに素と仮定する。
• 《つ》　「Y が Z で割り切れる」ことを示したい。

仮定《ち》により X と Z は互いに素なので、もし X ≠ 0 なら、補助定理から、X と Z の最小公倍数はこうなる:
　　《て》　L = lcm(X, Z) = |XZ|

さて、XY はもちろん X の倍数だが、仮定《た》により XY は Z の倍数でもある。つまり、XY は X と Z の公倍数。倍数の基本性質により、この公倍数 XY は L の倍数。従って、何らかの整数 n を使って、こう書ける:
　　XY = nL
　　右辺 の L に《て》を代入すると　XY = n |XZ|　（|XZ| は正の数）
　　符号の違いを無視すると　XY = nXZ　（XZ は負の数かもしれないが、気にしない！）
　　両辺を X で割ると　Y = nZ
　　両辺を Z で割ると　Y/Z = n

つまり Y ÷ Z は割り切れて、商が整数になる（符号の違いを無視しないなら、上記 XY = nXZ は両辺の符号があべこべかもしれず、その場合、正しくは XY = −nXZ つまり Y/Z = −n だが、割り切れることに変わりない）。これで《つ》が示された。すなわち「奥義」（ユークリッドの補題）が証明されたのである！

…と言いたいところだが、証明の途中で X ≠ 0 という余計な条件が入っちまった。証明の終わり近くでも X で割り算するので、X ≠ 0 は（上記の証明では）必要な制限。

フェルマーの小定理の証明に関する限り、割り算の規則1の除数 c が X に当たる。0 で割り算はできないので、c ≠ 0 つまり X ≠ 0 という限定があっても、別に困らない。とはいえ、X = 0 のケースはトリビアル（ばかばかしいくらい簡単）なので、ここでついでに片付けておこう。

X = 0 の場合の証明　まず「d が X の約数」というのは「X が d で割り切れること」、言い換えれば「d は 0 以外で、しかも dq = X を満たす q がその世界に存在すること」（例えば 2q = −6 は整数解 q = −3 を持つので、整数 2 は整数 −6 の約数）。X = 0 のとき、0 以外のどんな d もこの条件を満たす（q = 0 とすればいい）。だから X = 0 という数は無制限に大きい約数を持つが、Z の最大の約数は |Z| なので、
　　gcd(X, Z) = gcd(0, Z) = |Z|
となる（仮定《た》により Z ≠ 0）。さて、仮定《ち》により X = 0 と Z は互いに素なので、gcd(0, Z) = 1。つまり |Z| = 1、要するに Z = ±1。どんな整数 Y も ±1 で割り切れるので、もちろん《つ》が成り立つ。□

【4】　倍数の基本性質「a, b の公倍数は、どれも a, b の最小公倍数 L の倍数」。このことは【1】以下で使ったが、まだ証明していない。何となく当たり前過ぎて、逆にどっから手ぇ付けりゃぁいいのか分かんねー感じだが、超基本的なことから外堀を埋めていこう。

「超基本1」　A の倍数と、A の倍数の和は、再び A の倍数。A の倍数と、A の倍数の差も、再び A の倍数。

〔例〕　A の5倍（5A）と、A の3倍（3A）の和は、5A + 3A = 8A。差は 5A − 3A = 2A。どちらも A の倍数（それぞれ8倍と2倍）。

「超基本1」の証明　上の例の「5倍」と「3倍」を任意の整数倍に置き換えても、全く同様の議論が成り立つ。□

「超基本2」　A の倍数のそのまた倍数は、A の倍数。

〔例〕　A の5倍（5A）のそのまた3倍、つまり 5A × 3 = 15A は A の倍数（15倍）。

「超基本2」の証明　上の例の「5倍」と「3倍」を任意の整数倍に置き換えても、全く同様の議論が成り立つ。□

「超基本3」　a, b の公倍数と、a, b の公倍数の和・差は、再び a, b の公倍数。

証明　a, b の任意の公倍数 M は、もちろん「a の倍数」。a, b の任意の公倍数 N も、もちろん「a の倍数」。それらの和 M + N は「a の倍数」（超基本1）。…今言ったことは「a の倍数」を「b の倍数」に置き換えても、そのまま成り立つ。つまり M + N は「a の倍数」であり「b の倍数」でもあるから、a, b の公倍数。差 M − N についても同様。□

「超基本4」　「a, b の公倍数」のそのまた倍数は、a, b の公倍数。

証明　a, b の任意の公倍数 M は、もちろん「a の倍数」。そのまた倍数 kM は「aの倍数」（超基本2）。ここで k は任意の整数。…今言ったことは「a の倍数」を「b の倍数」に置き換えても、そのまま成り立つ。つまり kM は「a の倍数」であり「b の倍数」でもあるから、a, b の公倍数。□

当たり前のことばかりで、あくびが出てきたかもしれないが、今から最終ダンジョンに突入する。

倍数の基本性質の証明　a, b の最小公倍数を L とする。超基本4から、
　　L の倍数は a, b の公倍数。
このとき、逆に…
　　a, b の公倍数は L の倍数。
…と言い切れるか？　言い切れるのなら、倍数の基本性質が証明されたことになる。この「逆」の部分がラスボス。

「a, b の公倍数 X が L の倍数ではない、なんてことは、あり得ねぇんだよ！」ということを証明して、ラスボスを倒すぜ。

もしも、そういう正の数 X が存在したらどうなるか。0L, 1L, 2L, 3L, 4L, … は無限に大きくなる数の列。X は「そのどれか」ではないというのだから、謎の数 X が存在するとすれば、それは（例えば 8L と 9L の間のように）どこかの nL と (n+1)L の間にある（n は、とある整数）:
　　nL < X < (n+1)L = nL + L
この不等式から nL を引き算すると:
　　《と》　0 < X − nL < L

さて、nL は a, b の公倍数（超基本4)。X が a, b の公倍数だと言い張るのなら、そこから nL（それは a, b の公倍数）を引き算したものも a, b の公倍数（超基本3）。つまり不等式《と》の真ん中にある…
　　X − nL
…という数は「a, b の公倍数」であり、しかも、不等式《と》があるので「L より小さい正の整数」ということになる。そんな数はあり得ねぇ…。だって L は最小公倍数。最小公倍数ってことは、a, b の最小の正の公倍数なんだから、それよりもっと小さい正の公倍数なんて、あるわけねぇじゃん。

要するに、「L の倍数ではない正の整数 X」が a, b の公倍数になるケースがあったとすると、「最小公倍数より小さい正の公倍数」が存在することになるが、それはあり得ない話なので、今言ったような X は存在し得ない。

同様に、「L の倍数ではない負の整数 X」が a, b の公倍数になることも、あり得ない。0L, −1L, −2L, −3L, −4L, … は無限に小さくなる数の列なので、そういう負の数 X があるとすれば、それはどこかの nL と (n+1)L の間にある（n は、とある負の整数）。従って、上と同じ不等式が成り立ち、同じ議論が成り立ち、「あり得ない」と結論される。□

案外あっけないラスボスだったぜ。

以上で、フェルマーの小定理の証明が完成したが、これだけでは実感が湧いてこない。いろんな命題（一つ一つは単純だが）が絡み合い、全体的な見通しが悪い。次回、話を整理し直して、もう少しすっきりさせたい。

「奥義」については、バシェ／ベズの定理を使う現代的でエレガントな証明も、研究する価値がある。だが、最も好奇心を刺激することとして、2000年以上前に、ユークリッドはどうやってこんなことを思い付き、証明したのだろうか？

ユークリッド自身の証明法を研究してみるのも、面白そうだ…。（続く）

2022-06-28　フェルマーの小定理で遊んじゃえっ！　小学生の「フェルマーの小定理」

【1】　3 以上の素数 p を考える。その素数 p より 1 小さい数を q としよう。このとき、2^q − 1 は p で割り切れる。

• p = 3 は素数: 2² − 1 = 3 はもちろん 3 で割り切れる。
• p = 5 は素数: 2⁴ − 1 = 15 は 5 で割り切れる。
• p = 7 は素数: 2⁶ − 1 = 63 は 7 で割り切れる。
• p = 11 は素数: 2¹⁰ − 1 = 1023 は 11 で割り切れる。
• p = 13 は素数: 2¹² − 1 = 4095 は 13 で割り切れる。
• などなど

これは面白い現象だ！　q 乗から 1 を引くと p で割り切れる――事実は単純だが、なぜそうなるのかはミステリー。

一方、p が素数でない場合、似たことを考えると、例えば…

• p = 9 は素数でない: 2⁸ − 1 = 255 は 9 で割り切れない。
• p = 15 は素数でない: 2¹⁴ − 1 = 16383 は 15 で割り切れない。

p が素数かどうかによって、2^q − 1 の振る舞いが異なるようだ。2^q − 1 という数は、q が「素数マイナス1」かどうか、どうやって「感じる」ことができるのだろうか？

【2】　q 乗される数 b は「2」に限る必要ない。素数 p の倍数以外なら、何でもいい。試しに b を「3」としてみよう。

• p = 3 は素数だが… b = 3 はその p の倍数（1倍）なので、条件を満たさない。
• p = 5 は素数: 3⁴ − 1 = 80 は 5 で割り切れる。
• p = 7 は素数: 3⁶ − 1 = 728 は 7 で割り切れる。
• p = 11 は素数: 3¹⁰ − 1 = 59048 は 11 で割り切れる。
• などなど

一般に、p を素数、b を p の倍数以外の任意の整数とするとき、
　　b^q − 1 は p で割り切れる（q = p − 1）。
　　つまり　b^p−1 − 1 は p で割り切れる。

b^p−1 − 1 が p で割り切れるのだから、それより 1 大きい数を考えると、こうなる:
　　b^p−1 を p で割ると、割り切れずに 1 余る。
式で書くと:
　　b^p−1 ≡ 1 (mod p)

これがフェルマーの小定理だ！

合同記号 ≡ の意味は「小定理への道②」参照。

【3】　私たちはカレンダーを使って、この不思議な定理（何の役に立つのか分からないが…）を証明した。道筋を振り返ってみよう。ある月の次の日付は、もちろん全部曜日が違う:
　　S₁ = {1, 2, 3, 4, 5, 6}
ところが、S₁ の日付をそれぞれ2倍した次の日付も、やはり全部曜日が違う:
　　S₂ = {2, 4, 6, 8, 10, 12}
しかも S₂ の日付に含まれる6種類の曜日は、S₁ の日付の6種類の曜日と同じなのだ！

例えば、2022年6月のカレンダーでは、
　　S₁ の要素　←同じ曜日→　S₂ の要素
の1対1の対応が、次のように成り立っている:
　　1 ≡ 8 (mod 7)　　水曜日
　　2 ≡ 2 (mod 7)　　木曜日
　　3 ≡ 10 (mod 7)　　金曜日
　　4 ≡ 4 (mod 7)　　土曜日
　　5 ≡ 12 (mod 7)　　日曜日
　　6 ≡ 6 (mod 7)　　月曜日
合同式の左辺には S₁ の日付が過不足なく1回ずつ現れ、右辺には S₂ の日付が過不足なく1回ずつ現れている。

普通の等式について、例えば x = A, y = B なら xy = AB となるのは当たり前だが（ピンとこなければ x = A = 5, y = B = 3 のように具体的な数を当てはめてみよう）、合同式についても、法が一定の場合、x ≡ A, y ≡ B なら xy ≡ AB が成り立つ（パラレルワールドの掛け算）。それどころか、合同式が3個以上に増えて、例えば z ≡ C が追加されたとすると、xyz ≡ ABC も成立。上の曜日の対応表から、
　　1 × 2 × 3 ≡ 8 × 2 × 10 (mod 7)
が成り立つはずだ。実際に計算すれば、簡単に確かめられる:
　　6 ≡ 160 (mod 7)　左辺も右辺も7で割った余りは同じ
この理屈を6個の数の積に拡張して、同じ曜日の対応表を使うと:
　　1 × 2 × 3 × 4 × 5 × 6 ≡ 8 × 2 × 10 × 4 × 12 × 6 (mod 7)
――この左辺は S₁ の全要素の積、右辺は S₂ の全要素の積に他ならない。掛け算の順序を入れ替えると:
　　1 × 2 × 3 × 4 × 5 × 6 ≡ 2 × 4 × 6 × 8 × 10 × 12 (mod 7)

より一般的に、b を7の倍数以外の任意の数とするとき、次の2個の集合は、同じ曜日の日付をちょうど1個ずつ含む（ただし、現実のカレンダーと無関係に、例えばその月の「26日」の10日後を、その月の「36日」とみなす）。
　　S₁ = {1, 2, 3, 4, 5, 6}
　　S₃ = {1b, 2b, 3b, 4b, 5b, 6b}
この場合も、前者の全要素の積と、後者の全要素の積は合同（理由は後述）なので:
　　1 × 2 × 3 × 4 × 5 × 6 ≡ 1b × 2b × 3b × 4b × 5b × 6b (mod 7)
　　つまり　1 × 2 × 3 × 4 × 5 × 6 ≡ (1 × 2 × 3 × 4 × 5 × 6)b⁶ (mod 7)

この最後の合同式の両辺を (1 × 2 × 3 × 4 × 5 × 6) で割ると、
　　1 ≡ b⁶ (mod 7)
　　つまり b⁶ ≡ 1 (mod 7)
となって、フェルマーの小定理の p = 7 の場合が証明されたことになる。

この割り算が本当に許されるのか確かめることは、結構面倒だったが、私たちは「奥義」と呼ばれるものを証明した――この「奥義」を使うと「割り算の規則1」が証明され、上記の割り算の正しさが保証される。具体的に、mod m の世界では、m と互いに素な数で割るのなら、合同式の両辺を自由に割り算できる！

上の例の場合、(1 × 2 × 3 × 4 × 5 × 6) は、mod 7 の「7」と互いに素。

【4】　今、3 以上の任意の素数 p について、次の2個の集合を考えてみる:
　　T₁ = {1, 2, 3, 4, …, p−1}
　　T₂ = {1b, 2b, 3b, 4b, …, (p−1)b}
ここで b は p の倍数以外の任意の整数。

この場合も2個の集合のそれぞれについて、全要素の積は合同で:
　　1 × 2 × 3 × 4 × … × (p−1) ≡ 1b × 2b × 3b × 4b × … × (p−1)b (mod p)
　　つまり　1 × 2 × 3 × 4 × … × (p−1) ≡ [1 × 2 × 3 × 4 × … × (p−1)]b^p−1 (mod p)
両辺を 1 × 2 × 3 × 4 × … × (p−1) で割り算すると（☆）:
　　1 ≡ b^p−1 (mod p)
フェルマーの小定理が証明された！

（☆）の割り算が許される根拠として、z = 1 × 2 × 3 × 4 × … × (p−1) と p は互いに素。なぜなら p は素数なので、2 以上 p 未満の約数を持たず、z と p の最大公約数は 1。「割り算の規則1」が適用される。

T₁ と T₂ の各要素が mod p において1対1対応すること（例えば、1週間が11日で曜日が11種類あるパラレルワールドでは、どちらの集合も同じ10種類の曜日を過不足なく含んでいること）については、「小定理への道①」である程度観察したが、この点をもう少し分析してみよう。

「奥義」によると、XY が Z で割り切れるとき、X と Z が互いに素なら、Y が Z で割り切れる。裏を返せば:
　　《な》　X と Z が互いに素なのに、Y が Z で割り切れないなら、XY は Z で割り切れない。

T₁ のどの要素も、もちろん p で割り切れない。T₂ のどの要素も、やはり p で割り切れない。なぜ？　この場合、X に当たるのは 1, 2, 3, …, p−1 のどれか。Y = b で、Z = p に当たり、X と Z は互いに素。しかも「b は p の倍数ではない」と仮定しているから、Y = b は Z = p で割り切れない。だから《な》によって、XY = 1b, XY = 2b, XY = 3b などが Z = p で割り切れることはない。

すると、T₁ も T₂ も「p で割り切れる数」――言い換えれば ≡ 0 (mod p) の数――を含んでいない。つまり T₁ の日付は、その月の p 日目の曜日を含んでいないが、T₂ も、この曜日を含んでいない。一方、mod p ということは「1週間が p 日で曜日が p 種類」なのだから、T₁ は、p 日目の曜日以外の全曜日を1回ずつ含む。

もしも T₁ と T₂ の曜日（mod p での区別）が1対1対応していないのなら、集合 T₂ の日付を考えると、T₁ に含まれるどれかの曜日（どれかの要素と合同な要素）が抜けている。けれど、どちらの要素も p−1 個なので、T₁ の日付にあって T₂ の日付にない曜日があるとするなら、その分、T₂ の日付には「同じ曜日の重複」がある。それは不可能。というのも、もしも T₂ のとある要素 Nb と別の要素 Mb の曜日が「衝突」（重複）していれば――要するに
　　Nb ≡ Mb (mod p)
　　　　ここで Nb と Mb は T₂ の相異なる要素。
　　　　つまり N も M も 1 以上 p−1 以下
が成り立つとすれば――、その両辺から Mb を引いて:
　　Nb − Mb ≡ 0 (mod p)
　　つまり b(N − M) ≡ 0 (mod p)
従って b(N − M) は p で割り切れるはず。そうすると、b と p は互いに素なので、「奥義」によって N − M が p で割り切れるはず。N も M も 1 以上 p−1 以下なのだから、N と M をどう選択しても、そんなことは起こり得ない（強いて言えば N = M なら N − M = 0 は p で割り切れるが、その場合 Nb と Mb は同一の要素であり、相異なる要素ではないので、「別々の2要素が同じ曜日」という「衝突」はない）。

以上のことから、T₁ と T₂ は、全体として、同じ曜日の日付を一つずつ含む。つまり（☆）の割り算の前の「掛け算による合同式」には、きちんとした根拠がある。

T₁ = {u₁, u₂, u₃, …, u_p−1}, T₂ = {v₁, v₂, v₃, …, v_p−1} とすると、u₁ は v_○ のどれか一つと合同、u₂ は v_○ のどれか一つと合同、等々。具体的にどの要素とどの要素が合同なのかはさておき、全体として1対1で合同なのだから、u₁u₂…u_p−1 という積は、全体として v₁v₂…v_p−1 という積と合同。

【5】　論理的には、これでフェルマーの小定理が証明されたわけだが、算数のようなことを組み合わせて…というのは、とっつきやすい半面、見通しが悪い点もあるだろう。

フェルマーの小定理の証明法は、もちろんこれだけではない。1 × 2 × 3 × 4 のような計算を使って、別の角度から素早く証明する方法もある。

今回の主眼は、教科書をトレースすることではなく、「2・4・6・8・10・12・14日」は曜日が違うといった日常的なことからの（ちょっと奇抜な）アプローチ…。「公倍数は、最小公倍数の倍数」という算数に、全てを帰着させ、ユークリッドの補題を小学生的な方法で証明した。これらの方法はエレガントではないかもしれないが、少し掘り下げると、いろんなことと結び付いてる。

注意！　フェルマーの小定理は、p が素数なら、b^p−1 ≡ 1 (mod p) が必ず成り立つことを保証している（ここで b は p の倍数以外）。言い換えると、b^p−1 ≡ 1 (mod p) が成り立たなければ p は絶対に素数ではない。一方、逆に b^p−1 ≡ 1 (mod p) が成り立つからといって、必ずしも p が素数とは限らない（実際には素数であることが多いが、保証はない）。「4の倍数なら必ず偶数」だが、逆に「偶数だからといって、必ずしも4の倍数とは限らない」…それと同じこと。

【6】　カレンダーを使った説明では、話をシンプルにするため、例えば p = 7 のとき、b は「1 以上 6 以下」（0 や 7 ではない）と考えた。その場合、
　　b^p−1 ≡ 1 (mod p)
が成り立つわけだが、実は b は、7 の倍数でさえなければ 8 以上でも構わない。というのも、7 の倍数以外の b は、次のように「1 以上 6 以下」の数と合同だから。
　　b = 8 ≡ 1 (mod 7)
　　b = 9 ≡ 2 (mod 7)
　　b = 10 ≡ 3 (mod 7)
　　b = 11 ≡ 4 (mod 7)
　　b = 12 ≡ 5 (mod 7)
　　b = 13 ≡ 6 (mod 7)
　　b = 14 ≡ 0 (mod 7)　←　この b は 0 や 7 の仲間なので駄目
　　b = 15 ≡ 1 (mod 7)
　　b = 16 ≡ 2 (mod 7)
　　……

例えば 10 ≡ 3 (mod 7) について、等しいもの同士を掛け合わせても結果は等しいので
　　10 × 10 ≡ 3 × 3
　　10 × 10 × 10 ≡ 3 × 3 × 3
　　…などなど…
が成り立ち、その一例として
　　10⁶ ≡ 3⁶ (mod 7)　　‥‥「♪」
も成り立つ。そして
　　3⁷⁻¹ ≡ 1 (mod 7)
が正しいのだから、「♪」を当てはめれば、もちろん
　　10⁷⁻¹ ≡ 1 (mod 7)
も正しい。つまり b = 10 に対しても、
　　b⁷⁻¹ ≡ 1 (mod 7)
が成り立つ。

〔検算〕　3⁷⁻¹ = 3⁶ = 729 を 7 で割ると、確かに 1 余る。10⁷⁻¹ = 10⁶ = 1000000 を 7 で割っても、やっぱり 1 余る（1000000 = 7 × 142857 + 1）。

【7】　同じように考えると、一般に p が 3 以上の素数、b が p の倍数以外の任意の自然数のとき、
　　b^p−1 ≡ 1 (mod p)
が成り立つ。さらに、素数 p は 2 でも構わない――その場合、b は（p = 2 の倍数以外なので）奇数。そして「p−1乗」とは「1乗」のこと。だから p = 2 の場合の解釈は:
　　奇数の1乗（つまりその奇数自身） ≡ 1 (mod 2)
左辺も右辺も奇数だから、どちらも 2 で割れば 1 余る。だから、この合同式は正しい！

2022-08-16　パラレルワールドの割り算 Part 2

cd ≡ ce のような式が成り立ってるとき、両辺を c で割って d ≡ e とやりたくなるのが人情だろう。

このような「割り算」は可能だが、「パラレルワールドの割り算」でチラッと見たように、それをやると、一般には mod ○ の ○ が変化する。

「パラレルワールドの割り算」では、規則1（mod が変わらない場合）だけを証明し、規則2（mod が変わる場合）を詳しく検討しなかった。「身近な曜日の話題からフェルマーの小定理へ」というストーリーでは、規則2は関係ないので、省略したのだ。けれど、中途半端なのもすっきりしない。せっかくなので、割り算の話を完結させておこう！

【1】　modulo m（モジュロ・エム）、略して mod m の一つの解釈は「余りが同じ」ということだった。例えば 24 ≡ 10 (mod 7) が成り立つのは「24 も 10 も、どちらも 7 で割ると余りが 3 だから」。日常的な例で言えば「ある月の24日と10日は曜日が同じ」という事実に対応。どうして24日と10日は曜日が同じなのだろうか。「24 と 10 の差（つまり 14）が 7 の倍数だから曜日が同じ」という見方もできる（曜日は 7 日ごとにリピートするので、経過日数が 7 の倍数なら同じ曜日）。

a ≡ b (mod m) の解釈1　「a を m で割った余りと、b を m で割った余りが一致する」

a ≡ b (mod m) の解釈2　「a − b が m の倍数。言い換えれば a − b が m で割り切れる」

a − b の代わりに b − a を考えても構わない。上の例で言えば 24 − 10 = 14 と 10 − 24 = −14 は符号が反対なだけ。符号の違いは「7 で割り切れるかどうか」の判定に影響しないのいで、どっちからどっちを引き算してもいい。

24 ≡ 10 (mod 7) の例では、両辺を 2 で割って 12 ≡ 5 (mod 7) としても、結果は依然として正しい（パラレルワールドの割り算、規則1参照）。

ところで、22 ≡ 10 (mod 7) は正しくない。こーゆー場合、「等しい」の記号 = に対する「等しくない」の記号 ≠ と同様、22 ≢ 10 (mod 7) と書いて「mod 7 において 22 と 10 は合同ではない」と表現する。簡潔に「22 と 10 は不合同」とも言う。

【2】　一方 22 ≡ 10 (mod 12) は正しい！　なぜなら 22 も 10 も、12 で割った余りが等しいから（余り 10）。あるいは（別の解釈として）、22 − 10 = 12 が 12 の倍数だから。こっちの例は、日常生活で言えば「22時と10時は（午前・午後の区別を無視すれば）同じ時刻――普通のアナログ時計で、短針の位置が同じ」という事実に対応している。22 ≡ 10 のような式（合同式）が正しいかどうかは、「mod 何」で考えているかによって異なる。mod 7 の世界では正しくないことも、mod 12 の世界では正しいかもしれない。mod が違えば、世界が違う。だから合同式を考えるとき、mod の後ろの数（法と呼ばれる）が重大。同じ mod での式が続く場合、面倒なので mod ○ の表記を省略することも多いが、合同 ≡ や不合同 ≢ の記号には（たとえ表記が省略されていても）必ず mod の指定がある。

22 ≡ 10 (mod 12) の場合、両辺を 2 で割った 11 ≡ 5 (mod 12) は成り立たない。11時と5時は、時計の針の位置が違う。

この場合 11 ≡ 5 (mod 6) なら成り立つ。

このことは「22 ≡ 10 (mod 12) の両辺を 2 で割りたいなら、mod の後ろの 12 も 2 で割らないと駄目」ということを暗示しているようだ。けれど【1】では 24 ≡ 10 (mod 7) の両辺を 2 で割って、mod 7 のままでOKだった。どうも【1】の例と【2】の例では、同じような計算なのに別の規則に従うような…。一体どーゆーことだろう？

【3】　今、整数 a, b のどちらも c で割り切れるとする: a = cd, b = ce としよう（d, e はそれぞれ a, b を c で割った商）。すると問題は:
　　a ≡ b (mod m)　すなわち　cd ≡ ce (mod m)　　‥‥①
のとき
　　d ≡ e (mod m)　　‥‥②
と言い切れるか？

①の一つの解釈は、cd − ce が m で割り切れる…というものだった。言い換えると:
　　c(d − e) が m で割り切れる　　‥‥③
同様に②を解釈すると:
　　(d − e) が m で割り切れる　　‥‥④

前提③から結論④が出るかどうかは、奥義（？）絞り込みの術に関係している。奥義いわく「XY が Z で割り切れるとき、X と Z が互いに素なら Y が Z で割り切れる」。X = c, Y = (d − e), Z = m とすると、X = c と Z = m が互いに素なら、Y = (d − e) が Z = m で割り切れる。

互いに素というのは「2 以上の公約数を持たない」という意味だった。【1】の例では c = 2, d = 12, e = 5, m = 7 に当たり、こうなる。
　　前提　　2(12 − 5) が 7 で割り切れる（正しい）　つまり　2⋅12 ≡ 2⋅5 (mod 7)
　　結論　　12 − 5 が 7 で割り切れる（正しい）　つまり　12 ≡ 5 (mod 7)
　　それを保証する奥義　　2 と 7 は互いに素（2 以上の公約数を持たない）

一方、【2】の例では c = 2, d = 11, e = 5, m = 12に当たり、こうなる。
　　前提　　2(11 − 5) が 12 で割り切れる（正しい）　つまり　2⋅11 ≡ 2⋅5 (mod 12)
　　結論（？）　　11 − 5 が 12 で割り切れる（間違い！）　11 ≡ 5 (mod 12) は不成立！
　　奥義との関係　　2 と 12 は互いに素でない（2 以上の公約数を持つ）ので奥義の条件を満たさない
　　　↑　2 と 12 は、公約数 2 を持つ

第1の例は、それで割りたい数 c = 2 が mod の数 m = 7 と互いに素だから単純計算が成り立つが、第2の例は、c = 2 が m = 12 と互いに素でないから「奥義」の発動条件が満たされない。要するに③の
　　c(d − e) が m で割り切れる
という部分において、一般には c と m が互いに素という保証がないので、話が複雑になる。この困難を克服するには、出発点の③の代わりに
　　c′(d − e) が m′ で割り切れる
　　…ただし c′ と m′ は互いに素
の形を作ればいい。そうすれば、奥義によって d − e が m′ で割り切れる。

でも、もともとの c, m をどうやって、どのような c′, m′ で置き換えればいいのだろう？

【4】　結論から言おう。c と m の最大公約数 G が 2 以上なのがいけないのだから、c, m をそれぞれ G で割り、「割った結果同士」を「互いに素」にしてやればいい:
　　c′ = c/G, m′ = m/G

〔例1〕　c = 2, m = 12　→　最大公約数 G = 2
　　c′ = 2/2 = 1 と m′ = 12/2 = 6 なら互いに素

〔例2〕　c = 45, m = 60　→　最大公約数 G = 15
　　c′ = 45/15 = 3 と m′ = 60/15 = 4 なら互いに素

重要なのは、必ず「最大」公約数 G で割ること。最大でない公約数だと「奥義」を発動できない。

〔駄目な例〕　c = 45, m = 60　→　でたらめに選んだ公約数 3
　　c′ = 45/3 = 15 と m′ = 60/3 = 20 は互いに素にならない（公約数 5 を持つ）

〔駄目な例〕　c = 45, m = 60　→　でたらめに選んだ公約数 5
　　c′ = 45/5 = 9 と m′ = 60/5 = 12 は互いに素にならない（公約数 3 を持つ）

c, m をそれぞれ最大公約数 G で割った結果なら、必ず「互いに素」になる。なぜだろうか？

もしもそうならないとしたら…つまり、もしも
　　c′ = c/G　と　m′ = m/G
が依然として互いに素じゃないとすると、両者は 2 以上の公約数（それを h としよう）を持つ。そのとき…
　　c/G は h で割り切れる　→　c/G = h × ある整数（u とする） →　c/G = hu
　　m/G も h で割り切れる　→　m/G = h × ある整数（v とする） →　m/G = hv
右端の式を G 倍して分母を払うと:
　　c = Ghu, m = Ghv
これが本当なら「c も m も Gh で割り切れる」ことになるが、h は 2 以上なので、この Gh という数は G の 2 倍以上――G よりでかい。要するに c, m には G より大きい公約数 Gh がある…ということになる。けど G が最大公約数なんだから、G よりもっと大きい公約数なんてあるわけないよね。つまり、
　　c′ = c/G　と　m′ = m/G
が互いに素じゃない…っていうのは不合理な考えであり、こいつらが互いに素であることは保証されている！

【5】　結局、cd ≡ ce (mod m) が成り立つとき――つまり、③の内容
　　c(d − e) が m で割り切れる
が正しいとき――、もし c と m が互いに素でないのなら、④の方向に行ってもうまくいく保証がないので、代わりにこう考えればいい:
　　c′(d − e) が m′ で割り切れる　　‥‥⑤
　　ここで c′ = c/G と m′ = m/G は互いに素（G は c, m の最大公約数）
すると⑤に対して「奥義」を発動でき、次の結論が保証される:
　　d − e が m′ で割り切れる
　　つまり d ≡ e (mod m′)
m′ = m/G を上の式に代入すると:
　　d ≡ e (mod m/G)　　‥‥⑥

これが「割り算の規則2」だが、正確に言うと「規則1」は「規則2」の一部に当たる。すなわち、⑤⑥は c, m が最初から互いに素の場合にも成立。その場合 c, m の最大公約数 G は 1 なので、⑤においては
　　c′ = c, m′ = m
となり、⑥の結論としては
　　d ≡ e (mod m)
となって、mod の数 m を保ったままの単純計算が成り立つ。

理論的に正確な解釈: 「規則2」は、実は G が 1 でも 2 以上でも成り立つ。この「広い意味での規則2」において、たまたま G = 1 となった場合が「規則1」。すなわち「規則1」は「規則2」に包含されている。【1】では
　　24 ≡ 10 (mod 7)
の両辺を単純で 2 で割ることができたが、【2】においては
　　22 ≡ 10 (mod 12)
の両辺を 2 で割ると mod の数が 12 から 6 に変化して「なんか首尾一貫してねぇぞ？」とも感じられた。実は、前者では 2 と 7 の最大公約数 G = 1 で mod の数が割り算され（1 で割るので見掛け上、何も変わらない）、後者では 2 と 12 の最大公約数 G = 2 で mod の数が割り算される。…ちょっぴり分かりにくいけど、実はどちらも「mod の数が G で割り算される」という同じ法則に従ってる！

2022-06-29　フェルマーの小定理のスパイシーな話題　4k+1型素数は無限個

Hardy & Wright（1938）が「more difficult」と呼び、第20章でようやく証明を完成させている定理。高木貞治（ていじ） の『初等整数論講義』（1931）では、それが第1章で、そよ風のように証明されている――「フェルマーの小定理のちょっとした応用例」として！

どちらも有名な古典的名著だが、この証明に関しては、高木に軍配が上がるだろう。

美しい証明を紹介し、若干の冒険を試みる。

【1】　多くの人はご存じだろう。「素数は無限個存在する」こと、そして、ユークリッドによるそのエレガントな証明を…

2000年以上前、日本列島の住民が文字も持たず、1冊の本も持たず、竪穴住居でつましく暮らし（？）、イネを植えたりドングリを拾って食べたりしていた頃、ギリシャでは既に公理論的数論の研究書が執筆され、素数の無限が証明されていた。それから1000年以上たっても、ヨーロッパの住民は、古代ギリシャの教科書を読んで数論を勉強していた。驚くべきことだ！

ユークリッドの方法を少し変えると、4k+3型の素数（愛称: チョコレート素数）が無限個存在することも、簡単に示される。矛盾を導くため、チョコレート素数が有限個しかないと仮定する。その場合、一番大きいチョコレート素数が存在するので、それを C としよう。C 以下のチョコレート素数を、全部掛け合わせる:
　　3 × 7 × 11 × … × C
ユークリッドはこのような積に 1 を足したが、ここでは、この積を4倍して 1 を引いたものを D とする:
　　《に》　D = 4(3 × 7 × 11 × … × C) − 1
　　《ぬ》　D = 4(3 × 7 × 11 × … × C) − 4 + 3 = 4[(3 × 7 × 11 × … × C) − 1] + 3

〔解説〕　4k+3型は「4k−1型」ともいえるので、その形にするため、《に》では4倍して 1 を引いた。「それなら最初から4倍して 3 を足せば？」とも思えるが、それだと両辺が 3 で割り切れてしまう。

D は、4の倍数プラス3なので、4k+3型の奇数。言い換えれば:
　　《ね》　D ≡ 3 (mod 4)

D は、もちろん C よりでかい。もし D が素数だったらそれは C より大きい4k+3型素数であり、上記の仮定が間違ってたことが直ちに分かる。一方、D が合成数だとすると、D は、C 以下のどの4k+3型素数 p でも割り切れない（なぜなら《に》によれば、D は p の倍数より 1 小さい、つまり p の倍数ではない）。だが、仮定によれば C より大きい4k+3型素数は存在しない。ということは、D は4k+3型素数では一切割り切れないことになり、D の素因数は全部「4k+1型」でなければならない（D は奇数なので、因子2を含まない）。今、D が、次のように h 個の素因数に分解されたとしよう:
　　D = v₁v₂v₃…v_h
　　　ここで v₁, v₂, … は、どれも4k+1型素数（必ずしも相異ならない）
　　　言い換えると v₁, v₂, … は、どれも ≡ 1 (mod 4)
　　このとき　D = v₁v₂v₃…v_h ≡ 1⋅1⋅1⋅…⋅1 ≡ 1 (mod 4)
この最後の合同式は《ね》と矛盾する。□

〔例1〕　4k+3型素数が {3, 7} だけだと仮定（C = 7)。D = 4(3⋅7) − 1 = 83 は4k+3型素数で C より大きいので矛盾。

〔例2〕　4k+3型素数が {3, 7, 11} だけだと仮定（C = 11)。D = 4(3⋅7⋅11) − 1 = 923 = 13 × 71 と素因数分解される。71 は4n+3型素数で C より大きいので矛盾。

【2】　同様な方法で「4k+1型素数（愛称: バニラ素数）も無限にあること」も、示せそうな気がする。実際には、これは【1】より少し難しい。

Hardy & Wright は、この証明の完成を200ページくらい先延ばしして、x² + y² = n の解の個数の議論の特別な場合（n の因子としてチョコレート素数の1乗が含まれると、解がないこと）に帰着させている。高木は、フェルマーの小定理を使ってこれをあっさり片付け、続けて「一般に、ak+1型素数が無限にある」ことまで証明している（4k+1型は a=4 に当たる）。

以下ではまず高木の方法を紹介する。それは次の補題に依存している――含蓄があるものの、微妙に回りくどい。【3】では、この補題を使わないで済むような、ショートカットを研究しよう。

補題　b を任意の整数とする。b² + 1 が、4k+3型素数で割り切れることはない。

証明　p を 3 以上の素数とする。b² + 1 が p で割り切れるとする。
　　p で割り切れるということは　b² + 1 ≡ 0 (mod p)　つまり
　　《の》　b² ≡ −1 (mod p)

《の》の両辺を平方して b⁴ ≡ 1。補助定理1から、この指数 4 は b の位数の倍数。《の》から b の位数は 2 以下でないので、b の位数は「4」。補助定理1.1より、位数「4」は p − 1 の約数。従って
　　4 × 整数 = p − 1　つまり　p = 4 × 整数 + 1
と書ける。要するに、b² + 1 を割り切る 3 以上の素数 p は、必ず4k+1型。b² + 1 が、4k+3型素数で割り切れることはない。□

〔付記〕　原始根の存在を認めるなら…。p = 4k+3 のとき、《の》に解がない理由は、p − 1 = 4k+2 が 4 で割り切れないから（詳細）。補題の実体は、平方剰余の第一補充法則に他ならない。

定理（高木 §10.2）　4k+1型の素数が無限に存在する。

証明　矛盾を導くため、4k+1型の素数が有限個だと仮定する。すると、一番大きい4k+1型素数が存在がする。それを V としよう。このとき、4k+1型の全素数の積は:
　　5 × 13 × 17 × … × V
この積の平方の4倍に 1 を足したものを W とする:
　　《は》　W = 4(5 × 13 × 17 × … × V)² + 1　つまり
　　《ひ》　W = 2²(5 × 13 × 17 × … × V)² + 1 = (2 × 5 × 13 × 17 × … × V)² + 1

《は》から分かるように、W は4k+1型の奇数で V より大きい: もし W が素数なら直ちに矛盾が生じる。一方、W が合成数だとした場合、
　　b = 2 × 5 × 13 × 17 × … × V
と置くと、《ひ》は W = b² + 1 となるが、上の補題によれば、この数が4k+3型素数で割り切れることはない。つまり奇数 W が合成数なら、その素因数は4k+1型に限られる。ところが《ひ》から分かるように、V 以下のどの4k+1型素数で W を割っても、1 余ってしまい、割り切れない。要するに W が合成数なら、その素因数は4k+1型で、しかも V より大きい。いずれにしても最初の仮定は誤りで、V より大きい4k+1型素数が存在する。□

〔例3〕　4k+1型素数が {5, 13, 17} だけだと仮定（V = 17)。W = 4(5⋅13⋅17)² + 1 = 4884101 は4k+1型素数で V より大きいので矛盾。

〔例4〕　4k+1型素数が {5, 13, 17, 29} だけだと仮定（V = 29)。W = 4(5⋅13⋅17⋅29)² + 1 = 4107528101 = 37 × 173 × 641701 と素因数分解される。どの素因数も4n+1型で V より大きいので矛盾。

【3】　上記の高木の証明（若干改変している）は、フェルマーの小定理を直接使わず、位数の理論に依存する補題を経由している。以下では、この依存を取り除き、フェルマーの小定理だけを直接使って、同じ結論を得る。

ユークリッドは、素数のリストが有限だと仮定し「リストにある全素数の積プラス1」を考えて、矛盾を導いた。現代では、もう少し具体的に、最大の素数 N の存在を仮定して「N 以下の全素数の積プラス1」を考えることが普通だろう。以下でも V 以下の全素数の積を考える――ここで V は、勝手に選んだ4k+1型の素数。V をどう選んでも、さらに大きい4k+1型素数があることを示したい。それができれば「4k+1型素数は、際限なく、無限に存在する」ことが分かる。

高木の工夫をまねて「V 以下の全素数の積の2乗、プラス1」を考え、それをあらためて W と呼ぼう。
　　W = (2 × 3 × 5 × … × V)² + 1 = 4(3 × 5 × … × V)² + 1

この W は4k+1型の奇数で V より大きいので、もし W が素数なら、証明は完了する。一方、W が合成数の場合、その素因数の一つをどれでも勝手に選んで p とすると…。W は、V 以下のどの素数で割っても 1 余って割り切れないので、W の素因数 p は V より大きい。さて、W が p で割り切れるということは:
　　W ≡ 0　つまり　(2 × 3 × 5 × … × V)² + 1 ≡ 0 (mod p)
　　移項すると　(2 × 3 × 5 × … × V)² ≡ −1 (mod p)
この両辺を (p−1)/2 乗すると^〔注1〕:
　　《ふ》　(2 × 3 × 5 × … × V)^p−1 ≡ (−1)^(p−1)/2 (mod p)

〔注1〕　V は4k+1型の素数なので、最低でも5、p はそれより大きい素数なので奇数: (p−1)/2 は割り切れて整数になる。

p は素数なので、もちろん (2 × 3 × 5 × … × V) の倍数ではない。だから《ふ》の左辺にフェルマーの小定理を適用できる:
　　《へ》　(2 × 3 × 5 × … × V)^p−1 ≡ 1 (mod p)

分かりにくければ (2 × 3 × 5 × … × V) を b と置いてみよう。

《ふ》と《へ》の左辺同士は等しいので、もちろん右辺同士も等しい:
　　《ほ》　(−1)^(p−1)/2 ≡ 1 (mod p)
−1 の奇数乗は −1、偶数乗は 1 なので、(p−1)/2 が奇数か偶数かに応じて、《ほ》は
　　−1 ≡ 1 (mod p)　もしくは　1 ≡ 1 (mod p)
となる。前者は、ばかげている^〔注2〕。従って (p−1)/2 は偶数でなければならない: 2 で割って偶数になるのだから、(p−1) は 4 の倍数でなければならない。だから、とある整数 k を使って
　　p−1 = 4k　つまり　p = 4k+1
と書くことができる。すなわち、V より大きい4k+1型素数が存在する。それが示したいことだった。□

〔注2〕　A ≡ B (mod p) の意味は「A − B が p の倍数」。だから −1 ≡ 1 (mod p) の意味は「−2 が p の倍数」。上記の p は奇数なので「−2 が p の倍数」ということは不可能。

この別証明は、高木のオリジナル版から補題を除去して簡単化したもの。p は勝手に選んだ W の素因数であり、どの素因数を選んでもそれが4k+1型になることが示されたのだから、「W の素因数は4k+1型に限られる」という点に関しては、オリジナル版とそう変わらない。ただし W の定義が異なり、高木版と比べ、数値的には、無駄に大きい。「両辺を (p−1)/2 乗する」という操作も、若干、天下り的で不自然かもしれない。「遊び」としては、トリッキーな式変形もまた一興…

〔例5〕　4k+1型素数が {5, 13, 17} だけだと仮定（V = 17)。W = (2⋅3⋅5⋅7⋅11⋅13⋅17)² + 1 = 260620460101 = 1409 × 184968389 と素因数分解される。どの素因数も4n+1型で V より大きい。例3の W = 4(5⋅13⋅17)² + 1 = 4884101 に比べると、桁違いに大きい W を考えている。

今回の命題に関しては、Hardy & Wright の証明法を紹介すらしなかった（高木の証明の方が簡潔なので）。けれど Hardy & Wright の方法には、別の意味で価値がある。（続く）

2022-07-01　Hardy & Wright の古典的名著　その魅力と短所

日本語圏での数論の古典的名著といえば、高木の『初等整数論講義』だろう。この本は、ドイツ語圏の Dirichlet: Vorlesungen über Zahlentheorie の系譜に属する（当時、ドイツが数論の先進国だった――数学者 Gauß がお札の肖像画の国）。

さて、日本語圏では若干その陰に隠れる形になっているが、英語圏の Hardy & Wright: An Introduction to the Theory of Numbers も古典的名著だろう。現代の一般的な教科書と違い、厳密性や論理構造を第一目標にせず、面白さを優先している。著者自身が、心から楽しんでいる（高木の本もそうだが）。他のどの本にも載っていないような結果がどしどし紹介される一方、公理論的扱いは回避され、環は登場せず、イデアルも主役にならない。初版の序文にはこうある。

We have often allowed our personal interests to decide our programme, and have selected subjects less because of their importance [...] than because we found them congenial and because other writers have left us something to say.

講義内容を決めるに当たっては、自分たちの興味を優先させ、重要性にはあまりこだわっていません。個人的に心に響くと感じること、他の著者があまり書いていないことを積極的に取り上げています。

Our first aim has been to write an interesting book, and one unlike other books. We may have succeeded at the price of too much eccentricity, or we may have failed; but we can hardly have failed completely, the subject-matter being so attractive that only extravagant incompetence could make it dull.

第一目標は、面白い本、他とは違う本を書くこと。成功したかもしれませんが、その代わり、ひどくエキセントリックな本になってしまったかもしれません。あるいは失敗したかもしれません。でも完全な失敗ということもないでしょう――素材そのものが魅力的なので、よほど間抜けな料理人でもない限り、誰がどう料理しても、そうまずくはならないというわけです。

「エキセントリック」を象徴する例は Ramanujan…。Hardy はラマヌジャンの「発見者」ということもあって、入門書なのに、やたらとラマヌジャンの（奇妙な）研究が紹介される。特別な予備知識は、ほとんど何も要求されない。ベクトルも行列も必要ない。それでいて、代数的数論はもとより、解析的数論に踏み込むことがある。フェルマーの最終定理を証明した Wiles も、子どもの頃、本書で数論の幅広さを知り、それが全ての出発点になったという。

Curios! でおなじみの PrimePages には、この本について次のような趣旨のコメントがある。

「著者たち自身、内容に大きなギャップがあること、深みに欠けることを認めている。それなのに、なぜ本書は、これほどまでに高く評価される古典となったのだろうか。初版の序文を読むと、理由が分かる気がする」
https://primes.utm.edu/notes/hw_index.html

高木の序言のキーワードは「玲瓏にして…」だろう。論理的に完全な証明ができても、トリッキーで見通しが悪いと、高木は不満そうに「不透明」と評する。隅々まですっきり見通せる視点に到達すると、満足そうに「透明」と表現する。高木の講義は、透明なる高みへの明確な方向性を持つ。当時はまだ新奇だったイデアル論。「その意義を分かりやすく、順を追って解説したい」という強いモチベーションが感じられる。

一方、Hardy & Wright のキーワードは congenial（琴線に触れる）かもしれない。「重要かどうか」「どの方向に進みたいか」など、あまり気にしない。それ自体が好奇心を刺激すれば、それでいい。「興味深い話題を広く浅く」「あくまで出発点」というスタンス。

そんな楽しい H-W だが、短所としては、意外とミスプリントが多い。入門者の立場だと、ささいな誤植のせいでひどく混乱することがある…。さいわい最新版については正誤表が公開されているが、第4版ではなかった誤植が第6版で増えていたりして、訳が分からない。
https://www1.maths.ox.ac.uk/groups/number-theory/misprints-hardy-wright-and-titchmarsh

高木の本も H-W も基本的に「エリート志向」で、一般読者から見ると必ずしも親切ではない点もある（その気になればもっと整理・簡単化できる部分もある）。その点、Dirichlet の整数論講義^*1や、旧ソ連の「万人のための数学講義」（PLM^*2）シリーズは具体的で分かりやすく、しばしばハッとするような新鮮な視点を含んでいる。ドイツ語やロシア語というのは、別の意味で一般人には敷居が高いけど、部分的には英訳もされているし、数式は世界共通なので、語学的知識があまりなくても案外内容を理解できることもあるだろう。
*1 Dirichlet (& Dedekind): Vorlesungen über Zahlentheorie
https://archive.org/details/vorlesungenber00lejeuoft
*2 Популярные лекции по математике
https://math.ru/lib/ser/plm

5, 13, 17 のような「4で割って1余る素数」は無限に存在する。前回それを紹介したとき「高木の証明の方が美しい」というようなことを書いて H-W の証明法には触れなかった。

H-W の方法は、確かに4k+1型に関する限り非効率なのだが、4k+1型を8k+5型の特別な場合として扱う。8k+5型は、まともにやると平方剰余の議論になって少し深い。H-W は、それを割と初等的に、第1章でやってしまう（といってもギャップのある証明で、後からガウス整数を経由してギャップを埋めるのだが）。

Hardy & Wright は、今（2022年7月）普通に買うと、1～2万円くらいするかも（めちゃくちゃなドル高）。物理的に手に入れたい方は、図書館で借りるのが最も現実的かもしれない。「ポンド払いで英国の古本屋さんから送ってもらう」という方法もあり、探せば数千円で入手できるかもしれない。裏技としては、中国版という手も（哈代数论英文版）。かつて日本語訳が発行されたこともあるのだが、これは残念な品質だった: まれに見る機械的な直訳。訳した人は立派な数学者なのだろうけど、語学・翻訳に関しては経験が浅かったらしい。文の流れが分からなくて1語1語無理やり訳しているような箇所や、結果として意味が正反対になっている箇所が目立った。

一般に A, B が互いに素のとき、Ak+B型の素数が無限にあることは Dirichlet の定理であり、その証明は長くて難しい（厳密志向の高木は付録としてこれを証明しているが、楽しさ志向の H-W は証明しない）。

実は「無限に存在すること」を証明しなくても「少なくとも一つ存在すること」を証明できれば十分。ポーランドの数学者 Sierpiński が丁寧に解説している。
Sierpiński: Elementary Theory of Numbers
https://eudml.org/doc/219306

Ak+B の一般論は難しくても、いろいろな具体的な A と B の値については（例えば 4k+1 のような特別な場合は）、直接証明できる。この件は、もう少し研究してみる価値がありそうだ！　（続く）

2022-07-03　4k+1型素数の無限　Hardy & Wrightバージョン

【1】　4k+1型の素数、つまり4で割って1余る素数（5, 13, 17 など）をバニラ素数と呼ぶことにする。バニラ素数が「有限種類しかない」と仮定して、矛盾を導く。この仮定上では、最大のバニラ素数 V が存在する。今 V 以下の全奇素数の積を t とする:
　　t = 3 × 5 × 7 × 11 × … × V
そして t² + 4 を W とする:
　　《ま》　W = (3 × 5 × 7 × 11 × … × V)² + 2²

この数は、奇数の平方に 4 を足したものなので奇数: 2で割り切れない。5 以上 V 以下のどの素数で割っても 4 余って割り切れないし、3 で割ると 1 余って割り切れない。つまり W は V 以下の素数では割り切れず、W の素因数は、どれも V より大きい（W 自身が素数である可能性も含まれる）。ここで Hardy & Wright は、次の補題を使う。

補題（H&W13）　x と y が互いに素なら、x² + y² の奇数の素因数は、バニラ素数に限られる。

この補題によると、上記 W の素因数はバニラ素数。つまり V より大きいバニラ素数が存在し、バニラ素数が「有限個しかない」という仮定は正しくない。□

高木の補題「x² + 1 は4k+3型素数で割り切れない」（＝第一補充法則）は H&W13 の特別な場合に当たる。

上記の証明だけでは、あまり収穫がない（もっと簡単に同じ結論を導ける）。ところが――

【2】　奇数 1, 3, 5, 7, … の平方 1, 9, 25, 49, … は、どれも8で割ると1余る（つまり8k+1型の奇数）。

〔証明〕　任意の偶数は「2の倍数」なので、2a の形を持つ（a は、とある整数）。奇数は「偶数プラス1」なので、2a+1 の形を持つ。その平方は:
　　(2a+1)² = 4a² + 4a + 1 = 4 × a(a+1) + 1
a と a+1 の一方は奇数、他方は偶数なので、a(a+1) は奇数と偶数の積で、偶数: 2k の形を持つ（k は、とある整数）。だから:
　　(2a+1)² = 4 × a(a+1) + 1 = 4 × 2k + 1 = 8k+1
となる。□

(3 × 5 × 7 × 11 × … × V)² も「奇数の平方」なので、8k+1の形を持つ。従って、それに4を足した《ま》は、8k+5型の奇数。

「4で割って1余る自然数」を小さい順に並べると、
　　1, 5, 9, 13, 17, 21, 25, …　「4k+1型」（1から始めて4ずつ増える）
となり、当たり前のことだが「8で割ると1余る数」と「8で割ると5余る数」が交互に現れる:
　　1, 9, 17, 25, …　「8k+1型」（1から始めて8ずつ増える）
　　5, 13, 21, …　「8k+5型」（5から始めて8ずつ増える）
つまり、4k+1型の数は、8k+1型と8k+5型の2種類に分類可能。

さて、《ま》の素因数が4k+1型に限られることは【1】の通りだが、それらは果たして、8k+1型だろうか、それとも8k+5型だろうか？

8k+1型の数同士を掛け合わせても、再び8k+1型にしかならないことに注意しよう。

〔例〕　9 × 17 = 153 = 8⋅19 + 1

〔証明〕　任意の2個の8k+1型の数、8a+1 と 8b+1 を選ぶ。それらの積は:
　　(8a+1)(8b+1) = 8a × 8b + 8a + 8b + 1 = 8(a × 8b + a + b) + 1
これは、8の倍数プラス1。□

〔別証明〕　A ≡ 1, B ≡ 1 の積は AB ≡ 1 (mod 8)。□

従って、もしも《ま》の W の素因数が「全部8k+1型」なら、それらの積 W は再び8k+1型になるが、実際には W は8k+5型なのだから、その素因数が「全部8k+1型」ということは、あり得ない。つまり W の素因数の少なくとも一つは8k+5型（そして、W のどの素因数も V より大きい）。このことは「どんな大きな V を選んでも、V より大きい8k+5型素数が存在すること」を意味する。要するに、8k+5型素数も際限なく存在する。新しい事実が判明した！

〔例1〕　バニラ素数が {5, 13} だけと仮定。W = (3⋅5⋅7⋅11⋅13)² + 4 = 225450229 は8k+5型素数。

〔例2〕　バニラ素数が {5, 13, 17} だけと仮定。W = (3⋅5⋅7⋅11⋅13⋅17)² + 4 = 65155115029 は8k+5型。その素因数分解は 53 × 3821 × 321733 で、どの因数も8k+5型で V より大。

〔例3〕　バニラ素数が {5, 13, 17, 29} だけと仮定。W = (3⋅5⋅7⋅11⋅13⋅17⋅19⋅23⋅29)² + 4 = 10464232622576958229 は8k+5型。その素因数分解は 4229 × 59753 × 41410453417。3個の素因数のうち、4229 は8k+5型、残り2個は4k+1型（8k+5型の2数の積は8k+1型なので、W の素因数分解には、8k+5型素数が奇数個含まれる）。

☆　追記: 実は高木の方法からも、8k+5型素数の無限を導ける（高木の逆襲？【3】）。

【3】　証明を完成させるためには、補題（H&W13）を示す必要がある。4k+3型素数をチョコレート素数と呼ぶことにする。

証明　x² + y² = n と置いて、n の素因数を考える。ガウス整数を使って書き直すと:
　　(x + yi)(x − yi) = n
　　G = x + yi, H = x − yi と置くと　GH = n
ガウス整数の範囲で、G が s 個のガウス素数の積に分解されるとしよう:
　　G = P₁P₂…P_s
このとき G と共役の H も、s 個のガウス素数の積に分解される:
　　H = Q₁Q₂…Q_s　（対応する因子 P_○ と Q_○ もそれぞれ共役）

普通の素数との関係において、ガウス素数は、「普通の素数2を二つに砕いたもの（ramified）」「バニラ素数を二つに砕いたもの（split）」「チョコレート素数そのもの（inert）」の3種類に分類される（単数倍の違いは無視）。

G の因子 P_○ のどれかが「2を砕いたもの」（例えば 1 + i）だったとすると、対応する Q_○ はその共役 1 − i なので、GH = n は P_○Q_○ = 2 で割り切れる。この場合、n は素因数 2 を持つ（偶数の素因数）。

一方、P_○ のどれかが「バニラ素数 v を砕いたもの」（例えば 2 + i）だったとすると、対応する Q_○ はその共役なので、GH = n は P_○Q_○ = v で割り切れる。この場合、n はバニラ素数の因数 v を持つ（奇数の素因数）。

最後に、P_○ のどれかがチョコレート素数 c（例えば 7）という可能性はあるだろうか？　もしあったとすると、G = x + iy が P_○ によって――つまり普通の整数 c によって――割り切れるのだから、x も y も c で割り切れる。これは「x と y は互いに素」という仮定に反するので、あり得ない。

従って、n の奇数の素因数は、バニラ素数に限られる。□

この補題の証明は、入門書の第1章で扱うには、適さないだろう。Hardy & Wright もそれを第20章（定理366）まで先延ばしにしているが、そこで4種類もの証明を与えている。しかも、それは4平方和の定理（定理369）という、もっと大きな文脈の中での話であり、4平方和の定理自身にも、全く趣の違う3種類の証明が与えられている。一つ目は古典的だが、二つ目は四元数を使うもの（！）、三つ目は楕円関数に関連する Ramanujan 的アプローチ（！！）。Hardy & Wright の醍醐味といえよう…。ありふれたフランス料理をアイルランド風や、インド風にアレンジする天才シェフのようだ。

論理的には、同じことを別の方法で3度も4度も証明し直す必要はないんだけど、やっぱり「楽しいから！」なんだろう。「四元数」なんて意表を突くアプローチは、何ともマニアックで好奇心を刺激される。

かくして、4k+1型素数（バニラ素数）が無限に存在することだけでなく、8k+5型素数も無限に存在することが証明された。事実として 8k+1, 8k+3, 8k+5, 8k+7 型素数は、それぞれ無限にあるのだが、そのことを普通に証明しようとすると、平方剰余の繊細な議論になる（Sierpiński: Elementary Theory of Numbers, Chap. IX）。8k+5型のショートカットは、ちょっぴりいい気分…。（下へ続く）

2022-07-04　4k+1型素数の無限（続き）

【4】　前記 Hardy & Wright の証明には、改善の余地がある。必要最小限でいいのなら、まず補題を次のように簡単化できる。

補題（H&W13改）　x と y が互いに素なら、x² + y² はチョコレート素数では割り切れない。

証明　x² + y² = (x + yi)(x − yi) がチョコレート素数 c で割り切れたとする。c はガウス整数の世界でも素数なので、(x + yi) と (x − yi) の少なくとも一方は c で割り切れる。これは x と y がどちらも c で割り切れることを意味し、「x と y が互いに素」という仮定に矛盾。□

この準備の下で、
　　V以下の全奇素数の積　t = 3 × 5 × 7 × 11 × 13 × … × V
の代わりに、より小さな
　　V以下の全バニラ素数の積　t = 5 × 13 × … × V
を使うことができる。このとき、奇数 t² + 2² は、もちろん2で割り切れず、V以下のどのバニラ素数で割っても4余るので、その素因数はチョコレート素数でなければならない。ところが、上の補題から t² + 2² はチョコレート素数では割り切れない。矛盾。□

〔例1〕　バニラ素数が {5, 13} だけだと仮定（V = 13）。t = 5 × 13 = 65, t² + 2² = 4229。これはバニラ素数なので、仮定は間違っている。

〔例2〕　バニラ素数が {5, 13, 17, 29} だけだと仮定（V = 29）。t = 5 × 13 × 17 × 29 = 32045, t² + 2² = 1026882029 = 229 × 4484201 と素因数分解される。どちらの因数も、V より大きいバニラ素数。

【5】　4k+1型素数が無限にあることは、フェルマーの小定理だけできれいに証明できるのだから、ガウス整数を持ち出すのは（面白いけど）実用上、大げさ過ぎるように思える。けれど何事も試してみると収穫があるもので、ちょっとひらめいた: 上記の証明法のアイゼンシュタイン整数版を考えたら…？

補題（？）　x と y が互いに素のとき、3x² + y² の奇数の素因数は、決して3k+2型ではない。

定理　3k+1型素数は無限に存在する。

証明　3k+1型素数が有限個だと仮定して、矛盾を導く。最大の3k+1型素数を M として、M 以下の全部の3k+1型素数の積を t とすると、
　　3t² + 2² = 3(7 × 13 × 19 × … × M)² + 4
という奇数は、2でも3でも割り切れず、M以下のどの3k+1型素数で割っても4余るので、その素因数は、3k+2型の奇数。これは、上の補題（？）と矛盾する。□

この証明が有効なら、Hardy & Wright 定理14（8k+5型素数の無限）の素敵な応用といえるだろう！

問題は、補題（？）の部分。3k+1型素数が 3x² + y² の形を持つこと、3k+2型素数はこの形を持たないことは、アイゼンシュタイン整数を使って証明できる。さらに、3 はこの形を持ち（x = 1, y = 0）、4 もこの形を持つ（x = 1, y = 1）。これらの事実と
　　「3x² + y² の形の数は、原則として 3x² + y² の形以外の約数を持つことができない」
という性質を組み合わせると、およそ補題（？）の内容になりそうだ。

「3k+1型素数が無限にある」という事実だけなら、アイゼンシュタイン整数など持ち出すまでもなく、古典的な方法で証明できるだろうが、これはこれで、うまくいけば面白い。

3k+1型の整数は、6k+1型と6k+4型に分けられるが、3k+1型素数は奇数なので、どれも6k+1型。従って、上記の結論から、6k+1型素数が無限にあることも自動的に証明される！

【6】　H&W13の別証明（ガウス整数を使わない）。とりあえず x² + 4 がチョコレート素数 p で割り切れないことを言えば十分。これは、
　　《み》　x² + 4 ≡ 0　つまり　x² ≡ −4 (mod p)
の解の有無の問題。さて p がバニラでもチョコでも、x² ≡ 4 (mod p) には、もちろん解 x ≡ ±2 がある。一方、x² ≡ −1 (mod p) については、p がバニラなら解 x ≡ ±z^(p−1)/4 があるが（z は任意の原始根）、p がチョコなら解がない。従って p がバニラなら、《み》は次の解を持つ:
　　x ≡ ±2z^(p−1)/4
　　実際このとき　x² ≡ 2²z^(p−1)/2 ≡ −4

逆に 4z^(p−1)/2 ≡ −4 (mod p) が平方剰余としよう。合同式の基本性質として、4 と p が互いに素なら（p が奇素数なら常にそうなる）、この両辺を 4 で割ることができ、従って問題は −1 が平方剰余か否かに帰着される。

同様に考えると、一般に任意の整数 y が奇素数 p の倍数ではないとき、
　　《む》　x² + y² ≡ 0　つまり　x² ≡ −y² (mod p)
は、p がバニラなら解を持ち、p がチョコレートなら解を持たない。すなわち x² + y² の奇数の素因数は（x, y が互いに素という条件で）、バニラ素数に限られる。

〔例〕　x² = −4 (mod 13) は解を持つ。原始根として z = 2 を使うと、一つの解は x ≡ 2 × 2^(13−1)/4 ≡ 16 ≡ 3。実際 3² ≡ 9 ≡ −4。
x² ≡ −4 (mod 17) は解を持つ。原始根として z = 3 を使うと、一つの解は x ≡ 2 × 3^(17−1)/4 ≡ 162 ≡ 9。実際 9² ≡ 81 ≡ −4。
x² ≡ −9 (mod 17) は解を持つ。原始根として z = 3 を使うと、一つの解は x ≡ 3 × 3^(17−1)/4 ≡ 243 ≡ 5。実際 5² ≡ 25 ≡ −9。
一方、x² = −4 (mod 11) は解を持たない。実際 x ≡ ±1, ±2, ±3, ±4, ±5 に対して x² ≡ 1, 4, 9 ≡ −2, 16 ≡ 5, 25 ≡ 4。

2022-07-05　何となくフラクタル　3k+1, 9k+1, 27k+1…型素数の無限

シェルピンィスキーによる「初等的だけどワクワクする証明」。

【1】　3k+1型素数は、無限に存在する。それを直接証明する標準的方法は、x³ − 1 = (x − 1)(x² + x + 1) を利用するもの。この手法を一般化すると、Nk+1型素数（Nは3以上の任意の整数）が無限にあることを証明できるが、少々敷居が高い（円分多項式が絡んでくる）。

以下の方法は、いきなり一挙に一般化せず、Bk+1型素数（Bは3のべき）に話を限り、ある程度の具体性を持たせて、とっつきやすくしたもの。

【2】　3以外の素数は、3で割って1余るもの（7, 13, 19など）つまり3k+1型と、3で割って2余るもの（2, 5, 11, 17など）つまり3k+2型（別名3k−1型）の二つに分けられる。後者が無限に存在することは、4k+3型と同様に、簡単に証明できる。前者が無限に存在することの証明は、比較的難しい（4k+1型と同様）。

参考として、「3k+1型素数が無限にあること」を示すユークリッド風の証明を2パターン、付録として収録した（【8】【9】）。

【3】　Sierpiński が記述しているのは、もっと強力な方法。3k+1型, 3²k+1型, 3³k+1型…の素数がそれぞれ無限にあることが、一気に示される。5k+1型, 5²k+1型, 5³k+1型…や、7k+1型, 7²k+1型, 7³k+1型…などにも、そのまま一般化される。

Sierpiński: Elementary Theory of Numbers, Chap. VI §5, Theorem 11 以下。
http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4206.pdf
事実としては、高木の§10.3の内容をなだらかにしただけだが…

3² = 9で割って1余る素数（19, 37など）は、もちろん3で割っても1余る。3³ = 27で割って1余る素数（109など）は、3で割っても1余るし、9で割っても1余る。3⁴ = 81で割って1余る素数は…。以下同様。

従って 3k+1型, 3²k+1型, 3³k+1型, 3⁴k+1型…と無限に続く型の系列について、それぞれの型の素数をたった1個でも選択できるのなら（どの型の素数も互いに異なるように、選択できるのなら）、3k+1型素数は無限個存在することになる。

言われてみれば当たり前のことなんだけど、すごい発想だよね、これっ！

【4】　素数「3」の s 乗を B として、Bk+1型の素数を考える。
　　s = 1　⇒　B = 3¹ = 3　この場合、Bk+1型とは「3k+1」型
　　s = 2　⇒　B = 3² = 9　Bk+1型＝「9k+1」型
　　s = 3　⇒　B = 3³ = 27　Bk+1型＝「27k+1」型
　　s = 4　⇒　B = 3⁴ = 81　Bk+1型＝「81k+1」型
　　etc.
一般に「Bk+1」型、つまり「3^sk+1」型の素数が無限にあることを示したい（s は任意の正の整数）。

B = 3^s の指数を 1 減らした 3^s−1 を C として、a = 2^C と置く:
　　a = 2^C = 2^3s−1　（2 の 3^s−1 乗）
次の単純な関係に注意:
　　B = 3^s　（s 個の「3」の積）
　　C = 3^s−1　（s−1 個の「3」の積。掛け合わせる「3」の個数が B より1少ない）
　　B = 3C　（C にもう1個「3」を掛け算すれば、s 個の「3」の積になって B に等しい）
　　《ア》　a³ = (2^C)³ = 2^3C = 2^B

さて、次の恒等式を考えよう:
　　《イ》　a³ − 1 = (a − 1)(a² + a + 1)

s の値を選んで固定すると a の値は定まり、《イ》の因子 a² + a + 1 の値も定まる。この
　　《ウ》　a² + a + 1
の素因数分解を考え、出てきた素因数をどれでも一つ選んで q としよう。a² と a は偶数なので（2のべきだから）、《ウ》は奇数。従って、その素因数 q も奇数。q は《イ》右辺の因子 a² + a + 1 の約数だから、《イ》左辺 a³ − 1 は q で割り切れる。

〔例1〕　s = 1 のとき B = 3¹ = 3, C = 3⁰ = 1, a = 2^C = 2 なので a² + a + 1 = 2² + 2 + 1 = 7。その素因数は q = 7 自身。a³ − 1 = 7 は、この q で割り切れる（商は1）。

〔例2〕　s = 2 のとき B = 3² = 9, C = 3¹ = 3, a = 2^C = 8 なので a² + a + 1 = 8² + 8 + 1 = 73。その素因数は q = 73 自身。a³ − 1 = 511 は、この q で割り切れる（商は7）。

〔例3〕　s = 4 のとき B = 3⁴ = 81, C = 3³ = 27, a = 2^C = 2²⁷ = 134217728 となって、
　　a² + a + 1 = 18014398643699713 = 2593 × 71119 × 97685839
と素因数分解される。q として 2593 または 71119 または 97685839 を選択可能。
　　a³ − 1 = 2417851639229258349412351
は、そのどれでも割り切れる。

a は「2 を 3^s−1 個掛け合わせたもの」なので、s が大きくなるとき、a² + a + 1 は、めちゃくちゃでかくなる。でも、気にする必要ない。重要なのは具体的な q の値の計算ではなく、「素数 q が存在する」というシンプルな事実（どんな巨大な数でも、それ自身素数か、または素数の積で表される）。

a³ − 1 は素数 q で割り切れるので、それより 1 大きい a³ を q で割ると 1 余る:
　　《エ》　a³ ≡ 1 (mod q)
《ア》を使って書き換えると:
　　《オ》　2^B ≡ 1 (mod q)

【5】　mod q での 2 の位数――つまり 2^□ ≡ 1 (mod q) の □ に当てはまる最小の正の整数――を e とする。位数の基本性質（補助定理1）によると、《オ》左辺の指数 B は e の倍数。言い換えれば e は B の約数。B の定義は 3^s なので（そして 3 は素数なので）、B = 3^s の約数ということは、e は…
　　《カ》　1, 3, 3², 3³, …, 3^s−1 (=C), 3^s (=B)
…のどれか。後述する簡単な議論によると（【7】参照）、実は 2^C ≢ 1 (mod q)。従って e = B となる。

〔解説〕　2 の位数を e とすると（2^e ≡ 1）、e の任意の倍数 eX は 2^eX ≡ 1 (mod q) を満たす（なぜなら 2^eX = (2^e)^X ≡ 1^X = 1）。例えば、もしも e = 3² が 2^□ ≡ 1 の □ に当てはまる最小なら、その e の倍数である 3³ や 3⁴ も □ に当てはまる（最小ではないが）。逆に考えると、2^C ≡ 1 ではないのだから、C は e の倍数ではない: e は C の約数ではない。位数かもしれない数のリスト《カ》において、C = 3^s−1 以下の数は全部 C の約数。「e は C の約数ではない」という条件から、e = B (> C) という選択肢しか残らない（2^B ≡ 1 であることは《オ》で確認済み）。

2 はもちろん奇数 q の倍数ではないので、フェルマーの小定理が使えて、2^q−1 ≡ 1 (mod q)。位数 e = B は q − 1 の約数（補助定理1.1）。言い換えれば、q − 1 は B の倍数。こう書ける:
　　q − 1 = Bk　（k はとある整数）
　　つまり　q = Bk + 1

結論として、Bk+1型の――つまり 3^sk + 1 の形の――素数 q が少なくとも一つ存在する（s は任意の正の整数）。これが証明したいことだった。□

〔例4〕　s = 3 のとき B = 3³ = 27, C = 3² = 9, a = 2^C = 512 なので a² + a + 1 = 262657。その素因数は q = 262657 自身。この q を法として 2^C = 2⁹ = 512 ≢ 1 だが、2^B = 2²⁷ = 134217728 ≡ 1。実際、134217728 = 511q + 1。このとき q = 262657 は27k+1型素数。実際、262657 = 27 × 9728 + 1。

【6】　この証明は、「3」という部分を「任意の素数 p」に変えても、ほぼそのまま成り立つ。フェルマーの小定理と、初歩的な位数の理論だけを使い、平方剰余に依存せず、円分多項式の一般論にも直接には依存しない。

「少なくとも一つ」は弱い表現で、実際には、a² + a + 1 の相異なる素因数の個数だけ q の選択肢があり、少なくともその数だけ「3^sk+1型」素数がある。s は任意の正の整数: 正の整数は無限個あるので、各 s について「少なくとも一つ」の素数があるだけで、3k+1型素数の合計個数は無限になる。s = 2 を基準にしても、2以上の s は無限個あるので、結論は同じ（9k+1型素数が無限にある）。s = 3 なども同様。

従って、3k+1型の素数だけでなく、9k+1型の素数、27k+1型の素数…が無限に存在することも、同時に証明されたことになる。

有限個の素因数 q が繰り返し現れる可能性はないか？　有限個の q が（無限にループして）繰り返し現れるのなら「3k+1型素数は無限にある」という結論が怪しくなる。だけど、同一の q が反復して現れるなら、その同一の q を法とした 2 の位数は、もちろん同一。実際には s が増加するにつれて、この位数 B = 3^s も増加する。つまり s が違えば q も違い、反復は生じない。

（下に続く）

2022-07-06　何となくフラクタル（続き）

【7】　後回しにした 2^C ≢ 1 (mod q) つまり a ≢ 1 (mod q) の証明。

《ウ》の a² + a + 1 は q で割り切れるので（そのように q を選んだ）、
　　a² + a + 1 ≡ 0 (mod q)
…となるが、もしも a ≡ 1 (mod q) なら、上の式の左辺は ≡ 1² + 1 + 1 ≡ 3 となるから:
　　3 ≡ 0 (mod q)
つまり 3 が q で割り切れてしまう。3 も q も素数なので、約数の選択肢は非常に狭い。割り切れるとしたら q = 3 に固定されてしまう。

上記の例1～例4から分かるように、実際には q = 3 に固定されるわけではない（それどころか q = 3 のケースは全くない）。だから、上の推論がおかしいこと、つまり a ≡ 1 (mod q) という仮定が間違ってることは、ほぼ明らかだろう。以下では、このことをきちんと示す。

もしも q = 3 なら、《オ》はこうなる:
　　《キ》　2^B ≡ 1 (mod 3)

ところが、フェルマーの小定理から 2³⁻¹ ≡ 1 (mod 3): その両辺を 2 倍すると、
　　《ク》　2³ ≡ 2 (mod 3)
が成り立ち、そこから次々とこうなる:
　　(2³)³ ≡ (2)³ ≡ 2　（左端の丸かっこ内の 2³ を《ク》で簡約）
　　[(2³)³]³ ≡ [2]³ ≡ 2　（左端の角かっこ内を上の式で簡約）
　　{[(2³)³]³}³ ≡ {2}³ ≡ 2　（左端の波かっこ内を上の式で簡約）
　　etc.
要するに「2 の 3乗」「2 の 3²乗」「2 の 3³乗」「2 の 3⁴乗」…一般に「2 の『3 のなんたら乗』乗」は、全部 ≡ 2 (mod 3) となる。

事実、次が成り立つ:
　　2³ = 8 ≡ 2 (mod 3)
　　2⁹ = 512 ≡ 2 (mod 3)
　　2²⁷ = 134217728 ≡ 2 (mod 3)
　　etc.

さて、B = 3^s だから、2^B も「2 の『3 のなんたら乗』乗」。だから 2^B ≡ 2 (mod 3) が正しく、《キ》は間違い。事実に反する《キ》が生じた原因――「もしも a ≡ 1 (mod q) なら」という仮定――は、不合理だった: 正しくは a ≢ 1 (mod q) であり、a = 2^C だから
　　2^C ≢ 1 (mod q)
と結論される。□

〔注意〕　《オ》で見たように 2^B ≡ 1 (mod q) が成り立つ。《キ》が不合理だというのは「《オ》が間違ってた」という意味ではなく、「《オ》で q = 3 にはならない」という意味。《ウ》の a² + a + 1 の素因数 q は《オ》を成り立たせるけど q = 3 にはならないよ…ってこと。

【8】　付録。「3k+1型素数は無限個」のユークリッド風の証明。

以下の証明法は面白くないかもしれないが、比較することで、Sierpiński の証明法の美しさ・スケールの大きさが感じられる。

3k+1型素数をミント素数、3k+2型素数をワッフル素数と呼ぶことにする。

矛盾を導くため、ミント素数が有限個しかない（★）と仮定し、最大のミント素数を M とする。全ミント素数の積の3倍を a としよう:
　　a = 3 × (7 × 13 × 19 × … × M)
a は奇数の積なので、奇数。ここで
　　b = a² + a + 1
という数を考えると、この数は、仮定上、どのミント素数で割っても（1余って）割り切れない。b は3個の奇数の和なので奇数であり、2 でも割り切れない。b が 3 で割り切れないことも明白（a² と a は3の倍数なので、b を 3 で割ると1余る）。従って、b のどの素因数 q も、2 でも 3 でもなく、ミント素数でもない。要するに q は 5 以上のワッフル素数のはず…（仮定（★）が正しいならね）。

a は q の倍数ではない（a が q の倍数なら b = a² + a + 1 を q で割ると 1 余ってしまい、q は b の因数という仮定に反する）。素数 q と、その倍数ではない a は、互いに素。このことから、mod q での a の位数を考えることができる。以下では、この位数を問題にする。

〔参考〕　次のように論じてもいい。b の形から、b を a に含まれるどの素因数（3, 7, 13など）で割っても、1余って割り切れない。つまり a と b は互いに素。q は b の因数なので、もちろん a と q も互いに素。

さて、q は b = a² + a + 1 の約数だから、a³ − 1 = (a − 1)(a² + a + 1) は q で割り切れる:
　　a³ − 1 ≡ 0 (mod q)　つまり　a³ ≡ 1 (mod q)
すなわち mod q において、3 は a の位数の倍数: a の位数は 1 か 3 のどちらかだが…
　　（妄想の世界）
　　もしもよ～　a の位数が １ だとするじゃん？　それって
　　a¹ ≡ a ≡ 1 (mod q) っつー意味じゃん？　それってよ～
　　b = a² + a + 1 ≡ 1² + 1 + 1 ≡ 3 (mod q) ってことじゃん？
　　だから b を q で割ると 3 余るんだぜ。だって q は 5 以上だもんな…
　　（妄想終了）
… b は q で割り切れると仮定しているのだから、この妄想は不合理。消去法で a の位数は 3。

a は q の倍数ではないので、フェルマーの小定理が使えて:
　　a^q−1 ≡ 1 (mod q)

q は 5 以上のワッフル素数のはずだったが、a の位数 3 は q − 1 の約数でなければならないので、
　　3k = q − 1　（k はとある整数）
と書ける。つまり q = 3k + 1。この素数 q は、明らかに3k+1型（ミント素数）。矛盾。□

〔例〕　ミント素数が {7, 13, 19} だけだと仮定（M = 19）。
　　a = 3(7 × 13 × 19) = 5187
　　b = a² + a + 1 = 26910157 = 127 × 211891
と素因数分解される。q = 127 とすると:
　　a³ − 1 = 139556074202 は、当然 q = 127 で割り切れる。
　　従って　a³ ≡ 1 (mod 127)
　　しかし　a¹ ≡ 107 ≢ 1 (mod 127)
mod 127 での a の位数は 3。そのことから、素数 127 は3k+1型（ミント素数）。b のもう一つの素因数 211891 も、同様にミント素数。

【9】　付録2。「3k+1型素数は無限個」のユークリッド風の別証明（平方剰余を使う）。

補助命題　どんな整数 x を考えても、x² + 3 が、2以外のワッフル素数で割り切れることはない。

〔解説〕　p がミント素数の場合の例として、p = 7 を考える。x ≡ 0, ±1, ±2, ±3 (mod p) に対して x² はそれぞれ 0, 1, 4, 9。それぞれ 3 を足すと 3, 4, 7, 12。つまり x ≡ ±2 とすれば、x² + 3 ≡ 7 は p で割り切れる。一方、p が「2以外のワッフル素数」の場合には、このような x が存在しない…というのが命題の意味。

〔例1〕　ワッフル素数 p = 5 を考える。x ≡ 0, ±1, ±2 (mod p) に対して x² はそれぞれ 0, 1, 4。それぞれ 3 を足すと 3, 4, 7 で、どれも p で割り切れない。

〔例2〕　ワッフル素数 p = 11 を考える。x ≡ 0, ±1, ±2, ±3, ±4, ±5 (mod p) に対して x² はそれぞれ 0, 1, 4, 9, 16, 25。それぞれ 3 を足すと 3, 4, 7, 12, 19, 28 で、どれも p で割り切れない。

定理　ミント素数は無限に存在する。

証明　矛盾を導くため、ミント素数が有限個しかないと仮定し、最大のミント素数を M とする。全ミント素数の積の2倍を x とする:
　　x = 2 × (7 × 13 × 19 × … × M)
このとき
　　x² + 3 = (2 × 7 × 13 × 19 × … × M)² + 3
という数は、明らかに 2 でも 3 でも割り切れないし、仮定上、どのミント素数で割っても 3 余って割り切れない。だから、その素因数は全部「2以外のワッフル素数」のはず。だが、補助命題によれば、この形の数は「2以外のワッフル素数」では割り切れない。矛盾。□

ロジックは単純だが、証明の設定がちょっと天下り的かもしれない。補助命題の証明の背景については、平方剰余の相互法則を参照――そちらでは (A|p) の代わりに、同じ意味で L(A, p) という表記が使われている。

〔補助命題の証明〕　「2 以外のワッフル素数」を法として −3 が平方非剰余であることを言えばいい。mod 3 では (±1)² ≡ 1 なので、1 は平方剰余、2 は非剰余。さて、法 p が 3 以外の奇素数の場合:
①　p がバニラ素数なら (−1|p) = +1。さらに (3|p) = (p|3) = +1 ⇔ p ≡ 1 (mod 3)。
②　p がチョコレート素数なら (−1|p) = −1。さらに (3|p) = −(p|3) = −1 ⇔ p ≡ 1 (mod 3)。
どちらでも p ≡ 1 (mod 3) ⇔ (−3|p) = (−1|p)(3|p) = 1　［①では (+1)(+1)、②では (−1)(−1)］
一方、法が偶素数つまり 2 の場合: −3 ≡ 1 ≡ 1² なので、−3 は平方剰余。まとめると、−3 は、法が「ミント素数または 2」なら平方剰余、法が「2 以外のワッフル素数」なら非剰余。□

〔補足〕　法が 3 の場合はトリビアル: −3 ≡ 0 ≡ 0² はもちろん平方剰余。上記の (A|p) のような表記は、ルジャンドル記号。x² ≡ A (mod p) に解があれば +1、解がなければ −1 を表す（A は p の倍数以外）。

〔追記〕　平方剰余の相互法則を使わずに、補助命題を直接証明することもできる。「12k+7型（チョコ・ミント）素数の無限」を参照。（2022年10月21日）

2022-07-09　5k+1型素数の無限　再び素数レースのイカサマ

1, 5, 9, 13, 17, 21, …

これは 1 から始まり 4 ずつ増える数の列。つまり4k+1型の自然数（k = 0, 1, 2, …）。この中には、素数が無限個存在する（5, 13, 17など）。合成数も無限個存在する（9, 21など）。

【1】　Dirichlet の定理によれば、4k+1型に限らず、一般に「mk+r型」の素数が、無限に存在する。ここで m と r は互いに素な定数（自然数）。

m と r が互いに素でなければ（つまり 2 以上の公約数 d を持つなら）、mk+r は（k の値と無関係に）いつも d で割り切れてしまい、話にならない。

Dirichlet の定理の（上記の意味での）内容はシンプルだが、証明は難しい。でも m と r が特定の値の場合には（3k+1型、3k+2型、4k+1型、4k+3型、5k+1型など）、簡単に証明できることもある。

一般的証明について、1931年、高木は「証明が初等的でないのが遺憾であるが、数学の現状ではやむを得ない」「直接に証明することは未開の謎である」と記した。1976年、Apostol は「no one has yet found such a simple argument that works for the general [case mk+r]」と記した。

「現状では難解だが、数論が進歩すれば、そのうち誰かがうまい証明法を発見するかも…」という希望が、あったのだろう。

ところが、1988年、Murty は「ユークリッド風の簡単な証明ができるのは r² ≡ 1 (mod m) の場合だけ」ということを証明した。何ということだろう、一般の場合については「簡単には証明できないこと」が証明されてしまったのである！

例えば、2² = 4 や 3² = 9 は ≡ 1 (mod 5) ではないので（つまり、5で割った余りが1ではないので）、5k+2型素数が無限にあること、5k+3型素数が無限にあることについては、ユークリッド風の簡単な証明は不可能。実は「5k+2型または5k+3型」の素数が無限にあることの証明は初等的だが、「または」を外して「5k+2型」「5k+3型」素数がそれぞれ無限にあることを証明しようとすると、ユークリッド風にはできない。

ユークリッド風＝「これこれの型の素数は有限個しかない」と仮定し、それらの素数全部の積 x を考え、x についての多項式（例えば f(x) = x + 1）の素因数 q を考えると矛盾が生じる（だから最初の仮定は否定される）…というようなタイプの証明。参考文献:
Keith Conrad: Euclidean Proofs of Dirichlet’s Theorem
https://kconrad.math.uconn.edu/blurbs/gradnumthy/dirichleteuclid.pdf

【2】　さいわい「簡単に証明できるケース」だけでも無限のバリエーションがあり、結構面白い。

例えば、任意の m について「mk+1型」素数が際限なく存在することは、比較的簡単に証明できる。特に m が素数べき p^s の場合の「p^sk+1型」については、Sierpiński の「フラクタル的」（？）議論で、あっさり一網打尽にできる。p = 3 の場合を詳細に検討してみたが、証明に必要なのは、フェルマーの小定理、初歩的な位数の性質、a^p − 1 についての簡単な恒等式だけだった。

【3】　p = 5 として、その道筋を振り返ってみる（つまり「5k+1型」「25k+1型」「125k+1型」…の素数が、それぞれ無限にあることを証明する）。

B = 5^s, C = 5^s−1, a = 2^C と置く。《ア》《イ》に当たる式は:
　　《あ》　a⁵ = (2^C)⁵ = 2^B
　　《い》　a⁵ − 1 = (a − 1)(a⁴ + a³ + a² + a + 1)

〔注〕　恒等式《い》については「げんしこん（その4）」の式「ア」参照。

s の値を選べば C の値、a の値が定まり、《い》の因子
　　《う》　N = a⁴ + a³ + a² + a + 1
の値も定まる。N の素因数を一つ選んで q とする（N は奇数なので q は奇素数）。a⁵ − 1 は q で割り切れるので:
　　《え》　a⁵ − 1 ≡ 0　つまり　a⁵ ≡ 1 (mod q)　《あ》を使うと
　　《お》　2^B ≡ 1 (mod q)

mod q での2の位数は、《お》によれば B の約数だが、下記の根拠から 2^C ≢ 1 なので、C の約数ではない。つまり mod q での2の位数は B。位数 B は q − 1 の約数なので:
　　q − 1 = Bk　（k はとある整数）　つまり　q = Bk + 1
これが証明したいことだった。

〔例〕　s = 2, B = 5² = 25, C = 5²⁻¹ = 5, a = 2^C = 32 のとき、a⁴ + a³ + a² + a + 1 = 1082401 = 601 × 1801 と素因数分解される。どちらの素因数も5²k+1型（つまり25k+1型）で、それは5k+1型でもある。

【4】　2^C つまり a が ≢ 1 (mod q) である根拠。矛盾を導くため a ≡ 1 (mod q) と仮定すると、《う》について
　　N = a⁴ + a³ + a² + a + 1 ≡ 1 + 1 + 1 + 1 + 1 ≡ 5 (mod q)
となるが、N は q の倍数なので:
　　N = a⁴ + a³ + a² + a + 1 ≡ 0 (mod q)

上の2個の合同式から 5 ≡ 0 (mod q)。それが成り立つのは q = 5 の場合のみ（q は素数なので q = 1 という選択肢はない）。そのとき《お》は
　　2^B ≡ 1 (mod 5)
となるが、これは
　　2^B ≡ 2 (mod 5)
という事実（理由は下記）と矛盾する。

理由: フェルマーの小定理から 2⁴ ≡ 1 (mod 5)、両辺を 2 倍すると 2⁵ ≡ 2 (mod 5)。この合同式を再帰的に使うと、
　　(2⁵)⁵ ≡ 2⁵ ≡ 2　　［なぜなら (2⁵) ≡ 2］
　　((2⁵)⁵)⁵ ≡ 2⁵ ≡ 2
　　(((2⁵)⁵)⁵)⁵ ≡ 2⁵ ≡ 2
…などとなり、要するに、
　　2⁵, 2⁵², 2⁵³, 2⁵⁴, …
は、どれも ≡ 2 (mod 5)。
　　2^B = 2^5s
もこの形なので ≡ 2 となる。

〔例〕　(2⁵)⁵ = 2²⁵ = 33554432 は「2 の 5² 乗」に当たり、5 で割ると 2 余る。別の角度から言うと、「5 で割って 2 余る数」の 5 乗は、再び「5 で割って 2 余る」。実際:
　　「5 で割って 2 余る数」 = 「5のとある倍数（それを x とする）プラス2」 = x + 2
　　(x + 2)⁵ = x⁵ + 5x⁴⋅2 + 10x³⋅2² + 10x²⋅2³ + 5x⋅2⁴ + 2⁵
この右辺で、最後の項以外は全部 x の倍数なので、5 で割り切れる。5 で割ったときの余りの発生源は、最後の項 2⁵ = 32 だけだが、32 を 5 で割ればもちろん 2 余る。

【5】　Dirichlet の定理の深い意味（そして「パラドックス」）は、5k+1型・5k+2型・5k+3型・5k+4型の各素数が、どれも同じ「密度」で存在する…ということ。

「パラドックス」というのは「素数レースのイカサマ」、つまり Chebyshev’s bias の存在。「バニラ素数 vs. チョコレート素数」や「ミント素数 vs. ワッフル素数」から類推すると、5k+1型・5k+4型素数は個数が少なく、5k+2型・5k+3型素数は個数が多いかのように感じられる…と予想される（5 を法として 1 と 4 は平方剰余、2 と 3 は非剰余なので）。果たしてどうだろうか？

100以下の素数25個のうち、5の倍数「5」を除いた24個を分類してみよう。

5k+1型（5個）　 「剰余チーム」所属

11, 31, 41, 61, 71

5k+4型（5個）　 「剰余チーム」所属

19, 29, 59, 79, 89

5k+2型（7個）　 「非剰余チーム」所属

2, 7, 17, 37, 47, 67, 97

5k+3型（7個）　 「非剰余チーム」所属

3, 13, 23, 43, 53, 73, 83

やっぱり…。平方剰余チームが微妙に不利になるように細工されているっ！

日常的な言葉で言うと: 最下位桁が 1 or 9 の素数より、最下位桁が 3 or 7 の素数の方が多いように感じられる。

「5k+1型」は、「10k+1型」と「10k+6型」に分けられるが、「10k+6型」は 6 以上の偶数なので、素数にならない。だから「5k+1型」素数とは、実質「10k+1型」素数（末尾が1）。

同様に「5k+4型」は、「10k+4型」と「10k+9型」に分けられるが、「10k+4型」は素数にならない。だから実質「10k+9型」素数（末尾が9）。

一方「5k+2型」は、「10k+2型」と「10k+7型」に分けられ、ほとんどは「10k+7型」（末尾が7）だが、「10k+2型」（末尾が2）にも、一つだけ素数がある（k = 0 のときの「2」）。

最後に「5k+3型」は、「10k+3型」と「10k+8型」に分けられるが、「10k+8型」は素数にならない。実質「10k+3型」素数（末尾が3）。

【6】　「たまたま100以下では、誤差があるだけかも？」という見方もあるので、サンプルサイズを少し増やしてみると…

素数レース mod 5
範囲　剰余チーム vs. 非剰余チーム
100以下　10 vs. 14 :: bias=4
1000以下　78 vs. 89 :: bias=11
1万以下　609 vs. 619 :: bias=10
10万以下　4777 vs. 4814 :: bias=37
100万以下　39210 vs. 39287 :: bias=77
1000万以下　332136 vs. 332442 :: bias=306

微妙だよね…。「1万以下で10個とか、100万以下で77個とか、そのくらい誤差の範囲でしょ。深い意味はないよ」と思おうとすれば思えてしまう。「10¹⁰⁰⁰⁰ より先では偏りがなくなるかも？」と言われれば、確かにそうかもしれない。けれど mod 3 でも mod 4 でも剰余チームが劣勢なので、やはり何やら非常に深い問題が絡んでるようだ。

チェスや将棋で起きたことが数論でも起きるとすると、やがて「人間の数学者には思い付かないような証明の手筋」を発見するAIが、出現するのかもしれない。リーマン予想を解決するのは、人間ではないのかもしれない。

2022-07-11　乗乗の奇妙な冒険　「2 の乗乗は 2 と合同」

p^s　←　素数 p の s 乗

2^ps　←　2 の「p の s 乗」乗（略して「乗乗」）

例　→　p = 3, s = 4 のとき 2^ps = 2³⁴
= 2^3×3×3×3 = 2⁸¹ = 2𥝱4178垓5163京9229兆2583億4941万2352

京（けい）　＝　1兆の1万倍

垓（がい）　＝　1兆の1億倍

𥝱（じょ）　＝　1兆の1兆倍

【1】　2ⁿ を n で割ると 2 余ることがある:

• n = 3　⇒　2³ = 8 を 3 で割ると 2 余る
• n = 4　⇒　2⁴ = 16 を 4 で割ると 0 余る
• n = 5　⇒　2⁵ = 32 を 5 で割ると 2 余る
• n = 6　⇒　2⁶ = 64 を 6 で割ると 4 余る
• n = 7　⇒　2⁷ = 128 を 7 で割ると 2 余る
• n = 8　⇒　2⁸ = 256 を 8 で割ると 0 余る
• n = 9　⇒　2⁹ = 512 を 9 で割ると 8 余る
• n = 10　⇒　2¹⁰ = 1024 を 10 で割ると 4 余る
• n = 11　⇒　2¹¹ = 2048 を 11 で割ると 2 余る
• ……

n が奇数の素数なら、必ずこの現象が起きる。なぜ？

n が 3 以上の素数なら、フェルマーの小定理から:
　　2ⁿ⁻¹ ≡ 1 (mod n)
その両辺を 2 倍すると:
　　《サ》　2ⁿ ≡ 2 (mod n)

2ⁿ⁻¹ の 2 倍は 2ⁿ。「n−1 個の 2 の積」にさらに 2 を掛ければ、「n 個の 2 の積」。合同記号（≡）の意味？

2 も素数だが、n = 2 の場合、2² = 4 を 2 で割っても 2 余らない。けれど、その場合にも《サ》は成り立つ。実際に《サ》に n = 2 を入れてみると、正しい式になる:
　　2² ≡ 2 (mod 2)
　　つまり　4 ≡ 2 (mod 2)
　　意味「左辺の 4 と右辺の 2 の差は、mod の後ろの数 2 で割り切れる」
　　別の解釈「左辺の 4 も右辺の 2 も、mod の後ろの数 2 で割った余りは同じ（どちらの余りも 0）」

mod 2 というのは、要するに「偶数と奇数の区別による分類」。4 ≡ 2 (mod 2) は「両辺とも偶数」という当たり前のことにすぎない。

【2】　以上をまとめると: p が素数（2 でも 3 以上でもいい）なら、次が成り立つ。
　　《シ》　2^p ≡ 2 (mod p)

今、《シ》の両辺を p 乗すると:
　　(2^p)^p ≡ 2^p (mod p)　つまり
　　《ス》　2^pp ≡ 2^p (mod p)
ところが《シ》によれば、《ス》の右辺 2^p は ≡ 2 なのだから、《ス》を次のように簡単化できる:
　　《セ》　2^pp ≡ 2 (mod p)

《セ》の両辺を再び p 乗すると:
　　(2^pp)^p ≡ 2^p (mod p)
　　つまり　2^ppp ≡ 2^p (mod p)
再び《シ》によって、上の式の右辺は ≡ 2 なのだから、こうなる:
　　《ソ》　2^ppp ≡ 2 (mod p)

《ソ》の両辺を再び p 乗すると…。この議論は何度でも繰り返すことができ、次が成り立つ:
　　2 ≡ 2^p ≡ 2^pp ≡ 2^ppp ≡ 2^pppp ≡ … (mod 2)　つまり
　　2 ≡ 2^p1 ≡ 2^p2 ≡ 2^p3 ≡ 2^p4 ≡ … (mod p)

要するに:

2 の「素数の自然数乗」乗　任意の素数 p と任意の自然数 s について、「2 の p^s 乗」は、p を法として 2 と合同:
　　2^ps ≡ 2 (mod p)　　「2 の乗乗は 2 と合同」^*1
すっきりさせるため p^s を B とすると:
　　《タ》　2^B ≡ 2 (mod p)

*1　「素数の自然数乗」乗を略して、「乗」乗と呼ぶことにする。簡潔に、乗乗と表記する。

〔例〕　p = 3, s = 2, B = 3² = 9 のとき:
　　2^B = 2⁹ = 512 ≡ 2 (mod 3)
p = 3, s = 3, B = 3³ = 27 のとき:
　　2^B = 2²⁷ = 134217728 ≡ 2 (mod 3)

【3】　ポーランドの数学者 Sierpiński（シェルピンィスキー）は、次のことを証明している^*2。
　　定理　「p^sk+1型」の素数は無限に存在する（k は正の整数）

*2　Sierpiński: Elementary Theory of Numbers, Chap. VI §5, Theorem 11
http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4206.pdf
例えば p = 7, s = 2 とすると「49k+1型」の素数は無限に存在する。

p = 3 の場合について、既にこの定理を詳しく検討した。p = 5 の場合についても、ざっと調べた。今回は、一般の素数 p について、定理を証明する。

上記《タ》――「2 の乗乗は 2 と合同」――が、この定理の証明の一つの鍵。

【4】　B = p^s, C = p^s−1, a = 2^C と置く。ここで p は任意の素数、s は 1 以上の任意の整数。

p = 3 の場合の《ア》、p = 5 の場合の《あ》に当たる一般式は:
　　《チ》　a^p = (2^C)^p = 2^B

〔解説〕　1個目の等号は、単に定義 a = 2^C によって a を書き換えただけ。2個目の等号の意味は:
　　(2^C)^p = (2^ps−1)^p = 2^{(ps−1 × p)} = 2^(ps) = 2^B
例えば p = 3, s = 3, B = 3³ = 27; s−1 = 2, C = 3² = 9 のとき:
　　(2⁹)³ = (2³²)³ = 2^(32 × 3) = 2⁽³³⁾ = 2²⁷

一方、p = 3 の場合の《イ》、p = 5 の場合の《い》に当たる一般式は^*3:
　　《ツ》　a^p − 1 = (a − 1)(a^p−1 + a^p−2 + … + a² + a + 1)
《ツ》右辺の第2因子を N と置く:
　　《テ》　N = a^p−1 + a^p−2 + … + a² + a + 1
　　《ト》　a^p − 1 = (a − 1)N　　← 《ツ》に《テ》を代入した

*3　式《ツ》が成り立つ理由については、下の【補足説明1】参照。《ツ》自体は p が素数でなくても成り立つが、ここで右辺第2因子が「素数個の項の和」であることが、後々意味を持つ。

N は何らかの自然数。その N の素因数の一つを q とする（N 自身が素数なら q = N とする。N が合成数なら、N の素因数を任意に一つ選んで q とする）。q は 3 以上の（奇数の）素数^*4。

*4　p は素数なので、もちろん 2 以上。従って B は 2¹ = 2 以上、C は 2⁰ = 1 以上、a は 2¹ = 2 以上。N が取り得る最小値は、p = 2 の場合の《ツ》《テ》…
　　a² − 1 = (a − 1)(a + 1)
　　N = a + 1
…に a = 2 を入れた『3』。さて、a は「2 の C 乗」なので偶数。従って《テ》右辺各項は、最後の 1 を除き偶数、和 N は奇数。つまり N は『3』以上の奇数、その素因数 q は 3 以上の奇素数。

N は q の倍数だが、《ト》から分かるように、a^p − 1 は、N（それは q の倍数である）のそのまた倍数なので、もちろん q の倍数であり、q で割り切れる:
　　a^p − 1 ≡ 0　つまり　a^p ≡ 1 (mod q)
この最後の式の左辺に《チ》を代入すると:
　　《ナ》　2^B ≡ 1 (mod q)

《ナ》は、性質《タ》――「2 の乗乗は 2 と合同」――に反しているようにも思える。でもよく見ると、《タ》は「2 の p^s 乗を法 p で考えた場合」であり、《ナ》は「別の法 q で考えた場合」。mod が違うので、《タ》とは直接関係ない。ただし万一 q = p になるなら、そのときは《ナ》は《タ》と矛盾する（言い換えると、論理的に q = p にはなり得ない）。ところで、《ナ》の左辺は偶数、右辺は奇数、mod 2 では両辺は不合同: q が 3 以上の奇素数であることが再確認される。

mod q での 2 の位数^*5を e とすると、《ナ》によって e は B の約数のどれか。

*5　「位数」の意味や、それが何々の約数になる…といった性質について、下の【補足説明2】参照。

B は素数べき p^s なので、その約数は、
　　1, p, p², p³, …, p^s−1 (=C), p^s (=B)
しかない。このうち、C 以下のものはどれも C の約数だが、「mod q での 2 の位数は C の約数じゃない」ことを証明できるので（後回し: 【6】参照）、消去法によって e = B となる。mod q での位数は q − 1 の約数なので、e = B は q − 1 の約数。言い換えれば q − 1 は B の倍数。こう書ける:
　　q − 1 = Bk　（k はとある整数）
　　つまり　q = Bk + 1 = p^sk + 1

これで、素数 q は「p^sk+1型」であることが分かった！

【5】　といっても「p^sk+1型」の素数 q が1個構成されただけで、「無限個あること」の証明には程遠いようにも思える。でも上記において、正の整数 s の値は任意だった。そこで s を自由に設定すると:
　　s = 1 のとき　p¹k+1型の素数 q₁ が存在
　　s = 2 のとき　p²k+1型の素数 q₂ が存在
　　s = 3 のとき　p³k+1型の素数 q₃ が存在
　　……
という無限の系列が得られる。しかも「p²k+1型」＝「ppk+1型」の素数は、「pk+1型」でもある（pk をあらためて k と置けばいい）。

〔例〕　「3²k+1型」つまり「9k+1型」の素数（19, 37 など）は、「3k+1型」の素数でもある。

同様に、「p³k+1型」＝「pppk+1型」の素数は、pk をあらためて k と置けば「p²k+1型」でもあり、あるいは ppk をあらためて k と置けば「pk+1型」でもある。以下同様に進めると…。「より大きい s の型は、自動的により小さい s の型にもなっていること」「ある整数より大きい s の選択肢は無限にあり、そのどれを選んでも構わないこと」…この二つの原理から、s の初期値が何であれ、その型の素数は無限に存在する！

Sierpiński のこの論法は、ちょっとゾクッとする。

このロジックを支える柱として、q₁, q₂, q₃, … はどれも互いに異なる素数。

無限に続く列があるとしても、もし有限個の同じ素数が無限ループして現れるのなら、その列には、有限種類の素数しか含まれていない。次のパラグラフでは、この嫌な可能性を否定する。

もし仮に同じ素数 q が反復出現するなら、その同一素数 q を法とすると、もちろん 2 の位数は一定。言い換えると、法 q と法 q′ とで 2 の位数が違うのなら、q = q′ ということはあり得ない。q₁, q₂, q₃, … を上記のように（s をだんだん増やして）構成した場合、構成法から明らかなように、それぞれの q を法として 2 の位数は B = p^s。s が増えると位数 p^s も増えるので、各 q の値は異なり、重複はない。

【6】　最後に、後回しにした「mod q での 2 の位数は C の約数じゃない」ことの証明。それには、
　　《ニ》　2^C ≢ 1　つまり a ≢ 1 (mod q)
を示せば十分。

〔解説〕　2 の位数 e とは 2^□ ≡ 1 を満たす最小正整数なので、《ニ》の状況ではもちろん e ≠ C。のみならず e が C の約数だとして ef = C とすると（f は整数）、位数の定義上 2^e ≡ 1 だから 2^C = 2^ef = (2^e)^f ≡ 1^f ≡ 1 となって、《ニ》と両立できない。だから《ニ》が成立するなら、e は C の約数のどれでもない。

《ニ》を検証するため、あえてそれを否定して a ≡ 1 (mod q) と仮定し、何が起きるか考えてみよう。《テ》の右辺は（p−1 種類の a のべきと 1 の和なので）この仮定上では、次のように「p 個の 1 の和」と合同:
　　N = a^p−1 + a^p−2 + … + a² + a + 1 に a ≡ 1 を代入すると
　　N ≡ 1^p−1 + 1^p−2 + … + 1² + 1 + 1 (mod q)　つまり
　　《ヌ》　N ≡ p (mod q)
一方、q の意味を考えると、もちろん N は q で割り切れるから:
　　《ネ》　N ≡ 0 (mod q)
《ヌ》と《ネ》から p ≡ 0 (mod q)。つまり、p は q で割り切れる。でも p は素数なので、1 と p 自身でしか割り切れない。だから q = 1 または q = p だが、q は素数なので 1 ではない。従って q = p。これを《ナ》に代入すると 2^B ≡ 1 (mod p) となるが、これは《タ》の 2^B ≡ 2 (mod p) ――「2 の乗乗は 2 と合同」――と矛盾する。

q は 3 以上の奇素数なので（【4】参照）、p = 2 の場合、q = p の時点で既に矛盾。では、例えば p = 3 なら q = p = 3 が起こり得るか。《ナ》の下の注釈にあるように、答えはノー。

a ≡ 1 (mod q) と仮定すると矛盾。だからこの仮定は間違いで《ニ》が正しい。証明が完成した。□

【7】　すなわち、一挙に証明されたのである――
　　2k+1型・4k+1型・8k+1型・16k+1型…（2^sk+1型）
　　3k+1型・9k+1型・27k+1型・81k+1型…（3^sk+1型）
　　5k+1型・25k+1型・125k+1型・625k+1型…（5^sk+1型）
　　7k+1型・49k+1型・343k+1型・2401k+1型…（7^sk+1型）
　　11k+1型・121k+1型・1331k+1型…（11^sk+1型）
　　……
　　（p^sk+1型）
　　………
のどの型の素数も、それぞれ無限にあることが！　事実としては Dirichlet の定理の氷山の一角にすぎないとしても、上記の定理は、証明がシンプルな割にターゲットが広い（例えば、4k+1型だけを個別にゴチャゴチャ証明することと比べると…）。

こんな素敵な証明が、どうして歴史に埋もれかけているのだろう？　「一般的には、結局 Dirichlet の定理が必要」「初等的な範囲でも、mk+1型の素数については、円分多項式を使う定石がある」ということから、p^sk+1型という中途半端に特殊なケースを追究しても仕方ない…ということだろう。事実、上記の N の式は、円分多項式の最も簡単な場合を選択しているにすぎない。

とはいうものの、単純なロジックを鮮やかに組み合わせて、アッと驚くような論法で事実が導かれると、心に染みるものがある。

「p¹k+1型」の証明の中に、その証明自体のミニチュア・コピーのように「p²k+1型」の証明が埋め込まれていて、そのまた中に「p³k+1型」の証明が…という「自己相似」の無限連鎖によって、素数の無限性が確立される。ある種の fractal 構造。偶然なのか必然なのか、さすがは Sierpiński gasket のシェルピンィスキー…？

当時のポーランドならではの「良い意味での奇妙さ」なのかも…。大胆で革新的な「数論の本流」はドイツやフランスのような強国で「支配」されていたので、ポーランドでは、非主流的だった部分が繊細に考察され、そこからかえって新境地が開けたとも解釈できる。

言うまでもなく Sierpiński は卓越した頭脳の持ち主だったが、ロシア支配時代、反抗心からロシア語の授業では「わざと」悪い点を取ったという（笑）。そして自著も、フランス語でも英語でもなく、ましてやロシア語やドイツ語ではなく、ほとんどポーランド語で記した。強大なロシアと強大なドイツに挟またポーランドでは、愉快ならざる事態が多かったことは想像に難くない。ロシアの数学者・ドイツの数学者には何の罪もないのだが、腐敗する権力のせいで、善良な研究者や一般人が翻弄されるのは、昔も今も変わらないようである…

下に続く。

2022-07-16　乗乗の奇妙な冒険　補足説明

【補足説明1】　a^p − 1 = (a − 1)(a^p−1 + a^p−2 + … + a² + a + 1)

この式は、（素数に限らず）任意の正の整数 p に対して成り立つ:
　　p = 1 なら a¹ − 1 = (a − 1)(1)　←　当たり前
　　p = 2 なら a² − 1 = (a − 1)(a + 1)
　　p = 3 なら a³ − 1 = (a − 1)(a² + a + 1)
　　………

どれも見慣れた式かもしれないが、右辺を展開すれば、成り立つことを直接確かめられる。右辺の2番目の丸かっこの中の和は、
　　p = 5 なら a⁵ − 1 = (a − 1)(a⁴ + a³ + a² + a + 1)
のように、a の p−1 乗から始まって2乗・1乗まで下がって、最後に 1 を付ける（1 は 0 乗とも解釈できる）。

これを証明するため、任意の p（素数とは限らない）が与えられたとして
　　N = a^p−1 + a^p−2 + … + a² + a + 1
と置く。証明したい式は:
　　a^p − 1 = (a − 1)N　つまりこう書ける:
　　《ハ》　a^p − 1 = aN − N　←　証明したい式

《ハ》の右辺第1項 aN は、N の定義から次に等しい:
　　aN = a(a^p−1 + a^p−2 + … + a² + a + 1)
　　《ヒ》　aN = a^p + a^p−1 + … + a³ + ² + a
上の計算は、次の例からも容易に理解できるだろう。
　　p = 5 の例　a(a⁴ + a³ + a² + a + 1)
　　= a⁵ + a⁴ + a³ + a² + a + 1

一方、《ハ》の右辺第2項 −N は、単に N の符号をマイナスにしただけ:
　　《フ》　−N = (−1)N = −a^p−1 − a^p−2 − … − a² − a − 1

《ハ》の右辺は《ヒ》と《フ》の和だが、a の p−1 乗から a の 1 乗までの各項は、《ヒ》のプラス版と《フ》のマイナス版を足し合わせると、どれも 0 になって消えてしまう。消えずに残るのは《ヒ》の最初の項と《フ》の最後の項だけ。つまり:
　　aN − N = a^p − 1
証明したかった式《ハ》が得られた。

この公式は、もっと一般的な xⁿ − yⁿ の展開式で x = p, y = 1 と置いたものに当たる。参考までに、帰納法を使った正式な証明。

【補足説明2】　位数については、別のところにいろいろ書かれているが、ここでは基本性質しか使わない。q を3以上の素数とする。q を法とする 2 の位数とは:
　　《ヘ》　2^□ ≡ 1 (mod q)
の □ に当てはまる最小の正の整数。

〔例〕　q = 7 とすると:
　　2¹ = 2 ≢ 1 (mod 7) なので 1 は □ に当てはまらない。
　　2² = 4 ≢ 1 (mod 7) なので 2 も □ に当てはまらない。
　　2³ = 8 ≡ 1 (mod 7) なので 3 は □ に当てはまる！
　　2⁴ = 16 ≡ 2 ≢ 1 (mod 7) なので 4 は □ に当てはまらない。
　　2⁵ = 32 ≡ 4 ≢ 1 (mod 7) なので 5 も □ に当てはまらない。
　　2⁶ = 64 ≡ 1 (mod 7) なので 6 も □ に当てはまる！

この例では、3 と 6 が □ に当てはまるが、そのうち最小の 3 が位数となる。フェルマーの小定理から
　　2^q−1 ≡ 1 (mod q)
なので、q−1 は必ず □ に当てはまる（上の例では 7−1 = 6）。もし q−1 より小さい正の整数の中に □ に当てはまる数がなければ、q−1 が位数ということになる。

位数の性質1　《ヘ》の □ に当てはまる最小の正の整数（つまり位数）を e とする。《ヘ》の □ に当てはまる任意の正の整数（必ずしも最小でなくてもいい）を f とする。このとき、f は e の倍数。言い換えると、e は f の約数。

〔具体例〕　上記 q = 7 のケースでは e = 3。そして f = 6 とすれば…

理由。例えば e = 3 が位数だとして、その倍数ではない f = 5 も、《ヘ》の □ に当てはまるとすると、矛盾が起きる。というのも、その場合、2³ ≡ 1 と 2⁵ ≡ 1 (mod q) が両方成り立つはずだが、
　　前者は 2 × 2 × 2 ≡ 1 を意味する。
　　後者は (2 × 2 × 2) × 2 × 2 ≡ 1 を意味する。
　　下の式の丸かっこ内に上の式から代入すると
　　(1) × 2 × 2 ≡ 1　つまり　2² ≡ 1 (mod q)
この最後の合同式によれば、2 も《ヘ》の □ に当てはまる。ところが、位数 e = 3 の定義は、□ に当てはまる最小の正の整数なのだから、それよりもっと小さい正の整数 2 が □ に当てはまるというのでは、つじつまが合わない。だから、e の倍数ではない f が □ に当てはまる…ということは不合理であり、あり得ない。

一般に、f が e の倍数ではない場合、f を e で割ると割り切れずに 1 以上の余り r が出る。f を e で割ると商 m、余り r だとしよう。これは f = em + r を意味する（例えば f = 7, e = 3 なら m = 2, r = 1）。このとき:
　　もしも 2^f ≡ 1 なら
　　2^f = 2^em+r = (2^em)(2^r) = [(2^e)^m]2^r　要するに
　　《ホ》　2^f = [(2^e)^m]2^r
e が位数という仮定から、最後の式の丸かっこ内は、次のように ≡ 1 になる:
　　(2^e) ≡ 1　従って　[(2^e)^m] ≡ [(1)^m] ≡ 1
これを《ホ》に代入すると:
　　2^f = [1]2^r ≡ 2^r
仮定によれば、この最後の式の左端の 2^f は ≡ 1 なので、それと合同な右端の 2^r も ≡ 1。だが r は e で割った余りなので e より小さい。位数 e より小さい正の整数 r が《ヘ》の □ に当てはまることになってしまう。おいおい、それじゃぁ話が矛盾してるだろ！　話の前提として □ に当てはまる最小の正の整数は e なんだからよ…。っつーわけで「e の倍数じゃない f が □ に当てはまる」なんつーことは、論理的にあり得ねぇな。

位数の性質2　フェルマーの小定理によって、q − 1 は、必ず《ヘ》の □ に当てはまる。従って、上記「位数の性質1」から、q − 1 は 2 の位数 e の倍数。言い換えれば、e は q − 1 の約数。ここで q は、計算の枠組みとなる mod q の値 q を指す。

q は 3 以上の奇素数なので 2 と互いに素。従ってフェルマーの小定理が当てはまり、mod q での 2 の位数を考えることもできる。一般に q と互いに素な任意の自然数 b について（q は素数なので、これは「b は q の倍数でなければ」というのと同じ意味）、全く同様のことが成り立つ: mod q での b の位数とは、b^□ ≡ 1 (mod q) に当てはまる最小の正整数 e だが、この □ に当てはまる任意の数 f は e の倍数。特に q − 1 は e の倍数。

下に続く。

2022-07-15　乗乗の奇妙な冒険（その2）　数値例

前回の続き。具体的な数値例。

【8】　シェルピンィスキーの論法を要約すると、下記の整数 N の素因数 q は、p^sk+1型の素数:
　　N = a^p−1 + a^p−2 + … + a² + a + 1
　　ここで C = p^s−1, a = 2^C　←　要するに a = 2^p^(s−1)
そのことから、p^sk+1型の素数が無限にあると結論されるのだった。

p = 2 のときの N = a + 1 の例。

s = 1, a = 2, N = 3
s = 2, a = 4, N = 5
s = 3, a = 16, N = 17
s = 4, a = 256, N = 257
s = 5, a = 65536, N = 65537
s = 6, a = 4294967296, N = 4294967297

これらはフェルマー数に他ならない。そして a = 2¹, 2², 2⁴, 2⁸, 2¹⁶, … に 1 を足したものが N なのだから、もし N が素数なら（フェルマー素数）、N は（2^sk+1型であるのはもちろん）2^Ck+1型素数になる。

s = 6 以降のフェルマー数で、素数になるものは知られていない。s = 6 のケースは
　　F₅ = 4294967297 = 641 × 6700417
と分解される。それでも、これらの素因数 q = 641, q = 6700417 が「2⁶k+1型」つまり「64k+1型」素数になる:
　　641 = 64 × 10 + 1
　　6700417 = 64 × 104694 + 1

〔注〕　フェルマー数は F_n = 2^2^n だが、ここでは a = 2^2^(s−1) を考えているので、両者の関係は n = s−1: つまり F の添え字 n は s より 1 小さい。

さらにシェルピンィスキーの証明によれば、mod 641 と mod 6700417 において、2 の位数が 2⁶ = 64 になるはず:
　　2⁶⁴ ≡ 1　しかし　2³² ≡ −1 (mod 641)
　　2⁶⁴ ≡ 1　しかし　2³² ≡ −1 (mod 6700417)
確かにそうなっている！

〔解説〕　2⁶⁴ ≡ 1 は既に分かっている。もし位数が 2⁶ = 64 より小さいなら、そのとき位数は 64 の約数なので、S = {64, 32, 16, 8, 4, 2, 1} のどれか。仮に位数 e がそのうち 32 以下のどれかだとすると、e の具体的値がどれであるにしても（例えば e = 8 だとしても 16 だとしても）、32 はその e の倍数: だから 2³² ≡ 1 になるはず。実際には 2³² ≡ 1 は不成立なので、e は 32 の約数のどれでもない。【補足説明2】参照。

s = 7 の場合、N = 18446744073709551617 = 274177 × 67280421310721。つまり 2 の 64 乗プラス 1 は、274177 で割り切れる。この 274177 は「128k+1型」素数。積 N も ≡ 1 (mod 128) なので、余因子もこの形でなければならない。そして 2 の位数に関連して:
　　2¹²⁸ ≡ 1　しかし　2⁶⁴ ≡ −1 (mod 274177)
　　2¹²⁸ ≡ 1　しかし　2⁶⁴ ≡ −1 (mod 67280421310721)

〔参考〕　この定理の一般論としては「2^sk+1型」素数が構成されるが、p = 2, s ≥ 3 の場合、さらに強く「2^s+1k+1型」素数が得られる。例えば 641 は「128k+1型」（それは「64k+1」型の特別な場合である）、274177 は「256k+1型」、等々。

p = 2 で s が 3 以上なら、素数 q は少なくとも「2³k+1型」つまり「8k+1型」。ところが、別の理論（平方剰余の第2補充法則）によると、このように q が8の倍数プラス1のときには、x² ≡ 2 (mod q) に解がある。2 の位数が 2^s であることは証明済みなので、この 2 ≡ x² は 2^s 乗して初めて ≡ 1 になり、従って解 x は 2^s+1 乗して初めて ≡ 1 になる。x の位数 2^s+1 もまた q − 1 の約数なので、q − 1 = 2^s+1k と書ける（k はとある整数）: つまり q は「2^s+1k+1型」。

【9】　p = 3 の場合。a = 2^3^(s−1) に対して、N = a² + a + 1 の素因数が「3^sk+1型」になり、それを法とした 2 の位数は 3^s に等しいはず。

s = 1, a = 2, N = 7
s = 2, a = 8, N = 73
s = 3, a = 512, N = 262657
s = 4, a = 134217728, N = 18014398643699713

初めの3個の N は、それぞれ「3k+1型」「9k+1型」「27k+1型」素数。4番目の N は
　　18014398643699713 = 2593 × 71119 × 97685839
と分解され、各因子は「81k+1型」素数。2 の位数について:
　　2⁸¹ ≡ 1　しかし　2²⁷ ≡ 1455 (mod 2593)
　　2⁸¹ ≡ 1　しかし　2²⁷ ≡ 16175 (mod 71119)
　　2⁸¹ ≡ 1　しかし　2²⁷ ≡ 36531889 (mod 97685839)

s = 5 のときの N は巨大だが、小さい素因数 q = 487 を持つ。これは「3⁵k+1型」つまり「243k+1型」素数で、それを法とする 2 の位数は 243。

3k+1型の整数は、6k+1型と6k+4型に分けられるが、後者は明らかに素数ではない。つまり「3k+1型」素数というのは、実際には「6k+1型」。同様に「9k+1型」も実際には「18k+1型」だし、例えば「5k+1型」は実際には「10k+1型」。等々。

【10】　p = 5 のとき、a = 2^5^(s−1) に対して、N = a⁴ + a³ + a² + a + 1 の素因数が「5^sk+1型」になり、それを法とした 2 の位数は 5^s に等しいはず。

s = 1 のとき a = 2, N = 31 は「5k+1型」（実際には「10k+1型」）の素数。

s = 2 のとき a = 32, N = 1082401 = 601 × 1801 と分解される。これらの因子は「25k+1型」（実際には「50k+1型」）の素数で、それを法とした 2 の位数は 25 に等しい:
　　2²⁵ ≡ 1　しかし　2⁵ ≡ 32 (mod 601)
　　2²⁵ ≡ 1　しかし　2⁵ ≡ 32 (mod 1801)

s = 3 のときの N は大きいが、「125k+1型」の素因数 q = 269089806001 が得られる。この q を法として 2 の位数は125。

【11】　p = 7 のとき、a = 2^7^(s−1) に対して、N = a⁶ + a⁵ + … + a² + a + 1 の素因数が「7^sk+1型」になり、それを法とした 2 の位数は 7^s に等しい。

s = 1 のときの N = 127 と s = 2 のときの N = 4432676798593 は、それぞれ「7k+1型」「49k+1型」の素数。

s = 3 のときの N は巨大だが、「343k+1型」の素因数 q = 6073159 を持つ。この q を法として、2 の位数は343。

【12】　p = 11 のとき、a = 2^11^(s−1) に対して、N = a¹⁰ + a⁹ + … + a² + a + 1 の素因数が「11^sk+1型」になり、それを法とした 2 の位数は 11^s に等しい。

s = 1 のときの N = 2047 は 23 × 89 と分解される。どちらの因子も「11k+1型」の素数。

s = 2 のときの N は巨大だが、「121k+1型」の小さな素因数 q = 727 を持つ。それを法として 2 の位数は 121。

以上によって、mk+1型素数が無限に存在することが、m = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 に対してそれぞれ証明され、数値的にも確認された！

しかしこの方法では、m = 12 の場合――つまり「12k+1型」の素数が無限に存在すること――を証明できない。12 は p^s の形（またはその2倍）ではないから…。

同じ理由から、この証明法は m = 15, 20, 21, 24, 28, 30 には通用しない（32 以下のそれ以外の m には対応可能）。

m が素数 p なら（あるいは一般に素数のべき p^s またはその2倍 2p^s なら）、mk+1型素数が無限にあることについて、前回の方法で証明できる。理論的にはそれでいいのだが、この方法でmk+1型素数を生成すると、一般に巨大な数になってしまう（m がおよそ300以下なら実際に計算可能）。

mk+1型素数の無限性についての一般論は、少し難しい。円分多項式を直接使わないまでも、メビウス関数やメビウス反転が使われ、そのためには「入力 n が与えられたとき、n の各約数 d について f(d) を計算して、それらの総和を出力とする」という考え方が必要になる。面倒といえば面倒だけど、やりがいがある。

〔参考〕　円分多項式もメビウスも使わない初等的な証明（分かりやすいかどうかはともかく）が下記に掲載されている。
Sedrakian & Steinig: A particular case of Dirichlet’s theorem on arithmetic progressions
https://archive-ouverte.unige.ch/unige:12642

2022-07-17　春素数と秋素数　高木の逆襲？

8k+1型の素数が無限に存在することは、Sierpiński の「フラクタル論法」（？）で再帰的に証明済みだが、このメモではそれを直接証明する。

Hardy & Wright は、4k+1型の素数が無限に存在することを証明するついでに、8k+5型の素数も無限にあることを証明している。シンプルな高木の証明法でも、このひねり技を追加できる！

【1】　以下 p を 3 以上の素数とする。4k+1型素数が無限にあることの直接証明は、およそどの方法でも、平方剰余の第一補充法則…
　　x² = −1 (mod p) に解あり　⇔　p は 4k+1型
…に帰着されるようだ（フェルマーの小定理だけを使う証明（スパイシーの【3】）もあるにはあるが）。

うまくいくかどうかはともかく、その拡張として、もし次が成り立てば同様にして8k+1型素数の無限も証明できるのでは…？
　　四乗剰余の補充法則（？）　x⁴ = −1 (mod p) に解あり　⇔　p は 8k+1型
さらに調子に乗って、
　　八乗剰余の補充法則（？）　x⁸ = −1 (mod p) に解あり　⇔　p は 16k+1型
が成り立てば、16k+1型素数の無限が出るのでは…

そもそも法則（？）は本当に成り立つのか。とりあえず数値的に実験。

\\ PARI/GP
kai_sagasu(p) = { for( x=1, p-1, y=x^4;
  if( y%p==p-1, 
    printf("p=%d (8k+%d), x=%d : x^4=%d : %d=%d * %d\n",
               p,     p%8,   x,       y, y+1, p,   (y+1)/p)
  ) ); }
forprime( p=3, 50, kai_sagasu(p) )

結果

p=17 (8k+1), x=2 : x^4=16 : 17=17 * 1
p=17 (8k+1), x=8 : x^4=4096 : 4097=17 * 241
p=17 (8k+1), x=9 : x^4=6561 : 6562=17 * 386
p=17 (8k+1), x=15 : x^4=50625 : 50626=17 * 2978
p=41 (8k+1), x=3 : x^4=81 : 82=41 * 2
p=41 (8k+1), x=14 : x^4=38416 : 38417=41 * 937
p=41 (8k+1), x=27 : x^4=531441 : 531442=41 * 12962
p=41 (8k+1), x=38 : x^4=2085136 : 2085137=41 * 50857

1行目の意味: p=17 (8k+1型素数） のとき、x⁴ ≡ −1 (mod p) に解あり。x=2 は一つの解で、実際、x⁴=16 は p=17 の倍数 17 より 1 小さい。

2行目の意味: p=17 (8k+1型素数） のとき、x⁴ ≡ −1 (mod p) に解あり。x=8 は一つの解で、実際、x⁴=4096 は p=17 の倍数 4097 より 1 小さい。以下同様。

50以下の奇素数 p に関する限り、解があるのは p が8k+1型のときに限られる。逆に50以下の8k+1型素数は 17 と 41 の2個だけだから、この範囲では「法則」は成り立っている。x⁴ ≡ −1 は4次方程式なので、解が（あるなら）4個あるのは、驚くには当たらない。解が1個でも見つかったら検索を打ち切ることにして、範囲を 200 まで広げてみる。

kai_sagasu(p) = { for( x=1, p-1, y=x^4;
  if( y%p==p-1, 
    printf("p=%d (8k+%d), x=%d : x^4=%d : %d=%d * %d\n",
               p,     p%8,   x,       y, y+1, p,   (y+1)/p);
    return ) ); }
forprime( p=3, 200, kai_sagasu(p) )

結果

p=17 (8k+1), x=2 : x^4=16 : 17=17 * 1
p=41 (8k+1), x=3 : x^4=81 : 82=41 * 2
p=73 (8k+1), x=10 : x^4=10000 : 10001=73 * 137
p=89 (8k+1), x=12 : x^4=20736 : 20737=89 * 233
p=97 (8k+1), x=33 : x^4=1185921 : 1185922=97 * 12226
p=113 (8k+1), x=18 : x^4=104976 : 104977=113 * 929
p=137 (8k+1), x=10 : x^4=10000 : 10001=137 * 73
p=193 (8k+1), x=9 : x^4=6561 : 6562=193 * 34

これらの p は、200以下の全ての8k+1型素数（愛称: 春素数）で、それぞれに対して解がある。他方、8k+1型以外の p に対しては1例も「解あり」のケースが見つからない。法則は正しそうだ！

となれば、証明しなければなるまい。

【2】　四乗剰余の補充法則　奇素数 p が8k+1型の場合（そしてその場合に限って）、x⁴ ≡ −1 (mod p) は解を持つ。言い換えると、任意の整数 x について、x⁴ + 1 の素因数は、8k+1型の奇素数 p か、偶素数 2 に限られる。

〔例〕 x = 3 のとき x⁴ + 1 = 82 = 2 × 41。この 41 は8k+1型。
x = 10 のとき x⁴ + 1 = 10001 = 73 × 137。どちらの素因数も8k+1型。

〔解説〕 どうにかして x⁴ ≡ −1 (mod p) が解を持つ必要十分条件が分かったとしよう。−1 を左辺に移項した x⁴ + 1 ≡ 0 (mod p) が解を持つかどうかも、もちろん同じ条件に従う。言い換えれば、x⁴ + 1 が素数 p で割り切れるかどうかも、同じ条件に従う。さて p = 2 なら、x = 1 が解であることはすぐ分かる: 1⁴ = 1 ≡ −1 (mod 2)。問題は p が 3 以上の素数（奇素数）の場合だが…

証明　p を奇素数とする。mod p での原始根を一つ選んで g としよう。今、
　　x⁴ ≡ −1 (mod p)　　‥‥「☆」
に解 x = r があるとして、g を使って r ≡ g^k と書くと（k は r に対応して定まる整数で、1 以上 p−1 以下）:
　　r⁴ ≡ (g^k)⁴ = g^4k ≡ −1 (mod p)
原始根の性質から ≡ −1 になるのは (p − 1)/2 乗のときに限られる。つまり g^4k ≡ −1 の指数 4k は (p − 1)/2 に等しい:
　　4k = (p − 1)/2　両辺を2倍すると　8k = p − 1
従って p = 8k + 1。逆に p = 8k + 1 の形なら 4k = (p − 1)/2 なので:
　　(g^k)⁴ = z^4k = g^(p−1)/2 ≡ −1 (mod p)
つまり x = g^k は「☆」を満たす。□

定理1　8k+1型の素数は無限に存在する。

矛盾を導くため「8k+1型の素数は無限には存在せず、m 個しかない: {p₁, p₂, …, p_m} だけだ」と仮定する。A⁴ + 1 の形の奇数を作った場合、この奇数はもちろん 2 では割り切れないので、上記の補充法則によって、8k+1型の素因数だけを持つ。A⁴ + 1 が奇数であるためには、A⁴ が偶数になればいい。この下心に基づき、A の因子に 2 を入れておく:
　　A = 2p₁p₂…p_m
と置くと、奇数 B = A⁴ + 1 = (2p₁p₂…p_m)⁴ + 1 は8k+1型の素数 q で割り切れる（補充法則より）。しかしこの B は、明らかに p₁, p₂, …, p_m のどれで割っても（1余って）割り切れないので、q は、それらのどれとも違う8k+1型素数。要するに「8k+1型の素数のリストは有限だぜ」と仮定すると、「そのリストにない8k+1型素数 q があるじゃん」という結論になり、矛盾しちゃう。□

〔例〕　8k+1型素数が {17, 41} だけだと仮定。A = 2⋅17⋅41 = 1394。
　　B = 1394⁴ + 1 = 3776166151697 = 193 × 19565627729
と分解され、どちらの素因数も8k+1型。

〔暗算豆知識〕　1000 = 125 × 8 は 8 で割り切れるので、1000の倍数は、もちろん 8 で割り切れる。だから4桁以上の数を 8 で割った余りについては、1000単位の部分を無視して下3桁だけ考えれば十分。上記 19565627729 の例でいうと、ばか正直に左端から 8 で割らず、729 を 8 で割ることだけ考える。72 は（従って 720 も）一目で 8 の倍数なので、それも無視して「9 を 8 で割ること」を考えれば、瞬時に余り 1 と分かる。

200 = 50 × 4 = 25 × 8 は 8 で割り切れるので、3桁の数について、200単位の部分も無視していい（200 の倍数を引けるだけ引いて、つまり 200, 400, 600, 800 のどれかを適宜引き算して、200 未満の数を考えれば十分）。同じ発想で、その 200 未満の数からさらに 40, 80, 120, 160 を適宜引き算すれば、結局「40未満の数を8で割った余り」の計算に帰着され、簡単に暗算できる。例えば 729 → 600を引いて129 → 120を引いて9 としてもいい。

さらに別の方法として、下2桁を 8 で割った余りを考えてもいい。その場合、100 の位が偶数ならそれが答えだが（上記のように 200 の倍数は無視可能）、100 の位が奇数なら 4 を加減する（なぜなら 100 を 8 で割ると 4 余るので 100 ≡ 4 ≡ ±4 mod 8）。末尾 729 の上記の数では、29 を 8 で割ると 5 余る（あるいは 8 の倍数 32 より 3 小さいので −3 余るともいえる）。100 の位が奇数なので、そこから 4 を引いて（あるいは 4 を足して）答えは 1。もし仮に末尾が 731 だったら、同様に 31 ≡ 7 ということ（あるいは 31 ≡ −1 ということ）から、4 を引いて（あるいは足して）、答えは 3。――この最後の方法は簡単・便利なようだが、その代わり、場合によっては「88 と 96 が 8 の倍数」ということが判断基準となる。88 が 8 の倍数なのは当たり前として、96 は慣れてないと、ちょっと分かりにくいかも…。

補充法則と定理1の「8」と「4」をそれぞれ「16」と「8」に変えれば、同様にして、16k+1型素数が無限にあることを証明できるだろう。「16」と「8」をそれぞれ「32」と「16」に変えれば、32k+1型素数についても、またしかり。等々。

〔参考〕　「p が8k+1型の素数なら x⁴ ≡ −1 (mod p) を満たす x が存在する」という上記の事実を利用して、「この型の p を法として ±2 は平方剰余であること」の別証明が得られる（Gauß DA art. 115）。DA には、四乗剰余の（第一）補充法則について、かなり詳細な記述がある。参考リンク: 「第二補充法則の散歩道」シリーズ、特に「四乗剰余の冒険」以下。

【3】　話変わって、8k+5型素数（愛称: 秋素数）。Hardy & Wright は秋素数が無限にあることを証明しているが、複素整数の素因数分解が絡んだりして、入門者向きとは言い難い。4k+1型に対する高木のシンプルな証明をベースに、もっと簡単に同じ結論を導こう。

高木の証明を整理し直すと、要するに【２】の「8」と「4」をそれぞれ「4」と「2」に変えただけ。任意の x について、整数 x² + 1 の素因数は、4k+1型の素数 p か、偶数 2 に限られる（平方剰余の第一補充法則）。今、4k+1型の素数が有限個 S = {p₁, p₂, …, p_m} だけと仮定し、
　　A = 2p₁p₂…p_m
と置くと、奇数
　　《や》　B = A² + 1 = (2p₁p₂…p_m)² + 1
は、4k+1型の素数 q で割り切れ（補充法則より）、リスト S にない新しい素数が見つかる。

奇素数 q について A² + 1 ≡ 0 すなわち A² ≡ −1 (mod q) は「q が4k+1型」ということと同値。

《や》を次のように書くこともできる:
　　《ゆ》　B = 4(p₁p₂…p_m)² + 1
《ゆ》の丸かっこ内は、4k+1型の素数（つまり奇数）の積なので奇数。従って
　　(p₁p₂…p_m)²
は奇数の平方だから ≡ 1 (mod 8) となる（H-Wバージョン【2】参照）。つまり《ゆ》は:
　　《よ》　B = 4(p₁p₂…p_m)² + 1 ≡ 4⋅1 + 1 ≡ 5 (mod 8)

《や》の各素因数は4k+1型――つまり8k+1型または8k+5型。もしもどの因数も8k+1型、つまり ≡ 1 (mod 8) なら、それらの積も
　　B ≡ 1 × 1 × … × 1 ≡ 1 (mod 8)
になってしまい、《よ》と矛盾。だから《や》の素因数の少なくとも一つ（より正確に言うと奇数個）は、8k+5型でなければならない。

4k+1型素数が有限個なら8k+1型素数も有限個であり、その全ては（仮定上の）4k+1型素数のリスト S に含まれている。実際には、どんな有限リスト S を考えても、そのリストに載っていない4k+1型素数が《や》から必ず出現する（高木の証明法）。のみならず、出現する「新しい4k+1型素数」の中には、必ず8k+5型素数が少なくとも一つ含まれる。つまり、8k+5型素数も際限なく存在する。

〔例1〕　4k+1型素数が {5, 13} だけと仮定。A = 2 × 5 × 13 = 130:
　　B = A² + 1 = 130² + 1 = 16901
この 16901 は、それ自身4k+1型素数だが、8k+5型でもある！

〔例2〕　4k+1型素数が {5, 13, 17, 29, 37} だけと仮定。それらの積の2倍は 2371330:
　　B = 2371330² + 1 = 5623205968901 = 233 × 593 × 3301 × 12329
と分解される。右辺の4個の素因数はどれも4k+1型だが、そのうち 3301 は8k+5型（それ以外の3個は8k+1型）。

かくして次の定理が、あらためて証明された。

定理2　8k+5型の素数は無限に存在する。

---