メモ(数論7): ガウス整数など

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

数学 / 2 / 3 / 4 / 5 / 6 / Curios / 野蛮

***

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) = 32 + 02 = 32 = 9
なので、ぎりぎり「ノルム10以下」の範囲に入る。

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

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

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

一方、チョコレート素数だが…。チョコレート素数 q のノルムは q2 なので、ノルム n 以下の範囲に限るのなら q2 ≤ 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)2
は奇妙に砕けている(因子に「重複」がある)。一方、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 は 103 = 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 = 10n (n = 1, 2, …, 16) に対する G(x) の値は https://oeis.org/A091100 に載っている(単数倍の違いを無視せずに、4倍された値)。

x = 1018, 1020 に対する 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) は自力で計算するしかなさそうだ。1017 についてベタでやってみる(PARI)。

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

3秒ほどで 8541578 が返った。すると…
  G(1017) = 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(1019) = 2 × 117028833597800689 + 75939612 + 1 = 234057667271540991 「イ」

「使えるものは何でも使う」というアグレッシブな高速化のためには、A091099 の C(109) = 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(1017) = 2623557157654233 + 8541578 − 6284060 = 2623557159911751 「ア」と一致
  G(1019) = 234057667276344607 + 75939612 − 80743228 = 234057667271540991 「イ」と一致

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

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

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

V(x) が C(x) より大きくなる逆転領域のうち、9番目のものが 1018 付近に存在するという(2004年に発見された*)。同様の理由から、n が大きくなるとき…例えば n が100万までの範囲を考えると、δ(10n) が一瞬 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)b6

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

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

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

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

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

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

より一般的に p を任意の素数として、b を 1 以上 p 未満の整数とするとき、
  bp−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 を M1 として c − d を M2 とすると、M1 も M2 も m の倍数。
  (a + c) − (b + d) = (a − b) + (c − d) = M1 + M2
は、m の倍数を2個、足し合わせたものなので、m で割り切れる。□

なぜなら M1 = m × 整数、M2 = m × 整数なので、M1 + M2 = m × (整数 + 整数)。

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

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

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

一般に、一定の法 mod m について a1 ≡ b1 と a2 ≡ b2 が成り立てば、a1a2 ≡ b2b2 も成り立つ。

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

3個以上の数が掛け算される場合も同様。例えば、a1 ≡ b1, a2 ≡ b2, a3 ≡ b3 のとき、a1a2 ≡ b2b2 は証明済みなので、その式と a3 ≡ b3 について、左辺同士・右辺同士を掛け合わせれば:
  a1a2a3 ≡ b2b2b3

【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 ≡ b6 (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)(u2 + 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)b6 (mod 7)
の両辺を 1 × 2 × 3 × 4 × 5 × 6 で割る必要があった。より一般的に(後で整理し直すが)、素数 p を法とする合同式…
  《け》 1 × 2 × … × (p − 1) ≡ [1 × 2 × … × (p − 1)]bp − 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が使えない)、《く》《け》みたいには扱えない。(続く)

⁂


<メールアドレス>