メモ（数論12）: Unlucky Seven

チラ裏　＞　数論 i　＞　メモ12

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

• 2022-12-31　アンラッキー・セブン　2, 4, 8, 16, 32…の不思議
• 2023-01-02　アンラッキー・セブン②　幸運と不運の分かれ目
• 2023-01-04　アンラッキー・セブン③　2は1の4乗根!?
• 2023-01-08　オイラーの定理　もしも週が8日だったら
• 2023-01-12　アンラッキー・セブン④　あなたの勘では…？
• 2023-03-10　アンラッキー・セブン⑤（最終回）　73と89は超アンラッキー
• 2023-03-13　1000個のドアと1000人のいたずらっ子　有名（？）パズルのジョーク
• 2023-03-14　「1000人のいたずらっ子」パズルの答え　エレガントな解法ｗ
• 2023-03-24　完全数と忍者数　メルセンヌ数・再訪

2022-12-31　アンラッキー・セブン　2, 4, 8, 16, 32…の不思議

#数論　#ジグモンディの定理

2 を次々と倍々にした数 2, 4, 8, 16, 32, … に、それぞれ 1 を足してみます。
　　3, 5, 9, 17, 33, …
この一つ一つの数は、どんな数で割り切れるでしょうか？

3, 5, 17 は素数（1 と自分自身でしか割り切れない数）。9 は 3 で（2回）割り切れます。33 は 3 と 11 で割り切れます。

64, 128, … など、もうちょっと先まで同様のことを考えてみると――

2ⁿ + 1 の約数たち

n	2n	2n + 1	約数に分解
1	2	3	(3)
2	4	5	(5)
3	8	9	3 × 3
4	16	17	(17)
5	32	33	3 × (11)
6	64	65	5 × (13)
7	128	129	3 × (43)
8	256	257	(257)
9	512	513	3 × 3 × 3 × (19)
10	1024	1025	5 × 5 × (41)
11	2048	2049	3 × (683)
12	4096	4097	17 × (241)
13	8192	8193	3 × (2731)
14	16384	16385	5 × (29) × (113)
15	32768	32769	3 × 3 × 11 × (331)
16	65536	65537	(65537)

約数への分解は、素数の積の形で書いてあります。素数の約数（素因数）が2個以上あるとき、それらをいくつか掛け合わせたものも、約数: 例えば n = 9 の 513 = 3 × 3 × 3 × 19 は、もちろん 3 × 19 = 57 や 3 × 3 × 19 = 171 などでも割り切れる…。それはいいとして、丸かっこを付けてある素因数 (3), (5), (17), (11), …などは「新出素数」――つまり、表のもっと前の部分にはなかった素因数。例えば n = 6 の 5 × (13) でいうと、5 は n = 2 のとき既出なので丸かっこが付かず、(13) は既出でないので丸かっこ付き。n = 14 の場合、新出素数が2個あります！

この表をしばらく眺めていると、素朴な疑問として、全部の素数がどこかで新出するのだろうか？　3, 5, 11, 13, 17, 19 などがあるので、2 は別にして、全部の素数がどこかにありそうな気もしますが、素数 7 が見当たりません。もっと先まで表を作ると、そのうち 7 も出現するのでしょうか？

実は 7 は、どんなに n を大きくしても永遠に 2ⁿ + 1 の約数になることができない不運な素数（？）なのです。これ自体は、ちょっと考えると簡単に分かることなのですが（詳しくは次回以降）、興味をそそられますよね。他にも、同様の「不運な素数」があるのだろうか。ある素数が「不運」かどうか、事前に予言する方法はあるのだろうか？

さらに、この表をじっくり眺めていると、丸かっこ内の素数（＝新出素数）は、どれも新出時点の n の倍数より 1 大きい。例えば (11) は n = 5 で新出し、5 の倍数プラス1。(43) は n = 7 で新出し、7 の倍数プラス1。丸かっこ内の数を対応する n で割ると、必ず 1 余る！　これは、どういう現象なのでしょうか？

他にも、より深い問題として、なぜ n = 3 のときだけ新出素数がないのか？　これは Zsigmondy（ジグモンディ）の定理という、あまり聞いたこともないような定理の、特別な場合に対応する現象なのです…。

2, 4, 8, 16, 32, … なんていう平凡な数列でも、それに1プラスするだけで、面白いことがいっぱいあるものですね！　（下に続く）

2023-01-02　アンラッキー・セブン②　幸運と不運の分かれ目

#数論

2, 4 = 2 × 2, 8 = 2 × 2 × 2, 16 = 2 × 2 × 2 × 2, …は「2 だけ」を掛け合わせた数なので、3 では割り切れない。より詳しく言うと、2 は 3 の倍数より 1 小さい（この場合の「3 の倍数」とは「3 の 1 倍」つまり 3 自身）。このことを次のような記号で表す:
　　2 ≡ −1 (mod 3)
一方、4 は 3 の倍数より 1 大きい。8 は 3 の倍数より 1 小さく、16 は 3 の倍数より 1 大きい。記号的には、それぞれこうなる:
　　4 ≡ 1 (mod 3), 8 ≡ −1 (mod 3), 16 ≡ 1 (mod 3)

これについては、最初の…
　　2 ≡ −1 (mod 3)
…の両辺を2乗・3乗・4乗したと考えると、見通しがいい。例えば:
　　4 ≡ 1 (mod 3)　は　2² ≡ (−1)² (mod 3)　と同じこと（☆）
　　8 ≡ −1 (mod 3)　は　2³ ≡ (−1)³ (mod 3)　と同じこと

ところで本題とは全然関係ないが、（☆）は「マイナスかけるマイナスがプラスになることの証明」といえなくもない…。2² ≡ (−1)² が 4 ≡ 1 と同じ意味であるからには、(−1)² = (−1) × (−1) が +1 と同じ意味にならねばならず、事実 4 は 3 の倍数プラス 1 である！

【1】　より一般的に、−1 の偶数乗は +1、奇数乗は −1 なので、2 の偶数乗は 3 の倍数より 1 大きく、2 の奇数乗は 3 の倍数より 1 小さい（ここで偶数・奇数というのは、正の偶数・奇数のこと）。すなわち:
　　n は偶数　⇔　2ⁿ ≡ 1 (mod 3)
　　n は奇数　⇔　2ⁿ ≡ −1 (mod 3)
この2種類の式の両辺に 1 を足すと:
　　n は偶数　⇔　2ⁿ + 1 ≡ 2 (mod 3)
　　n は奇数　⇔　2ⁿ + 1 ≡ 0 (mod 3)
前者は「3 で割ると 2 余る」という意味を持ち、後者は「3 で割ると 0 余る」つまり「3 で割り切れる」という意味。

結局、2, 4, 8, 16, 32, … にそれぞれ 1 を足したもの――
　　3, 5, 9, 17, 33, …
――要するに、第n項が 2ⁿ + 1 である数列において、奇数番目の項は 3 で割り切れ、偶数番目の項は 3 で割り切れない（3 で割ると 2 余る…言い換えると、3 の倍数より 1 小さい）。よって、この数列の各項を素因数分解した場合、3 は第1項で新出素数となり、第3項・第5項・第7項…で既出素数となる。

2ⁿ + 1 の素因数: 3 の出現位置

n	2n	2n + 1	素因数分解
1	2	3	(3)
2	4	5	(5)
3	8	9	3 × 3
4	16	17	(17)
5	32	33	3 × (11)
6	64	65	5 × (13)
7	128	129	3 × (43)

【2】　第3項の素因数において、3 が二重に出現する理由は今のところ不透明だが、とにかくどの奇数項でも、素因数 3 が必ず一つは存在しなければならない。この単純な考察は、3 以外の素因数にも適用できる。例えば 2, 4, 8, 16; 32, 64, 128, 256; … を 5 で割った余りは 2, 4, 3, 1; 2, 4, 3, 1; … であり、周期4で同じ余りがループしている:
　　n = 1 のとき 2ⁿ ≡ 2 (mod 5)
　　n = 2 のとき 2ⁿ ≡ 4 (mod 5)　言い換えれば　2ⁿ ≡ −1 (mod 5)
　　n = 3 のとき 2ⁿ ≡ 3 (mod 5)　言い換えれば　2ⁿ ≡ −2 (mod 5)
　　n = 4 のとき 2ⁿ ≡ 1 (mod 5)
　　n = 5 のとき 2ⁿ ≡ 2 (mod 5)
　　n = 6 のとき 2ⁿ ≡ 4 (mod 5)　言い換えれば　2ⁿ ≡ −1 (mod 5)
　　n = 7 のとき 2ⁿ ≡ 3 (mod 5)　言い換えれば　2ⁿ ≡ −2 (mod 5)
　　n = 8 のとき 2ⁿ ≡ 1 (mod 5)
　　………

2ⁿ + 1 が素因数 5 を持つこと、つまり 2ⁿ + 1 が 5 で割り切れるということは、
　　2ⁿ + 1 ≡ 0 (mod 5)　両辺から 1 を引けば　2ⁿ ≡ −1 (mod 5)
ということなので、上記の観察から、n = 2 のとき 5 が新出素数となること、その後、4項ごとに（第6項・第10項・第14項などで） 5 が既出素数となることが予想される。事実、例えば 2¹⁰ = 1024 に 1 を足せば 5 の倍数になる！

〔参考〕　2 の累乗は偶数なので、最下位桁は偶数。従って、mod 5 で 2, 4, 5, 1 のループは、mod 10 で 2, 4, 8, 6 のループとなる。実際:
　　2, 4, 8, 16; 32, 64, 128, 256; 512, 1024, 2048, 4096; …

【3】　じゃあ一体なぜ、素数 7 には同様の議論が通用しないのか（どこまで行っても 7 が新出素数にならないのか）？　素数 11 や 13 や 17 などはどこかで出現するのに（前回参照）、なんで 7 は駄目なの？

2ⁿ + 1 が素因数 7 を持つこと、つまり 2ⁿ + 1 が 7 で割り切れるということは、
　　2ⁿ + 1 ≡ 0 (mod 7)　両辺から 1 を引けば　2ⁿ ≡ −1 (mod 7)
ということなので、それが不可能という現象については、次のように要約できる:
　　2, 4, 8, 16, 32, … は、どこまで行っても 7 の倍数より 1 小さくなることはない。
実際 2, 4, 8, 16, 32, 64, … をそれぞれ 7 で割った余りを調べてみると 2, 4, 1; 2, 4, 1; … という周期3のループになって、余り 6 にはならない。

そもそも「余りがループする」というのは、どういう現象なのだろうか。確かに数値的観察では「余りがループする」ようだけど、ものすご～い先の例えば第1万項くらいで、突然気まぐれに余りが 6 になったりしないのだろうか…？

その点を解明する必要があるのだが、とりあえず今回の考察からだけでも、次の重要な結論が得られる。

「第n項が 2ⁿ + 1 の数列」の各項の素因数を考えたとき、素数 p の出現位置では、次が成り立つ:
　　2ⁿ ≡ −1 (mod p)
この条件を満たす n が一つ以上あるとして、そのうち最小の n において p は新出する。

一般論として、もし p で割った余りがループするのなら（事実ループするのだが）、一度でも出現した素因数は――何らかの周期でループするのだから、その一定の周期で――無限回、出現する。つまり上記の「一つ以上あるとして」というのは控えめな表現で、実際には、あるのなら無限個ある。無限回の出番がある「幸運な素数」と、一度も出番のない「不運な素数」の分かれ目は、上記の条件を満たす n の有無。

次回は、この「余りのループ」について研究してみたい――Fermat の小定理に関連する現象だが、Fermat の小定理を使わない証明も可能かもしれない。

実は、素数の新出位置には、かなり強い制約がある。前回の表を詳しく観察すると、「p が n において新出するなら、n は p − 1 の約数」ということが予想される。しかも、どんな約数でもいいわけではなく、p − 1 の2分の1、または4分の1、または6分の1…など「偶数分の1」であることが必要。従って、p = 7 が新出するチャンスがあったとしたら、唯一 n = 3 においてだった（p − 1 = 6 の「偶数分の1」の形の約数は、それしかない）。p = 7 がこの唯一のチャンスを生かせなかったのは「たまたま不運」だったのだろうか。それとも、何か理由があるのだろうか？

2023-01-04　アンラッキー・セブン③　2は1の4乗根!?

#数論

ある数の4乗根とは、4乗するとその数になる値。例えば 3 を 4 乗すると…
　　3⁴ = 3 × 3 × 3 × 3 = (3 × 3) × (3 × 3) = 9 × 9 = 81
…なので 3 は 81 の4乗根。同様に 2⁴ = 16 なので、2 は 16 の4乗根。

パラレルワールドの一つ mod 5 の世界では、「5 で割った余りが同じなら同じ値」と見なされるので、16 と 11 と 6 と 1 などは「同じ」（合同）:
　　16 ≡ 11 ≡ 6 ≡ 1 (mod 5)
だから 2⁴ ≡ 1 (mod 5) であり、2 は 1 の4乗根となる！

驚くべきことに 3 以上のどんな奇数 a を考えても、パラレルワールド mod a では、2 は 1 の何乗根かになっている。例えば…
　　a = 3 のとき　2² = 4 ≡ 1 (mod 3)　つまり 2 は 1 の2乗根
　　　↑　4 を 3 で割ると 1 余る
　　a = 5 のとき　2⁴ = 16 ≡ 1 (mod 5)　つまり 2 は 1 の4乗根
　　　↑　16 を 5 で割ると 1 余る
　　a = 7 のとき　2³ = 8 ≡ 1 (mod 7)　つまり 2 は 1 の3乗根
　　　↑　8 を 7 で割ると 1 余る
　　a = 9 のとき　2⁶ = 64 ≡ 1 (mod 9)　つまり 2 は 1 の6乗根
　　　↑　64 を 9 で割ると 1 余る
　　a = 11 のとき　2¹⁰ = 1024 ≡ 1 (mod 11)　つまり 2 は 1 の10乗根
　　　↑　93 × 11 = 930 + 93 = 1023 は11の倍数なので、1024 を 11 で割ると 1 余る
　　a = 13 のとき　2¹² = 4096 ≡ 1 (mod 13)　つまり 2 は 1 の12乗根
　　　↑　315 × 13 = 3150 + 945 = 4095 は13の倍数なので、4096 を 13 で割ると 1 余る

この一つ一つの観察は、別々のパラレルワールド内のことだが、それにしても mod 3, mod 5, mod 7, mod 9 などのどの世界でも、同様の現象が起きている。これは「フェルマーの小定理」の一般化と関係あるのだが、以下では、もっと単純な発想で、このミステリーを解明してみたい。

【1】　例えば 5 で割った余りは 0, 1, 2, 3, 4 の5種類しかない。一方、2 を倍々にした数（2, 4, 8, 16, 32, 64, …）は、無限に考えられる。ということは 2, 4, 8, 16, 32, 64, … の一つ一つを 5 で割ると（割られる数は無限に続くけど、余りは5種類しかないんだから）、どこかで同じ種類の余りが出る。だって、仮に5番目までの数が全部異なる種類の余り（0, 1, 2, 3, 4 のどれか）を持つとしても、6番目の数は、もはや違う種類の余りを持つことはできない――遅くとも5番目までには、全種類の余りが出尽くしてしまうから。

だから 1 から 6 の範囲の、何らかの2種類の整数 ○ と △ について、2^○ と 2^△ は、5 で割ったとき同じ余りを持つ。この相異なる2種類の整数 ○ と △ のうち、大きい方を x、小さい方を y とでもすると:
　　2^x ≡ 2^y (mod 5)　ただし x は y より大きい
この両辺を 2^y で割ると:
　　2^x/2^y ≡ 2^y/2^y (mod 5)　つまり　2^x−y ≡ 1 (mod 5)　　※注1
x は y より大きい整数なので x − y = ℓ は正の整数になって:
　　2^ℓ ≡ 1 (mod 5)
ℓ がいくつかはともかく、mod 5 の世界で 2 が 1 の ℓ 乗根になるのは必然といえる。具体的な数値としては 2⁵ = 32 と 2¹ = 2 は、どちらも 5 で割ると 2 余るので、x = 5, y = 1 となって ℓ = 5 − 1 = 4。つまり、この世界では 2 は 1 の4乗根となる（最初に観察した通り）。

※注1　　2^x/2^y = 2^x−y になる理由: 「x 個の 2 の積」が分子、「y 個の 2 の積」が分母なので（そして x の方が大きいので）、約分すると、分子にある 2 が y 個消え、分母は 1 になる; 結局、約分の結果は「x−y 個の 2 の積」。…やってることは普通の整数の計算と同じだが、正確に言うと、これは「パラレルワールドの割り算」。2^yと mod の数 5 が互いに素であることから、2^y で自由に割り算できるのだ。

【2】　「5 で割った余りは 0, 1, 2, 3, 4 の5種類」といっても、よく考えてみると 2, 4, 8, 16, 32, … が 5 で割り切れること（余りが 0 になること）はあり得ないので、この場合、実際には「発生する可能性のある余り」は 1, 2, 3, 4 の4種類しかない。だから、どんなに遅くとも 2, 4, 8, 16, 32, … の4番目の数までで、可能性のある全種類の余りは出尽くしてしまい、5番目の数では既出の余りが再出現する。事実「1番目の数 2 と5番目の数 32 は、どちらも 5 で割ると 2 余る」。

同様に考えると、2, 4, 8, 16, 32, 64, … を 7 で割った余りは、可能性として1～6の6種類しかなく、遅くとも7番目の数までには、同じ余りが2回以上出るはず。この場合、実際には7番目まで行くまでもなく、4番目の 16 が、1番目の 2 と同じ余りを持つ（どちらも 7 で割ると余り 2）。【1】と同様に表現すると…
　　x = 4, y = 1 に対して 2^x ≡ 2^y (mod 7)
　　従って　2^x−y = 2³ ≡ 1 (mod 7)
…となり、mod 7 では、2 は 1 の3乗根となる（最初に観察した通り）。この場合、理論上の可能性として余りは最大6種類あるものの、実際には、3種類の余りしか出現しない。2, 4, 8, 16, 32, 64, … を 7 で割った余りは、2, 4, 1, 2, 4, 1, … となっている。

より一般的に、2, 4, 8, 16, 32, … を3以上の奇数 a で割った余りは、a−1 種類の選択肢しかないので、遅くとも a 番目の項までには同じ余りがリピート。それについて上記と同様の分析をすると、mod a の世界では、「1 は 2 の ℓ 乗根」となる（ℓ の具体的な値は a によって異なる）。要するに、
　　2^ℓ ≡ 1 (mod a)　　‥‥《あ》
が成り立つ。言葉で言えば 2 を ℓ 乗すると ≡ 1 になる。

【3】　2, 4, 8, 16, 32, … を a で割った余りは、mod a では 2, 4, 8, 16, 32, … 自身と「同じ」であり、次々と 2 倍になっていく。例えば:
　　2 ≡ 2 (mod 7), 4 ≡ 4 (mod 7), 8 ≡ 1 (mod 7), 16 ≡ 2 (mod 7), …
だから 2 を ℓ 乗すると ≡ 1 になるということは（上記の例では ℓ = 3）、「その次の数」は ≡ 2 に戻る（1番目の余りと同じ）ということであり、従って「そのまた次の数」は ≡ 4 ということであり（2番目の余りと同じ）、以下同様にループする。そして 2ℓ 乗すれば再び ≡ 1 になって、無限に同じことが繰り返される。というのも:
　　《あ》の両辺を 2 乗すれば (2^ℓ)² ≡ 1²　つまり　2^2ℓ ≡ 1 (mod a)
　　《あ》の両辺を 3 乗すれば (2^ℓ)³ ≡ 1³　つまり　2^3ℓ ≡ 1 (mod a)
　　《あ》の両辺を 4 乗すれば (2^ℓ)⁴ ≡ 1⁴　つまり　2^4ℓ ≡ 1 (mod a)
　　………

以上のことから 2, 4, 8, 16, 32, … を奇数 a で割った余りは、周期 ℓ でループする。これが前回観察した「余りのループ」の正体。このことは 2, 4, 8, 16, 32, … の各数に 1 を足した数列――
　　3, 5, 9, 17, 33, …
――の各項がどんな素因数を持つか？という最初の疑問（新出素数）にも、重大な影響を及ぼす。

けれど、奇数 a とそれに対応する周期 ℓ は、一体どういう関係にあるのだろうか？

周期 ℓ は最大でも、「可能性のある全種類の余り」が出尽くす a−1 であり、mod 7 の場合のように a−1 より小さいこともある。今回の観察からだけでも、それは分かる。a が小さい場合には、2¹, 2², 2³, … を一つずつ a で割ってみれば、どこかで余りが 1 になるのだから、実用上、一つずつ試すことで ℓ を確定できるだろう。でも例えば a = 123 のように少し数が大きくなった場合、この考え方だと、ℓ を決定するのに最悪100回以上も試行錯誤の割り算を繰り返す必要がある…。計算の手間についてはとりあえず無視するとしても、「1 から a−1 のどれかの数」というのでは、あまりにも漠然としていて、見通しが悪い。ここはやはりフェルマーの小定理や、その一般化を考えるのが得策のようだ…。（続く）

2023-01-08　オイラーの定理　もしも週が8日だったら

#数論

「小学生のフェルマーの小定理」の別バージョン。簡単な算数だけで「オイラーの定理」。アホくさい（けど分かりやすい？）アプローチをお楽しみください。

【1】　「1週間が8種類の曜日から成る異世界」を考える。8種類の曜日を順に「1曜日」「2曜日」…「8曜日」と呼ぶことにして、話を簡単にするため、毎月の「1日」は「1曜日」に固定されているとする（そして月の日数は無限にあるとしよう）。「8曜日」である8日の翌日の9日は、「1曜日」に戻る。そのまた翌日の10日は「2曜日」。そして例えば（その5日後の）15日は「7曜日」…。一般に「D日」は、D が8の倍数なら「8曜日」で、そうでなければ D を8で割った余りを R として「R曜日」となる。

この架空のカレンダーにおいて、第一週の「奇数曜日」は、もちろん次の 4 種類の日付:
　　S = {1, 3, 5, 7}
これらの各日付を奇数倍すると、再び 4 種類の「奇数曜日」の日付になる。例えば、3倍したものをこう書くことにする:
　　3S = {3, 9, 15, 21}　　←　S の4個の日付をそれぞれ3倍した
これらの新しい4種類の日付のうち（「3曜日」の3日は新しくないが）、9日は「1曜日」、15日は「7曜日」、21日は「5曜日」なので、3S は、S と同じく、4種類の「奇数曜日」を過不足なく1回ずつ含む。同様に:
　　5S = {5, 15, 25, 35}
は左から順に「5曜日」「7曜日」「1曜日」「3曜日」なので、4種類の「奇数曜日」を1回ずつ含み、
　　7S = {7, 21, 35, 49}
は左から順に「7曜日」「5曜日」「3曜日」「1曜日」なので、やはり4種類の「奇数曜日」を1回ずつ含む。

【2】　より一般的に、1週間が w 種類の曜日から成るとして、全種類の曜日（すなわち「1曜日」から「w曜日」）のうち、曜日の番号と w が2以上の公約数を持たない場合を「素敵な曜日」と呼ぶことにする。例えば w = 6 の場合（1週間が6日）、素敵な曜日は「1曜日」と「5曜日」の2個しかない――「2曜日」「4曜日」「6曜日」は、「2」「4」「6」が w = 6 と公約数2を持つので素敵でなく、「3曜日」「6曜日」は、「3」「6」が w = 6 と公約数3を持つので素敵でない（「6曜日」は二重の意味で、素敵でない）。

w = 7 の場合、「7曜日」以外は全部素敵（w が変わったので「6曜日」は素敵になった）。w = 8 の場合（【1】参照）、奇数曜日が素敵。w = 9 の場合、「3曜日」「6曜日」「9曜日」は素敵でないが、それ以外の6種類の曜日は素敵。w = 10 の場合「1曜日」「3曜日」「7曜日」「9曜日」の4種類が素敵。w = 11 の場合、「11曜日」以外の10種類が全部素敵。

「素敵な曜日」の日付を「素敵な日付」「素敵な数」と呼ぶことにしよう。実は、第一週の「全種類の素敵な日付」に「素敵な数」を掛けた日付は、再び「全種類の素敵な日付」になる。例えば w = 8 の場合、第一週の奇数曜日
　　S = {1, 3, 5, 7}
が「素敵」であり、1, 3, 5, 7 という日付の数字自身は「素敵な数」に当たる。そして 3S も 5S も 7S も S と全く同じ曜日の集合であることは【1】の通り。別の例として w = 6 の場合、第一週の素敵な日付は:
　　S = {1, 5}
これらの日付に、素敵な数 5 を掛けると:
　　5S = {5, 25}
5日は「5曜日」、25日は（週が6日のこの世界では）「1曜日」なので、曜日の観点では、この 5S もやはり S と同じであることが分かる。

この性質は――少々意味不明なように思えるかもしれないが――オイラーの定理を証明するための鍵となる。

〔付記〕　実は「素敵な数」というコンセプトは「逆数を持つ数」という意味を持ち、「素敵な数」だけを考えることは「掛け算・割り算が自由にできる世界」を構築することに当たる（付録参照）。

「素敵な曜日」の定理　1 以上の任意の整数 w を選んで、固定する。その w に対して、第一週の全種類の素敵な日付を集めたもの――
　　S = {d₁, d₂, …, d_e}　　ここで e は第一週に含まれる素敵な曜日の数
――を（その w についての）オイラー集合と呼ぶことにしよう。オイラー集合の各要素に、任意の素敵な数 a を掛けた結果の e 種類の日付――
　　aS = {ad₁, ad₂, …, ad_e}
――は、S と同じく、全種類の素敵な曜日を過不足なく1個ずつ含む。

〔注意〕　「素敵」の定義は「w との間に 2 以上の公約数がない」。教科書用語で言えば「互いに素」ってやつ。言い換えると、素敵な数というのは、「w のどの素因数 p から見ても p の倍数ではない」ような数。「オイラー集合」というのは説明の便宜上の名前で、一般的な用語ではない。

証明　aS に含まれる e 個の日付は、どれも素敵。というのも、仮定によって a は素敵だし、d₁, d₂, … なども素敵なので、前者も後者も、w の素因数 p の倍数ではない。素数 p の倍数ではない数を掛け合わせても、もちろん p の倍数になるわけがなく、すなわち素敵な数と素敵な数の積は、素敵なまま。

これで「aS の日付は全部素敵」ってことは分かったが、問題は「これらの日付は、全部曜日が別々か」。もしも同じ曜日の日付が2個以上含まれていたら、aS には e 個しか日付がないんだから、e 種類の素敵な曜日を全部含むことは不可能で、定理が成り立たない。他方、aS の日付の曜日が全部異なるのなら、aS はちょうど e 種類の日付を含むのだから、e 種類の素敵な曜日をちょうど1個ずつ含むことになり、定理が証明される。…真相は後者であること（つまり、曜日の重複が起きないこと）を示そう。もし仮に、例えば ad₁ と ad₂ が同じ曜日だとすると:
　　ad₁ ≡ ad₂ (mod w)　　‥‥《い》
――ここで
　　左辺 ≡ 右辺 (mod w)
という記号の意味は「左辺を w で割った余りと、右辺を w で割った余りが等しい」（詳細）。

a と w は互いに素なので（つまり a は素敵なので）、《い》の両辺を a で割ることができて:
　　d₁ ≡ d₂ (mod w)　　‥‥《う》
これは d₁ と d₂ が同じ曜日という意味だが、そんなことが起きるはずない（理由: オイラー集合 S は「第一週の」素敵な曜日の日付なので――そして週の全部の日付は曜日が違うので――、同じ曜日が2回以上含まれるわけない）。要するに「ad₁ と ad₂ が同じ曜日」という仮定《い》は、無理！

ad₁ と ad₂ に限らず、aS に含まれるどの2個の（相異なる）日付を選んでも、全く同様の議論が成り立つ: もしも《い》に当たる式が成り立つなら（つまり曜日の重複が起こるとしたら）、その両辺を a で割ると《う》の形になるが、その結論は無理なので、曜日の重複はあり得ない。□

【3】　このことから、次の重大な定理が成り立つ。

オイラーの定理　1 以上の任意の整数 w について、a を任意の素敵な数として、オイラー集合の要素の数を e とすると:
　　a^e ≡ 1 (mod w)

証明　「素敵な曜日」の定理によれば S に含まれる e 個の日付と aS に含まれる e 個の日付は、曜日が1対1対応。つまり次の e 個の式が成り立つ:
　　d₁ ≡ ad_● (mod w)　　← 最初の素敵な曜日
　　d₂ ≡ ad_▲ (mod w)　　← 2個目の素敵な曜日
　　………
　　d_e ≡ ad_■ (mod w)　　← 最後の（e個目の）素敵な曜日
ここで右辺の ●, ▲, …, ■ は、何かの数字（d の右下に付く番号）。具体的にどれがどれかはケースバイケースだが、とにかく全体としては 1, 2, …, e が過不足なく1回ずつ現れる（言い換えると aS の各要素 ad₁, ad₂, …, ad_e が1回ずつ右辺に登場）。上記 e 個の式の左辺同士・右辺同士を全部掛け合わせると:
　　d₁d₂…d_e ≡ a^e(d₁d₂…d_e) (mod w)
d₁, d₂, … などは全部素敵なので、それらの積 d₁d₂…d_e も素敵であり、上の式の両辺をこの数で割ることが許される。その結果は:
　　1 ≡ a^e (mod w)
すなわち、オイラーの定理が成立。□

〔例1〕　w = 8 のとき e = 4 だった（奇数曜日が素敵になるケース: 【1】【2】参照）。素敵な数（つまり w = 8 と互いに素な数）の例として a = 3 を選ぶと、オイラーの定理によって、
　　a^e ≡ 1 (mod w)　すなわち　3⁴ ≡ 1 (mod 8)
が予言される。これは 3⁴ を 8 で割ると 1 余るという意味だが、3⁴ = 81 は、まさにこの性質を持っている。予言が的中した！

〔例2〕　w = 9 のとき、オイラー集合は {1, 2, 4, 5, 7, 8} で e = 6。素敵な数の例として a = 2 を選ぶと、
　　a^e ≡ 1 (mod w)　すなわち　2⁶ ≡ 1 (mod 9)
が予言される。これは 2⁶ = 64 を 9 で割ると 1 余るという意味だが、まさにそうなっている。

〔例3〕　w = 10 のとき、オイラー集合は {1, 3, 7, 9} で e = 4。素敵な数の例として a = 3 を選ぶと、
　　a^e ≡ 1 (mod w)　すなわち　3⁴ ≡ 1 (mod 10)
が予言される。これは 3⁴ = 81 を 10 で割ると 1 余るという意味だが、まさにそうなっている。

【4】　オイラーの定理の特別の場合として、もし w が3以上の素数なら、素数の性質上 w の約数は 1 と w 自身だけなので、オイラー集合は
　　{1, 2, …, w−1}
となる――要するに「w曜日」以外の全部の曜日が素敵。この場合 e = w−1 だから（理由: w 個の曜日の中で最後の 1 個を除いたものが素敵）、オイラーの定理はこうなる:
　　a^w−1 ≡ 1 (mod w)
これはフェルマーの小定理に他ならない。

つまり、オイラーの定理の証明によって、フェルマーの小定理も証明されたことになる。フェルマーの小定理では mod が素数に限られるが、オイラーの定理では、それが拡張され、任意の正の整数を mod とすることができる。オイラーの定理はフェルマーの小定理の上位バージョンで、有効範囲が広い！

正の整数 w を選べば、それに対応するオイラー集合のサイズ e が定まる。 w を入力として e を求めるこの計算（関数）は、オイラーのファイ関数と呼ばれ、e = φ(w) のように表記される。w が素数の場合に限れば、オイラーの定理は「フェルマーの小定理」と同じ意味になり、前述のように e = φ(w) = w−1 という簡単な計算が成り立つ。

この観点から見ると、mod p におけるフェルマーの小定理の指数 p−1 の正体は、p に対するオイラー集合の要素の数。

…というわけで、オイラーの定理の表面的意味を理解することは、別に難しくない。「オイラー集合のどの要素も e 乗すると ≡ 1 になる」というだけの話。そして e は「その集合の要素の数」という単純明快な意味を持つ。

〔例1〕　w = 6 のとき {1, 5} の 2 個が素敵（e = 2）。素敵な数を 2 乗すると ≡ 1 になる。つまり…
　　1² = 1
　　5² = 25
…のどちらの数も、w = 6 の倍数より 1 大きい。

〔例2〕　w = 7 のとき {1, 2, 3, 4, 5, 6} の 6 個が素敵（e = 6）。例1と同様に…
　　1⁶ = 1
　　2⁶ = 64
　　3⁶ = 729
　　4⁶ = 4096
　　5⁶ = 15625
　　6⁶ = 46656
…のどの数も、w = 7 の倍数より 1 大きい。

けれど「w が与えられたとき、どうやって e を決定するか」（オイラーのファイ関数の計算法）という問題が、残っている。それがはっきりしないことには、オイラーの定理を活用しにくい…。w が素数のときは上記のように 1 を引くだけで e が求まるが、w が素数以外の場合にどうすればいいのだろうか…。（続く）

【5】（付録）　群論は好きですか…？　群論って眠くなる…？　「群論」なんて聞いたこともない…？　まぁ、とりあえず必要もないけど、せっかくここまで来たんだ、ちょっと脱線して、オイラー集合がどんな「世界」なのか、群論的に考えてみる――といっても、小難しい群論用語を使わず、同じ意味のことを普通の言葉で書くね♪

オイラー集合は、単なる「要素の集まり」ではなく「その内部で自由に掛け算ができる」という性質を持つ。どういう意味かというと…

1週間の曜日の数 w ――言い換えれば mod の数――に対応するオイラー集合は、そのカレンダーの全種類の「素敵な数」の集まりじゃん？　でもって「素敵な数」と「素敵な数」の積は再び「素敵な数」でしょ？　例えば mod 10 での掛け算の表は次の通り（積が 10 を超えたら 10 で割った余りで置き換えている――結果的に、これらの積は、普通の掛け算の結果の最下位桁を取り出したものに当たる）。

〔解説〕　w = 10 の世界において、例えば「3曜日」になる日付（3 や 13 など）と「7曜日」になる日付（7 や 17 など）の積は、曜日の観点では「1曜日」の日付。この計算では（曜日さえ合ってれば）「その曜日の日付」としてどんな数を選んでも構わない。ざっくり言えば「3曜日」×「7曜日」=「1曜日」となる。なぜなら前者の日付は 10m+3 の形を持ち、後者の日付は 10n+7 の形を持つので、それらの積は次のように 10k+1 の形を持つ:
　　(10m+3)(10n+7) = 100mn+70m+30n+21 = 10(10mn+7m+3n+2)+1
最後の丸かっこ内を k とすると、上記の数は 10k+1 に等しい。あるいはもっと単純に:
　　3 × 7 ≡ 21 ≡ 1 (mod 10)

表からも一目瞭然だが、集合内でどのように掛け算をしても、結果は（曜日の観点では）再び集合内のどれかの要素に。さらに、この集合内には、どの要素に対しても逆数（掛けると積が 1 になる相手）がある。

「素敵な数」の積（mod 10）

×	1	3	7	9
1	1	3	7	9
3	3	9	1	7
7	7	1	9	3
9	9	7	3	1

逆数の存在（第一の証明）　w がどんな正の整数であるにせよ、その w に対して「1曜日」は素敵（なぜなら 1 と w は「2 以上の公約数」を持たない）。だから、オイラー集合は必ず「1」を含む。つまり集合内には、必ず要素「1」がある。

ヘッダーを除く表の中身（白い部分）について、最初の行（横）を「第一週の素敵な曜日」の日付と解釈すると、既に観察したように、掛け算の結果として、全部の行は「素敵な曜日」を過不足なく一つずつ含む（上の例では「1曜日・3曜日・7曜日・9曜日」――それを例えば 3 倍した日付は、再び全種類の素敵な曜日になるのだった）。あるいは最初の列（縦）を「第一週の素敵な曜日」と解釈すれば、全く同じ理屈から、どの列も「素敵な曜日」を過不足なく一つずつ含む。結局、どの行も、どの列も、重複なく「1」を1回だけ含む。その結果、どの要素から見ても、掛け算の結果が「1」になる相手（自分自身の場合もあるが）――つまり逆数――が、ちょうど一つ存在する。□

逆数を掛けることを「割り算」と呼ぶなら、オイラー集合は掛け算・割り算が自由にできる世界といえる（集合内の任意の数 a で割り算したければ、a の逆数を掛け算すればいい）。

逆数の存在（第二の証明）　逆数の存在については、オイラーの定理そのものからも、証明できる。任意の正の整数 w に対して、オイラー集合の要素の数（素敵な曜日が全部で何種類あるか？）を e として、任意の素敵な数を a とすると:
　　a^e ≡ 1 (mod w)
…これがオイラーの定理だが、a^e つまり「e 個の a を掛け合わせる」ということは、「e−1 個の a を掛け合わせて、さらにもう1回 a を掛けること」。つまり上の式をこう書くことができる:
　　(a^e−1)a ≡ 1 (mod w)
この式を解釈すると「任意の要素 a について、その a を (a^e−1) 倍すれば ≡ 1 になる」。この a^e−1 という数も、素敵な数（なぜなら、素敵な数 a を e−1 回掛け合わせたものなので）。だから（曜日の観点では）同じオイラー集合に属する。言い換えると…
　　任意の a ∈ S の逆数は a^e−1 ∈ S
となる。□

〔例〕　w = 10 のとき e = 4。この世界で a = 7 の逆数は a^e−1 = 7³ = 343 ≡ 3 (mod 10)。月の343日と3日は、曜日の観点ではどちらも「3曜日」で等しい。等しいのだから、どちらを使っても構わない: 7 × 343 = 2401 ≡ 1 (mod 10) なので 343 は 7 の逆数だし、7 × 3 = 21 ≡ 1 (mod 10) なので 3 も 7 の逆数。343 と 3 は同一の曜日を指す別名に過ぎない。

逆数の存在（第三の証明・参考）　上記2種類の説明と比べると分かりにくいかもしれないが、次のような分析もできる。1回読んだだけでピンとくる話じゃないかもしれないけど、参考までに…

任意の素敵な数 a と、基準となる w は、互いに素（最大公約数が 1）。だから、次の式を満たす整数 x, y が存在する（Bachet–Bézout の定理）:
　　ax + wy = 1　　‥‥《え》
この式を mod w で考えると、左辺第2項にある w の倍数 wy は消滅して ax ≡ 1 (mod w) となる。つまり a の逆数 x が（具体的な値は分からないけど）存在。問題は、この謎の要素 x が同じオイラー集合に属しているかどうかだが、《え》で変数名を交換して旧 a と旧 x をそれぞれ x と a と呼ぶことにすると、式《え》が成り立つことから、a は――つまりもともとの x は―― w と互いに素（Bachet–Bézout の定理の逆）。だから、もともとの謎の要素 x も素敵な日付。従って、曜日の観点では、オイラー集合に属する（＝この日付と曜日が同じ日付が、オイラー集合の要素の中にある）。□

この分析によると「逆数を持つこと」と「素敵であること」は本質的に同じ意味なので、「mod w のオイラー集合とは、mod w の要素のうち、逆数を持つやつだけを全部集めたもの」ってゆーことになる。

脱線ついでに、mod 8 の「素敵な数」の掛け算も見ておこう（mod 10 と原理は同じで、この場合、普通に掛け算して積が 8 を超えたら 8 で割った余りに置き換えている）。

「素敵な数」の積（mod 8）

×	1	3	5	7
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

mod 10 と同様、4種類の素敵な数があり、既に証明したようにどの数も逆数を持つのだが、掛け算の構造が異なる！　mod 8 のオイラー集合には、どの数も「自分自身が自分の逆数」（自分に自分を掛けると 1 になる）という奇妙な性質がある。mod 10 には、なかった性質だ…。

この性質は、かなりヤバイ。x² ≡ 1 (mod 8) を解きたいとき、「2次方程式の解は2種類」という常識を当てにして x ≡ 1 or −1 つまり x ≡ 1 or 7 (mod 8) とやると…。本当は4個も解があるのに、解が2個しか求まらない。一体どうすればいいんだッ？！

ところで mod 10 の4種類の要素については、たった一つの要素「3」のべき（累乗）として表現可能: 3¹ ≡ 3, 3² ≡ 9, 3³ ≡ 7, 3⁴ ≡ 1 (mod 10)。一方 mod 8 では、上記のヤバイ性質のせいで、どの数からスタートしても2乗しただけで ≡ 1 になってしまい、従って3乗するともともとの数に戻ってしまうので、同様のことができない。「4種類の要素を持ち、掛け算・割り算が自由にできる世界」という点は同じでも、mod 8 と mod 10 のオイラー集合は内部構造が違う…ってことが分かる。

だから何なのか？　そんな分析が、何の役に立つの？

一言で言えば「世界を外側から眺める」ってこと。例えばの話、地上の人が「雲の動き」を研究しようとしても、狭い範囲のことしか分からない。人工衛星を使って地球を外から眺めると、雲やら台風やらがどこをどう動いているのか、一目瞭然。

ある世界（例えば、整数の世界）の中で何かを計算してみても、実は「その世界自体」のことは、あまりよく見えない。世界を外から眺めて「その世界の全体像」を把握できれば、逆に「その世界での計算」のことも深く理解できるだろう。昔は、地球が平面なのか球なのかも結論が出ていなかったけど、地球を外から眺めれば疑問の余地はなくなるし、地球が球だと分かってみれば、測量だって正確にできる。しっかりした地図も作れる。

群論とは…
　　人工衛星のようなもの。打ち上げ・運用には綿密な計画・判断が必要だが、使いこなすと超強力なツール！
　　数学といっても、普通の意味での「計算」とかの話じゃない。「計算の舞台になる世界」それ自体を問題にする。

2023-01-12　アンラッキー・セブン④　あなたの勘では…？

#数論　#第二補充法則

フェルマー風の数列――
　　A: 3, 5, 9, 17, 33, 65, 129, …
それは 2 が倍々となる次の数列の各項に 1 を足したもの。
　　B: 2, 4, 8, 16, 32, 64, 128, …

A の偶数番目の項 5, 17, 65 = 5 × 13, 257, 1025 = 5 × 5 × 41, … を調べると、どの数も、そしてどの約数も、「4 の倍数より 1 大きい」という性質を持っているようだ。そういう目で、今度は A の奇数番目の項を眺めると:
　　3, 9 = 3 × 3, 33 = 3 × 11, 129 = 3 × 43, 513 = 3 × 3 × 3 × 19, …
因数にやけに 3 が多いことはさておき、どの素因数も「4 の倍数より 1 小さい」ようだ（3, 11, 43, 19）。――偶数番目・奇数番目の項に関するこの観察。たまたま数列の最初の方がそうなってるだけなのだろうか。それとも、どこまで行っても、無限にこの性質が維持されるのか？

あなたの勘では…？

【1】　B の第2項以降は全部 4 の倍数なのだから、それに 1 を足した A の第2項以降が 4k+1 の形（k: 整数）を持つことは、当たり前。でも 4k+1 の形だからといって、それを徹底的に約数に分解したとき――（1 と自分自身以外に約数を持たない）素数にまで分解したとき――、その素数も 4k+1 型になるとは限らない。実際 A の第3項 9 = 3 × 3 や第5項 33 = 3 × 11 では、4k+1 型の数が 4k+3 型の素数の積に分解される。

ところが A の偶数番目の項に関する限り、どこまで行ってもその素因数は 4k+1 型に限られる。次の法則がその根拠。

第一補充法則　p を 3 以上の素数とする。このとき、もし p が 4k+1 型なら、x² ≡ −1 (mod p) は（整数の）解を持つ。逆に、この式が解を持つのは p が 4k+1 型の場合に限られる。≡ −1 の意味は、下記の具体例参照。

A の第 n 項を A_n = 2ⁿ + 1 としよう。もし n が偶数 2m なら（m は 1 以上の整数）、こうなる。
　　A_2m = 2^2m + 1 = (2^m)² + 1
この数が 3 以上の素数 p で割り切れるとすると、それは p で割った余りが 0 という意味なので:
　　(2^m)² + 1 ≡ 0 (mod p)　　‥‥《か》
両辺から 1 を引くと:
　　(2^m)² ≡ −1 (mod p)　　‥‥《き》
言い換えると x² ≡ −1 (mod p) には x = (2^m) という解がある。だから、第一補充法則から p は 4k+1 型に限られる！

〔具体例〕　m = 3, n = 2m = 6 の場合、A₆ = 2⁶ + 1 = 65 は、素数 p = 13 で割り切れる（p = 5 でも割り切れるが、ここでは例として 13 を取り上げる）。このとき 2^m = 2³ = 8 なので、《か》に当たる式は:
　　8² + 1 ≡ 0 (mod 13)
《き》に当たる式は:
　　8² ≡ −1 (mod 13)
だから x² ≡ −1 (mod 13) には、少なくとも一つの解 x = 8 がある。ここで ≡ −1 (mod 13) というのは「13 で割ると −1 余る」つまり「13 で割り切るには 1 不足している」＝「13 の倍数より 1 小さい」と解釈可能（実際 64 は、13 の倍数 65 より 1 小さい）。あるいは、上の式の左辺の 8² つまり 64 と、右辺の −1 は「13 で割った余りが同じ」と解釈することもできる。64 を 13 で割れば、商が 4 で余りが 12。一方、−1 を 13 で割れば――「商が 0 で余りが −1」とも言えるけど、「13 で割った余りは 0～12 のどれかになる」という常識を守るとすれば――商が −1 で余りが 12。確かに、どっちも余り 12。…けど、そんなふうにいちいち考えんのも面倒なので、
　　○ ≡ △ (mod □)
の形については、○ と △ の差が □ の倍数、と解釈するのが一番シンプルかもしれない（フェルマーの小定理への道②参照）。
　　8² ≡ −1 (mod 13)
の場合 8² − (−1) = 65 は、確かに 13 の倍数だ。

x² ≡ a (mod p) を満たす解 x がある場合、a は p の平方剰余（へいほうじょうよ）と呼ばれる。解がなければ a は平方非剰余（略して非剰余）と呼ばれる。「平方剰余」は、普通の整数の世界での「平方数」（4, 9, 16, 25, … など）と同様の概念の、mod p バージョン。「非剰余」の方は「非平方数」（平方数でない数）に当たる。第一補充法則は −1 が平方剰余になるための、必要十分条件。例えば x² = −1 (mod 7) は解を持たない（言い換えると −1 は 7 の非剰余。要するに、平方して 7 で割ったとき、余りが 6 になる整数は存在しない）: 奇数の素数 7 は 4k+1 型じゃないから、必要条件を満たさないのだ…。

〔補足〕　普通の整数の世界で、例えば 49 は平方数（7 の平方）。一方、3² ≡ 9 ≡ 2 (mod 7) なので、2 は mod 7 の世界の「平方数」（3 の平方）に当たる（3² の 9 自身も、もちろん「平方数」だが、それと合同な 2 も「平方数」）。つまり 2 は mod 7 における平方剰余――それを略して「2 は 7 の平方剰余」という。これは「7 の平方が ≡ 2」という意味ではなく、「何かの平方が mod 7 の世界で ≡ 2」という意味。同様に「−1 は 7 の非剰余」というのは「−1 の平方は ≢ 7」という意味ではなく「何を平方しても mod 7 の世界では ≢ −1」という意味。

【2】　この流れだと、何となく「同様の理屈で、最初の数列 A の奇数番目の項の素因数は 4k+3 型に限られるのだろう」という予感がするかもしれない…。「偶数番目の項の素因数が 4k+1 型限定なら、バランスの問題として、奇数番目の項の素因数は 4k+3 型限定だろう」という考えは不自然ではないし、最初に見たように少なくとも数列の最初の方では、実際その通りになっている。正確に言うと、第27項 A₂₇ までは、そうなっている。けど第29項は…
　　A₂₉ = 2²⁹ + 1 = 536870913 = 3 × 59 × 3033169
…分かりにくいが、実はこの 3033169 は4k+1型の素数。別の例として、第35項は:
　　A₃₅ = 2³⁵ + 1 = 34359738369 = 3 × 11 × 43 × 281 × 86171
281 が 4k+1 型であることは明らか。この数が素数であることも、簡単に確かめられる。

281 は 17² = 289 より小さいので、合成数だとすれば 2, 3, 5, 7, 11, 13 のどれかで割り切れるはず。どれでも割り切れないことは、暗算でも分かる。

従って「奇数番目の項の素因数は 4k+3 型に限られる」という予想は、正しくない！

実は、奇数番目の項の素因数は 8k+1 型または 8k+3 型に限られる。8k+3 型は 4k+3 型の一種なので、4k+3 型の素因数が含まれてること自体は事実だが、それに加えて、4k+1 型の一種（8 の倍数より 1 大きいタイプ）の素因数も、含まれる可能性がある。上記の 281 のように。

【3】　奇数番目の項のこの振る舞いは、幾つかの法則と関係している。まず…

第二補充法則　p を 3 以上の素数とする。このとき、もし p が 8k+1 型または 8k+7 型なら、x² ≡ 2 (mod p) は解を持つ。逆に、この式が解を持つのは p がこれらの型の場合に限られる。

第一補充法則は −1 が平方剰余になる必要十分条件だったが、第二補充法則は 2 が平方剰余になる必要十分条件。このことから p が 8k+3 型または 8k+5 型なら 2 は p の非剰余となる。表にまとめると:

第一・第ニ補充法則

↓奇素数 p の型		p の例	−1 は p の…	2 は p の…
4k+1	8k+1	17, 41	平方剰余	平方剰余
4k+3	8k+3	3, 11, 19, 43	非剰余	非剰余
4k+1	8k+5	5, 13, 29, 37	平方剰余	非剰余
4k+3	8k+7	7, 23, 31, 47	非剰余	平方剰余

4k+1 型、4k+3 型をそれぞれバニラ、チョコと呼ぶと、バニラがOKでチョコが駄目（第一補充法則）。8k+1, 8k+3, 8k+5, 8k+7 型をそれぞれ春・夏・秋・冬と呼ぶと、春・冬（両端）がOKで夏・秋が駄目（第二補充法則）。

さらに、次が成り立つ（第二補充法則【11】参照）。

平方剰余・非剰余の積の性質　〔ア〕 a, b が両方とも p の平方剰余なら ab も p の平方剰余。 〔イ〕 a, b の一方が p の平方剰余、他方が非剰余なら ab は p の非剰余。 〔ウ〕 a, b が両方とも p の非剰余なら ab は p の平方剰余。

平方剰余を (+1) として、非剰余を (−1) とすると、(+1) 同士の積、(−1) 同士の積は (+1) になり、(+1) と (−1) の積は (−1) になる。

今、最初の数列の奇数番目の項――第 2m+1 項とする――を考えると（m は 0 以上の整数）:
　　A_2m+1 = 2^2m+1 + 1 = 2(2^m)² + 1
この数が 3 以上の素数 p で割り切れるとすると:
　　2(2^m)² + 1 ≡ 0 (mod p)
両辺から 1 を引くと:
　　2(2^m)² ≡ −1 (mod p)　　‥‥《く》
《く》左辺の因子のうち、(2^m) の平方である (2^m)² は、もちろん p の平方剰余。例えば (2^m)² を R とすると、x² ≡ R (mod p) には、当たり前だが x = (2^m) という解がある（下記の具体例参照）。つまり《く》をこう書くことができる:
　　R は p の平方剰余、そして 2R ≡ −1 (mod p)　　‥‥《け》

《け》左辺において、もし 2 が p の平方剰余なら、積の性質〔ア〕から、《け》左辺の 2R も p の平方剰余、それと合同な右辺の −1 も p の平方剰余。第一・第二補充法則から（表参照）、p が 8k+1 型のときに限って、この状況（2, −1 がどちらも平方剰余）があり得る。一方、もし 2 が p の非剰余なら、積の性質〔イ〕から 2R も p の非剰余、それと合同な右辺の −1 も p の非剰余。再び第一・第二補充法則を使うと、p が 8k+3 型のときに限って、この状況（2, −1 がどちらも非剰余）があり得る。

〔具体例〕　m = 3, n = 2m+1 = 7 の場合、A₇ = 2⁷ + 1 = 129 は、素数 p = 43 で割り切れる。このとき《く》に当たる式は:
　　2(2³)² ≡ −1 (mod 43)
ここで R = (2³)² = 8² が 43 の平方剰余であるというのは、x² ≡ 8² (mod 43) に解があるという意味だが、実際、見たまんま x = 8 という解がある。《け》に当たる式は:
　　2R ≡ −1 (mod 43)
43 は 8k+3 型の素数なので、第二補充法則から 2 は 43 の非剰余。43 は 4k+3 型ともいえるので、第一補充法則から −1 も 43 の非剰余。つまり上の式は「非剰余である 2 に、平方剰余 R を掛けたら、非剰余 −1 になる」という意味を持ち、積の性質〔イ〕の通りになっている。

【4】　以上を要約すると、数列 A_n = 2ⁿ + 1 の偶数番目の項の素因数は 4k+1 型（言い換えれば 8k+1 型または 8k+5 型）に限られ、奇数番目の項の素因数は 8k+1 型または 8k+3 型に限られる。すなわち 8 で割って余りが 1, 3, or 5 の素数だけが、この数列のどれかの項の約数となる可能性を持つ: そのうち 8k+3 型は奇数番目の項限定、8k+5 型は偶数番目の項限定だけど、8k+1 型は、理論上どっちにもなり得る。一方、8 で割って余りが 7 の素数（8k+7型）は、この数列のどの項の約数になる可能性もない。

これが「約数 7 がどこにも現れない」という現象の理由。同じ理由から 23 も、この数列の約数としては一度も出番がない。

7 が「アンラッキー」という構造はこれでクリアーになった！

それでは 8k+7 型以外の素数なら、必ずこの数列の約数としてどこかで出番があるのだろうか？

数列 A を素数 p で割った余りは、大ざっぱな話として、遅くとも p 項目にはループする。ループが始まる前にどこかで余りが 0 にならないことには、無限ループの性質上、永遠にどの項も p で割り切れない。この「特定の数で割った余りは、有限の範囲でループ」という縛りは、この数列において、かなり厳しい制約といえるだろう。

2, 4, 8, 16, … という数列 B は、文字通り指数関数的にものすごい勢いで大きくなり、10項目にはもう1000を超えてしまう。それに 1 を足した数列 A も、増加スピードは同様。他方、素数は 1000 以下だけでも 168 個（2 を除いても 167 個）もあり、比較で言うと「存在密度」が高い。約4分の1に当たる 8k+7 型には出番がないとはいえ、「出番があるかもしれない素数」は、依然として多い。その全部が、100項やそこらまでで、因数として全種類出現する…というのは、何となく無理なような気もする。8k+1 型、8k+3 型、8k+5 型素数のうち、実際に因数として出番があるのは、10%くらいの割合では…。それとも、この「選抜」はもっと甘くて、それらの素数の50%くらいは、どこかで因数として出現するのだろうか。あるいは、ひょっとして…実は、100%出現するのだろうか？

30 以下の（奇数の）素数に話を限った場合:
　　p = 3 は第1項で出現　2¹ + 1 = 3 は 3 の倍数
　　p = 5 は第2項で出現　2² + 1 = 5 は 5 の倍数
　　p = 7 は出現しない（8k+7型）
　　p = 11 は第5項で出現　2⁵ + 1 = 33 は 11 の倍数
　　p = 13 は第6項で出現　2⁶ + 1 = 65 は 13 の倍数
　　p = 17 は第4項で出現　2⁴ + 1 = 17 は 17 の倍数
　　p = 19 は第9項で出現　2⁹ + 1 = 513 は 19 の倍数
　　p = 23 は出現しない（8k+7型）
　　p = 29 は第14項で出現　2¹⁴ + 1 = 16385 は 29 の倍数
ここまでは 8k+7 型以外、因数として100%出現しているが、果たしてこのまま出現率100%が維持されるのか…。

あなたの勘では…？

（続く）

2023-03-10　アンラッキー・セブン⑤（最終回）　73と89は超アンラッキー

#数論　#第二補充法則　#フェルマー風の数列

2, 4, 8, 16, 32, … という倍々になる数から、それぞれ 1 を引くと Mersenne 数 1, 3, 7, 15, 31, … になる。1 を引く代わりに、1 を足すと:
　　3, 5, 9, 17, 33, …

こっちの数の中には、いわゆる Fermat 素数が5個、含まれる（3, 5, 17, 257, 65537）。 N がこの5種類の数のどれかなら、定規とコンパスだけを使って正 N 角形を作図できる。特に「定規とコンパスだけで正17角形を作図できる」という事実は、玄妙で魅惑的（少年時代の Gauß は、この事実を発見した喜びから、数学者になる決意をしたという）。正7角形・正9角形・正11角形などは駄目なのに、何で正17角形はOKなのか――直観的には不思議な話だ。Mersenne 素数は完全数と関係しているが、Fermat 素数は、作図可能な正多角形と関係している。

果たして 6番目の Fermat 素数は、あるのだろうか？　未解決の問題、未知の領域だ。

V_n = 2ⁿ + 1 のどの項も、決して 7 では割り切れない。7 に限らず、8k+7型の素数（23, 31 など）は、数列 V の項の因数としては、一度も出番がないアンラッキー素数。では8k+1型、8k+3型、8k+5型の素数はどうだろうか？

【1】　n を 1 以上の整数とする。V_n = 2ⁿ + 1 は、決して 8k+7 型素数 p では割り切れない。

この命題については前回既に証明したが、ここでは −2 の平方性を使う別証明を記しておく。

証明　p ≡ 7 (mod 8) のとき、2ⁿ + 1 ≡ 0 つまり 2ⁿ ≡ −1 (mod p) を満たす n がないこと――を示せばいい。n が偶数 2m なら、最後の合同式は (2^m)² ≡ −1 (mod p) を含意するが、これは第一補充法則に反する。n が奇数 2m+1 なら 2^2m+1 ≡ −1 (mod p) だが、その両辺を 2 倍すると:
　　(2^m+1)² ≡ −2 (mod p)
この合同式も不可能。なぜなら −2 が法 p の平方剰余であることは、p ≡ 1 or 3 (mod 8) と同値。□

上記 −2 の平方性についての議論によると、V の奇数番目の項が 8k+1 型素数で割り切れることは、不可能ではない。だが、比較的珍しい現象のようだ。1000以下の8k+1型素数は37個あるが、そのうち V の奇数番目の項の因数になるものは n = 281 と n = 617 の2個しかない。OEIS で検索したところ、これは https://oeis.org/A163184 [Primes of the form 8k + 1 dividing 2^j + 1 for some odd j.] に当たる。最小の例は:
　　V₃₅ = 2³⁵ + 1 = 343 5973 8369 = 3 × 11 × 43 × 281 × 86171
この分解は、既に Lucas も記述している。2番目の例は:
　　V₇₇ = 2⁷⁷ + 1 = 1511垓 1572京 7451兆 8286 4683 8273 = 3 × 43 × 617 × 683 × 78233 × 35532364099
この第77項は、8k+1型の素因数を2重に含んでいる: 78233 もこのタイプだ。

ここで「最小・2番目」というのは、素因数の大きさによるソート。項の番号の大小でソートした場合、最小例は:
　　V₂₉ = 2²⁹ + 1 = 5 3687 0913 = 3 × 59 × 3033169
2番目は:
　　V₃₃ = 2³³ + 1 = 85 8993 4593 = 3 × 67 × 683 × 20857
上記の V₃₅ は、このソートでは3番目に当たる。第29・33・35・37・41・45・47・49・51項が、8k+1型の素因数を持ち、第51項はそれを2重に持つ。

Lucas は第60項までを完全に分解し、第61項が因子3を持つことも承知していたが、
　　V₆₁ = 2⁶¹ + 1 = 3 × 76京 8614兆 3364 0456 4651
の18桁の余因子がどう分解されるのか、決定できなかったようだ。この18桁の数は実は素数だが、当時の環境では、確定判断は困難だったのだろう。それでもとにかく、Dans la série de FERMAT, les termes V_n ne contiennent aucun nombre premier de la forme 8q + 7. と正しく結論している（訳: フェルマーの数列において、項 V_n は 8q+7 の形の素因数を一切含まない）。

【2】　この探検を完結させるため、次の性質が役に立つ。

位数の半分についての定理　3 以上の素数 p が与えられたとする。2^x ≡ 1 (mod p) を満たす最小の正の整数 x = e を「2 の位数」と呼ぶ。もし e が偶数なら（そしてそのときに限って）、
　　2^x ≡ −1 (mod p)　　‥‥《さ》
を満たす正の整数 x が存在する。そのような最小の x は「2 の位数」の半分 e/2 に等しい。より一般的に、正の整数 x が e/2 の任意の奇数倍（1倍も含む）のとき《さ》は成り立ち、x がそれ以外の正の整数のとき《さ》は成り立たない。

注意　「2 の位数」は必ず存在する。なぜなら 2^x ≡ 1 (mod p) には必ず一つは解がある（事実、Fermat の小定理から、x = p − 1 は、この合同式を満たす）。位数の性質から e は p − 1 の約数（p − 1 自身の可能性もある）。

〔例1〕　p = 13 を法として「2 の位数」は e = 12。実際 2¹² = 4096 ≡ 1 (mod 13) だが、12 より小さい正の指数はこの性質を持たない: 2¹, 2², 2³, …, 2¹¹ は ≢ 1 (mod 13)。このとき e/2 = 6 は 2⁶ ≡ −1 (mod 13) を満たす。実際 2⁶ = 64 は 13 の倍数より 1 小さい。2⁶ ≡ −1 なので、指数を例えば 3 倍した 2¹⁸ も ≡ −1 になる。なぜなら 2¹⁸ = (2⁶)³ ≡ (−1)³ だから。

定理の証明　しばらくの間 e は偶数だと仮定する。まず、正の整数 x = e/2 が《さ》の一つの解であることを示す。2^e/2 を y とすると、定理の前提により y² = 2^e ≡ 1 (mod p) が成り立つが、この2次方程式の解は明らかに y ≡ 1 or −1 で、それ以外の可能性はない（なぜなら素数を法とする世界では、2次方程式の解は2種類以下）。けれど、2^x ≡ 1 を満たす最小の正の整数 x は e なのだから、2^e/2 ≡ 1 は不可能、つまり y ≡ 1 は不可能。従って y ≡ −1 つまり 2^e/2 ≡ −1 でなければならない。これは x = e/2 が《さ》の一つの解であることを意味する。

〔注〕　この証明では合同記号 ≡ は全て mod p。簡潔化のため mod の表記を省略する。

すなわち e/2 を f とすると 2^f ≡ −1 だが、より一般的に x が f の任意の（正の）奇数倍のときにも、明らかに《さ》が成り立つ。例えば x = 3f なら 2^3f = (2^f)³ ≡ (−1)³ ≡ −1。この「3」を任意の正の奇数に置き換えても、全く同様。

一方、もし x = h が f より小さい正の整数なら、決して《さ》は成り立たない。なぜなら 2^h ≡ −1 は 2^2h ≡ 1 を含意するが、これは 2 の位数が e であるという前提に反する（h が f = e/2 より小さいなら 2h は e より小さい）。従って、《さ》を満たす最小の正の整数 x は f。

より一般的に、x が f の奇数倍以外の場合には、《さ》は成り立たない――われわれは、背理法によって、それを示す: f の奇数倍以外の変な正の整数 x = h が《さ》を成り立たせると仮定して、矛盾を導こう。

指数 x が f = e/2 の偶数倍（つまり e の整数倍）の場合、《さ》が成り立たないことは明白。例えば x = 5e なら 2^5e = (2^e)⁵ ≡ 1⁵ ≡ 1 となり、《さ》は不成立。従って、もしも f の奇数倍以外の正の整数 x = h が《さ》を満たすなら、その h は f の奇数倍でも偶数倍でもなく、従って h は f で割り切れない。そこで h を f で割った整数商を q、余りを r とすると:
　　h = fq + r　ただし 0 < r < f = e/2　　‥‥《し》
背理法の仮定 2^h ≡ −1 と等式《し》から:
　　−1 ≡ 2^h ≡ 2^fq + r ≡ (2^fq)(2^r) ≡ (±1)(2^r)　　‥‥《す》
ここで 2^fq は q が偶数なら ≡ 1 で q が奇数なら ≡ −1（なぜなら 2^f ≡ −1）。前者の場合、《す》は 2^r ≡ −1 を含意するが、これは「《さ》を満たす最小の正の整数 x は f だ」という事実と矛盾する。後者の場合、《す》は 2^r ≡ 1 を含意するが、これは「2 の位数が e だ」という前提と矛盾する。

結論として、e が偶数の場合、正の整数 x が f = e/2 の奇数倍なら《さ》が成立し、正の整数 x がそれ以外の値なら《さ》は成立しない。

最後に、e が奇数の場合、e/2 の奇数倍は整数ですらないので、《さ》には整数解がない。実際、x が e の倍数のとき《さ》が成り立たないことは明白（e が偶数の場合と全く同じ）。もしもそれ以外の正の整数 x = h が《さ》を満たすなら、2^2h = (2^h)² ≡ (−1)² ≡ 1 となるが、この h は e の倍数ではないので 2h も e の倍数ではない――これは位数の性質に反する。□

この「位数の半分についての定理」を使うことで、Fermat 風の数列について、幾つかの基本事実を確立できる。先に結論を要約すると: 8k+7型の素数は全てアンラッキー（既述）、8k+5型と8k+3型の素数は全てラッキー、そして8k+1型の素数はケースバイケース。

【3】　8k+5型の任意の素数 p は V_n = 2ⁿ + 1 の無限個の項を割り切る。この型の素因数の出現位置は、偶数番目の項に限られる。

証明　V_n = 2ⁿ + 1 ≡ 0 つまり 2ⁿ ≡ −1 (mod p) を満たす n が、少なくとも一つ存在することを示す。n = (p−1)/2 = (8k+5−1)/2 = 4k+2 のとき、この最後の合同式は…
　　2^(p−1)/2 ≡ −1 (mod p)
…となるが、それが成り立つことは Euler の基準と第二補充法則から明らか。

〔例2〕　p = 13 は《さ》を満たす。実際、2⁶ = 64 は 13 の倍数より 1 小さい。言い換えれば V₆ = 65 は p = 13 で割り切れる。

項の番号 (p−1)/2 は、必ずしも新出位置ではない。例えば p = 109 も8k+5型素数だが、この場合、確かに V_(p−1)/2 = V₅₄ も p で割り切れるが、項の番号を3分の1にした次の数が既に p で割り切れる（こちらが新出位置）:
　　V₁₈ = 262145 = 5 × 13 × 37 × 109

p が8k+5型の場合、2^x ≡ −1 (mod p) を満たす正の整数 x は、偶数でなければならない。

〔理由〕　「位数の半分についての定理」から、x がこの合同式を満たすことは、x が 2 の位数の半分 f = e/2 の奇数倍であることと同値。x = (p−1)/2 = 4k+2 という偶数は、そのような x の一つだから（言い換えれば f の奇数倍が偶数になるケースが確認されているのだから）、f は偶数で、その奇数倍は偶数。

正の整数 n がその偶数 f の奇数倍のとき、V_n は p で割り切れる: 特に V_f において p は新出素数、V_cf において p は既出素数（c = 3, 5, 7, 9, …）。それら以外の項では、V_n は p で割り切れない。□

〔例3〕　p = 109 を法として 2 の位数は e = 36。これは「2³⁶ を 109 で割ると 1 余る」「2¹ ～ 2³⁵ の35種類の数は、109 で割ると 1 余るという性質を持たない」という意味（言い換えると、109 で割り切れる最小の Mersenne 数は M₃₆ である）。従って Fermat 風の数列 V_n においては、f = e/2 = 18 が 109 の新出位置となり、それより後ろの 18 の奇数倍の番号の項で、109 は既出素数となる:
　　V₁₈ = 2¹⁸ + 1 = 5 × 13 × 37 × 109
　　V_18×3 = 2⁵⁴ + 1 = 5 × 13 × 37 × 109 × 246241 × 279073
　　V_18×5 = 2⁹⁰ + 1 = 5 × 13 × 37 × 41 × 61 × 109 × 181 × 1321 × 54001 × 29247661

【4】　8k+3型の任意の素数 p は V_n = 2ⁿ + 1 の無限個の項を割り切る。この型の素因数の出現位置は、奇数番目の項に限られる。

証明　【3】と同様。(p−1)/2 = (8k+3−1)/2 = 4k+1 という奇数は、第二補充法則から次の関係を満たす:
　　2^(p−1)/2 ≡ −1 (mod p)
　　つまり　2^(p−1)/2 + 1 ≡ 0 (mod p)
要するに V_(p−1)/2 という項は p で割り切れる。この項の番号 (p−1)/2 = 4k+1 は奇数だが、それは新出位置 f の奇数倍なので、f は奇数。n が f の任意の奇数倍のとき（そのような n はどれも奇数）、V_n は p で割り切れる。それ以外の項 V_n は p で割り切れない。□

具体例は、次の表の素因数 3 や 11。●印は夏素数（8k+3型）で、奇数番目の項に現れる。★印は秋素数（8k+5型）で、偶数番目の項に現れる。冬素数（8k+7型）は決して現れない。▼印の素因数は、春素数（8k+1型）――この表の範囲では偶数番目の項にだけ現れているが、【1】で触れたように、奇数番目の項に現れるケースもある。

V_n = 2ⁿ + 1 の各項の素因数／丸かっこは新出位置

n	2n	2n + 1	素因数分解
1	2	3	(3●)
2	4	5	(5★)
3	8	9	3● × 3●
4	16	17	(17▼)
5	32	33	3● × (11●)
6	64	65	5★ × (13★)
7	128	129	3● × (43●)
8	256	257	(257▼)
9	512	513	3● × 3● × 3● × (19●)
10	1024	1025	5★ × 5★ × (41)
11	2048	2049	3● × (683●)
12	4096	4097	17▼ × (241▼)
13	8192	8193	3● × (2731●)
14	16384	16385	5★ × (29★) × (113▼)
15	32768	32769	3● × 3● × 11● × (331●)
16	65536	65537	(65537▼)

【5】　8k+1型素数 p は、法 p での 2 の位数 e が偶数なら、Fermat 風の数列の無限個の項を割り切る。出現位置は、f = e/2 の任意の奇数倍の番号の項: f が偶数なら（言い換えると e が 4 の倍数なら）偶数番目の項に限られ、奇数なら（言い換えると e が 4 で割って 2 余る偶数なら）奇数番目の項に限られる。一方、8k+1型素数 p を法とする 2 の位数 e が奇数なら、p はこの数列の項の因数になることはない。

この事実そのものは「位数の半分についての定理」から明らかだが、8k+1型の素因数の挙動の本質は「位数」という不透明な現象の内側に隠されていて、見通すことができない（少なくとも古典的な数論の範囲からは）。

数値的な観察は、次の通り。

1000以下の168個の素数のうち、8k+1型のものは37個。そのうち、28個は V_n の偶数番目の項の因数となり、2個は V_n の奇数番目の項の因数となり、7個は V_n のどの項の因数にもならない。8k+7型素数は全てアンラッキーなのだから、仕方がないとあきらめもつくが（？）、8k+1型素数の多くは V_n の因数として出番がある。8k+1型なのに一度も出番がない素数は、超アンラッキーといえよう。1000以下の7個の超アンラッキー素数は:
　　73, 89, 233, 337, 601, 881, 937

超アンラッキー素数の本質的意味は、はっきりしない。OEIS で検索しても、何もヒットしなかった。73, 89, 233, 937 は https://oeis.org/A152308 [Primes p such that the multiplicative order of 2 modulo p is (p-1)/8.] の最初の4項だが、この数列は「超アンラッキー素数」の部分列というわけでもない。

上記の7個の素数は、「それを法として 2 の四乗根と −2 の四乗根が存在する」という特徴を持つ。例えば:
　　18⁴ = 104976 ≡ 2 (mod 73)
　　31⁴ = 923521 ≡ −2 (mod 73)
これは超アンラッキー素数の特徴付けではないが、ちょっぴり素敵。特に mod 89 では ±2 が小さな四乗根を持ち、かわいい:
　　5⁴ = 625 = 623 + 2 = 89 × 7 + 2 ≡ 2 (mod 89)
　　7⁴ = 2401 = 2403 − 2 = 89 × 27 − 2 ≡ −2 (mod 89)

捜索範囲を広げると、1万以下の1229個の素数の中で、8k+1型は295個。そのうち200個が V_n の偶数番目の項の因数、53個が奇数番目の項の因数となる。どちらにもならない超アンラッキー素数は、42個。

〔追記〕　8k+1型の素数のうち、超アンラッキーなものの密度は約6分の1のようだ。1億までの範囲で、8k+1型素数は143万9970個、そのうち239953個が超アンラッキー（16.6637%）。10億までの範囲で1271万1220個中、2119205個（16.6719%）。

【6】　アンラッキー素数（8k+1型の一部と8k+7型の全部）の特徴付けは、「法 p での 2 の位数が奇数であるような素数 p」。
　　7, 23, 31, 47, 71, 73*, 79, 89*, 103, 127, …　（*は超アンラッキー）
これは https://oeis.org/A014663 [Primes p such that multiplicative order of 2 modulo p is odd.] であり、現在でも関連する研究が行われているようだ。より直接的には https://oeis.org/A072936 [Primes p that do not divide 2^x+1 for any x>=1.] に当たる。

アンラッキー素数の集合には、「四乗剰余の第二補充法則」――つまり x⁴ ≡ 2 が解を持つような素数の法――との類似性が見られる。https://oeis.org/A040098 [Primes p such that x^4 = 2 has a solution mod p.]

法がアンラッキー素数であることは、2 が四乗剰余になる必要条件ではないが、十分条件になるのかもしれない。8k+7型素数に関しては、全てアンラッキー、そしてそれを法として 2 は四乗剰余なので、二つの現象は同値。上記 A040098 のコメントによると、8k+1型素数 p に関しては、それを法として 2 が四乗剰余になることは、p が x² + 64y² の形を持つことと同値だという。実際、上記のアンラッキー素数について 73 = 3² + 64⋅1², 89 = 5² + 64⋅1² などと書ける。でも、これは「超アンラッキー素数であること」より弱い条件だ。例えば、8k+1型素数のうち p = 113, 257, 281, 353, 577 を法として 2 は四乗剰余だが、これらの p は超アンラッキーではない（特に 257 は、アンラッキーどころか V₈ の値そのもの）。

〔例4〕　113 は 7² + 64⋅1² に等しいので、上記の二次形式を持つ。そして 27⁴ ≡ 2 (mod 113)。一方、mod 113 での 2 の位数は e = 28 なので、V の e/2 = 14 番目の項、またはその奇数分の1番目の項が 113 の新出位置。第 14/7 項 2² + 1 = 5 は明らかに条件を満たさないので、113 の新出位置は V₁₄ = 2¹⁴ + 1 = 16385。実際 16385 = 5 × 29 × 113。要するに mod 113 で 2 は四乗根を持つが、113 はアンラッキーではない。

〔例5〕　257 は 1² + 64⋅2² に等しいので、上記の二次形式を持つ。そして 35⁴ ≡ 2 (mod 257)。一方 V₈ = 2⁸ + 1 = 257 は、もちろんアンラッキーではない。Fermat 素数という超レアな存在だ。

〔例6〕　281 は 5² + 64⋅2² に等しい。そして 46⁴ ≡ 2 (mod 281)。一方 281 は V₃₅ の約数（【1】参照）。アンラッキーどころか「奇数番目の項を割る8k+1型」という珍しい素数だ。理論上では V₅ = 33 または V₇ = 129 の因数になり得るが、この二つの項は明らかに小さ過ぎる。従って、第35項でこの素因数は新出。

Fermat 風の数列（P = 3, Q = 2 の同伴 Lucas 数列）は、Mersenne 数列の相棒に当たる。関連するアンラッキー素数のうち、8k+7型（常にアンラッキー）については完全に古典数論の範囲だった。8k+1型の素因数の挙動は不透明だが、表面的な結論としては、要するに 2 の位数が偶数ならラッキー、奇数ならアンラッキー。

この数列におけるアンラッキー素数については、これで一応結論が出たが、この話題との関連では、遊ぶ場所がいっぱいある！　特殊的には、Mersenne 数の話題のアナロジーとして、「Fermat 数の素数判定」と「合成数の Fermat 数の分解」という観光名所がある。一般的には、Lucas 数列という広くて渋い話題がある。Lucas 自身は、他の種類の Lucas 数列におけるアンラッキー素数についても記していて、それも興味深い話題だ。「アラベスク」の一般バージョンは、鳥肌ものの美しさだろう。「Fermat の小定理の Lucas 方向の一般化」は、素晴らしい冒険コースに違いない！

2023-03-13　1000個のドアと1000人のいたずらっ子　有名（？）パズルのジョーク

超巨大ビルの長い廊下に、1号室から1000号室までの、1000個のドアが並んでいる。ドアは初期状態では全部閉まっているが、鍵はかかっていないので自由に開け閉めできる。

そこにゼッケン1番から1000番までの、1000人のいたずらっ子がやって来た！

どのいたずらっ子も、「自分のゼッケン番号の倍数の番号の部屋」にいたずらをする。例えば2番の子は、2号室・4号室・6号室…にいたずらをし、3番の子は、3号室・6号室・9号室…にいたずらをする。

いたずらの内容は、たわいもない。「その部屋のドアが閉まっていたら、勝手に開けて、そのまま放置する。ドアが開いた状態になっていたら、勝手に閉めてしまう！」という内容。要するに、開いてたら閉め、閉まってたら開け、開閉状態を逆にする。

〔注〕　ドアは自動的に開閉することはなく、いたずらっ子の手動操作によってのみ、開閉のステータスが変わるものとする。余計な曖昧さをなくすため、「複数の子が、“同時に”同じドアにいたずらをしようとして干渉する」といった、ややこしい事態は発生しないものとしよう（同じドアが複数回いたずらされる場合、“同時に”ではなく、ある子のいたずらが終わってから、別のタイミングで別の子がそのドアにいたずらをする）。

さて、1000人の子が上記のいたずらを完了した後で、「最終的に開いているドアの総数は、今月の日数より多いか少ないか」で賭けをしたい。賭けの参加費は100ユーロ、正解したら10倍になって返ってくるが、不正解なら没収だぞ～（笑）。あなたなら、どっちに賭けますか？

〔コメント〕　素朴な直観だと、ドアを勝手に開けるいたずらと、勝手に閉めるいたずらは半々の確率で発生しそうにも思える。だとすると、500個くらいのドアが開いた状態になりそうだが（？）、いかがなものか。

2023-03-14　「1000人のいたずらっ子」パズルの答え　エレガントな解法ｗ

#数論　#約数の個数

1番から1000番までの1000人のいたずらっ子が、それぞれ1番から1000番までの1000個のドア（初期状態では全部閉まっている）にいたずらをして、自分の倍数の番号のドアに対して「開いていたら閉める」「閉まっていたら開ける」という行為をした場合、最終結果はどうなるか。

→　パズルの全文（賭けに勝って1000ユーロ、ゲットだぜ！ｗ）

各ドアの最終状態は、いたずらっ子の訪問順序には依存せず、合計何人のいたずらっ子がそのドアをいじるかという回数にのみ依存する。一人目がいたずらして開けた後で二人目がいたずらして閉めると元に戻るので、いたずらっ子たちの合計訪問回数が偶数回なら、そのドアは最終的に閉まっているし、奇数回ならドアは最終的に開いている。

例えば15号室のドアは、いたずらっ子1、3、5、15の4人にいたずらされるので、最終的には閉じている。36号室のドアは、いたずらっ子1、2、3、4、6、9、12、18、36の9人にいたずらされるので、最終的には開いている。一般に、N番のドアは、Nの約数の数だけ、いたずらされる。

そこで教科書的には「約数の個数」の議論になるわけだが――その方法でもそれほど面倒でもないのだが――、ちょっと考えると「伴侶論法」が使え、約数の個数の議論を省略できる！　例えば、いたずらっ子 a = 3 が15号室にいたずらするケースでは、ab = 15 を満たすいたずらっ子 b = 5 も同じドアにいたずらする。ab = N の関係の二人のいたずらっ子 a, b をその（N号室の）ドアに関して「恋人」と呼ぶと、ほとんどの場合、誰かが開けたドアは、その子の恋人が閉じるので、最終的にドアは閉じている！

例外は a = b のケースつまり ab = a² = N のケース。この場合、いたずらっ子 a の恋人は a 自身なので、「ドアを開けるハンドラーだけが存在して、閉じるハンドラーが存在しない」と解釈できる――その根拠は、以下の通り。

結果は訪問順序に依存しないのだから、「恋人が別人であるような、通常のカップル」が先に訪問を済ませると仮定していい。そして「通常のカップル」はトータルでは何もしないのと同じなので、最初から存在しないものと解釈して差し支えない。要するに「例外のいたずらっ子 a だけが a² 号室のドアを開ける。それ以外には何も起きない」と考えても、結果は同じこと。

〔補足〕　ある部屋の例外ケースに関わるいたずらっ子（例えば36号室に対する6）でも、別の部屋（例えば60号室）にいたずらするときは、別人の恋人が存在して（この例では恋人は10）、通常カップルの行動を取る。

〔参考〕　教科書的には「平方数は奇数個の約数を持つ。それ以外の正の整数は偶数個の約数を持つ」。

結局、問題は、1 から 1000 の中に a² = N の形の数が何個あるか？に帰着される。それが例外の正体だッ！

答えは 1² = 1 から 31² = 961 までの31個で、32² = 1024 は範囲外。従って、最終的に開いているドアは31個。

31² = 961 は別に難しい計算でもないが、ちょっと別の角度から: √10 = 3.16… と円周率 3.14… は、近似的に等しい。面倒なので 3.14 で代用すると:
　　√1000 = √10 × √100 ≈ 3.14 × 10 = 31.4
　　ゆえに 31² < (31.4)² ≈ 1000 < 32²
となる。たまたまだが、円周率の日にちなんだネタになった！　もっと正しい値…
　　√10 = 3.16227766…
…の語呂合わせは「三つ色で、ふらふら並ぶなムカムカ」。意味は、三つの色（種類）の数字が次々とペアで並んでいること（2-2, 7-7, 6-6）について、「ふらふら並ぶなムカムカ」と腹を立てている（らしいｗ）。ずいぶん怒りっぽい性格の人である。

〔検算〕　2⁵ = 32 と 2¹⁰ = 1024 については、いざとなれば倍々にしながら指折り数えられる。32² = 1024 ってことは、1024 の平方根は32 ってこと。上から押さえても、1000 の平方根は32よりちょっと小さいはず…。上記の考察とつじつまが合う！

ここまでは「まじめなパズル」。

「最終的に開いているドアの総数は、今月の日数より多いか少ないか」で賭けをしたい、という付け足しは…。

今月（2023年3月）の日数は31なので、それより「多い」に賭けても「少ない」に賭けても、あなたは賭けに負けてしまう――というオチのジョーク（笑）。

お持ち帰り　√10 = 3.1622776601… は π = 3.1415926535… にまぁまぁ近い（ミツイロの後ろは「ふらふら並ぶなムカムカおーい」、3.14 の後ろは「異国に婿さんゴー」）。1000 の平方根は 10π に近く、1000以下の正の整数の中には平方数が31個ある。31って、和歌の文字数。んでもって 1000 以下の素数は168個、いろはと読める。どっちも和風？

危ない賭けのネタでは「デスノートをさがして」というパズル（寿命が縮むｗ）もある。

2023-03-24　完全数と忍者数　メルセンヌ数・再訪

#数論　#メルセンヌ数　#べき和　#奇数の立方和

完全数――それは「自分自身以外の約数」の和が、自分自身に等しい数（例えば 28 = 1 + 2 + 4 + 7 + 14）。第一印象、地味な話題に思える。最小の完全数は 6 = 1 + 2 + 3。

一方、二番目・三番目・四番目…の完全数は、次のように、奇数の3乗を順々に2個・4個・8個、足した和に等しい。

• 28 = 1³ + 3³
• 496 = 1³ + 3³ + 5³ + 7³
• 8128 = 1³ + 3³ + 5³ + … + 15³
• ⋮

この性質は一見して美しく、意表を突く。一体「完全数」と「奇数の立方和」に、どういう関連性が？

謎を解明するため、「奇数の3乗和」ってどういう値なのか、調べてみよう。普通の3乗和…

• 1³ + 2³ + 3³ + … + n³ = n²(n + 1)²/4　　　「全」

…の両辺を 2³ 倍つまり 8 倍すると「偶数の3乗和」になる:

1. 2³⋅1³ + 2³⋅2³ + 2³⋅3³ + … + 2³⋅n³ = 2³n²(n + 1)²/4
2. 2³ + 4³ + 6³ + … + (2n)³ = (2n)²(2n + 2)²/8

a = 2n と置けば:

1. 2³ + 4³ + 6³ + … + a³ = a²(a + 2)²/8　　　「偶」

「全」から「偶」を引き算すれば、ご注文の「奇数の3乗和」。以下で3乗される最後の数 b は奇数。従って 後半の「偶数の3乗和」では、最後の項は (b − 1)³ だ。計算上、「偶」の a に偶数 b−1 を代入することになる。

1. 1³ + 3³ + 5³ + … + b³
2. = [1³ + 2³ + 3³ + 4³ + 5³ + 6³ + … + b³] − [2³ + 4³ + 6³ + … + (b − 1)³]　　
3. = [b²(b + 1)²/4] − [(b − 1)²(b + 1)²/8]　　←「全」と「偶」から
4. = (b + 1)² × [2b² − (b − 1)²]/8　　← (b + 1)² をくくり出してから通分
5. = (b + 1)²(b² + 2b − 1)/8

ここからどう進めるか…。多少の試行錯誤の結果、以下の道が見つかる。

1. = (b + 1)²[(b + 1)² − 2]/8

A = b+1 とすると、上の式は A²(A² − 2)/8 というシンプルな形になる――分母の 8 がちょっと邪魔くさいが、次のようにすると、これも除去できる。
　　A²(A² − 2)/8 = A²/4 × (A² − 2)/2 = A²/4 × (A²/2 − 1)
ここで c = A/2 と置くと、c² = A²/4 で 2c² = A²/2 なので、こうなる。
　　A²(A² − 2)/8 = c²(2c² − 1)　　← 邪魔な分母が消えてくれたッ！
この c = A/2 = (b+1)/2 とは、3乗される最後の奇数 b の半分（端数切り上げ）であり、足し算される立方数の個数に他ならない。つまり――

定理1（奇数の立方和）　最初の c 個の奇数の立方の和は c²(2c² − 1) に等しい。言い換えれば、2c 以下の正の奇数をそれぞれ3乗して足し合わせると、c²(2c² − 1) になる。

〔例1〕　c = 3, 2c = 6 の場合。1³ + 3³ + 5³ = 1 + 27 + 125 = 153:
　　c²(c² − 1) = 3²(2⋅3² − 1) = 9 × 17 = 153　← ちゃんと和と一致

〔例2〕　c = 4, 2c = 8 の場合。1³ + 3³ + 5³ + 7³ = 1 + 27 + 125 + 343 = 496:
　　c²(c² − 1) = 4²(2⋅4² − 1) = 16 × 31 = 496　← ちゃんと和と一致

2 の p 乗から 1 を引いた数 2^p − 1 をメルセンヌ数と呼び、M_p で表す（p は正の整数）。メルセンヌ数は素数になることも、ならないこともある。素数のメルセンヌ数をメルセンヌ素数という。

メルセンヌ数 M_p = 2^p − 1 が与えられたとき、整数 2^p−1 を、（対応する）忍者数と呼ぶことにしよう。文字列としては、どちらも「2」「p」「−」「1」の4文字だが、メルセンヌ数
　　2^p − 1
において 2^p の背後にいる大きな −1 が、忍者数
　　2^p−1
においては、小さくなって指数部分に忍び込んでいる。この二つの違いは、ちょっと紛らわしい。

メルセンヌ数と完全数に関連して、オイラーが完成させた次の定理がある。

定理2（偶数の完全数の特徴付け）　メルセンヌ数 M_p = 2^p − 1 が素数なら、忍者数とメルセンヌ数の積
　　2^p−1 M_p = 2^p−1(2^p − 1)
は完全数。逆に N が偶数の完全数なら、N は上記の形でなければならない。

ここで p は、一般論としては「任意の正の整数」だが、実は M_p が素数になるためには p が素数であることが必要。従って、メルセンヌ素数――あるいは「メルセンヌ素数になる可能性のある数」――に話を絞る場合、p を素数に限定して構わない。最初の素数 p = 2 に対して、M_p = M₂ = 3 はメルセンヌ素数。従って、次の数が第一の完全数:
　　2²⁻¹ M₂ = 2 × 3 = 6
同様に M₃ = 7 はメルセンヌ素数なんで、次の数が第二の完全数:
　　2³⁻¹ M₃ = 4 × 7 = 28

今 p を 3 以上の素数とすると、忍者数 2^p−1 は 2 の偶数乗。忍者数の指数を p−1 = 2m とすると（m は正の整数。p−1 は偶数なのでこの形を持つ）:
　　2^p−1 = 2^2m = (2^m)²
　　2^p = 2 × 2^p−1 = 2(2^m)²
ここで c = 2^m と置くと、定理2の「忍者・メルセンヌ積」をこう表現できる:
　　2^p−1 M_p = 2^p−1(2^p − 1) = c²(2c² − 1)
これは定理1の「奇数の立方和」に他ならない！

整理すると:

定理3（偶数の完全数と奇数の立方和の関係）　最初の c = 2^(p−1)/2 個の奇数の立方和――つまり 2c = 2^(p+1)/2 以下の奇数をそれぞれ3乗して足し合わせた和――は、2^p−1 M_p に等しい。このことは、M_p が素数でも素数でなくても成り立つ。特に、p が 3 以上の素数のとき、
　　N = 2^p−1 M_p = 1³ + 3³ + 5³ + … + (2c−1)³
が完全数かどうかは、M_p が素数かどうかによって決まる。逆に、N が偶数の完全数なら、N = 6 であるか、または N は上記の奇数立方和の形を持つ。

〔例3〕　p = 2, 3, 5, 7 のとき M_p = 3, 7, 31, 127 はメルセンヌ素数、それぞれ最初の4個の完全数 6, 28, 496, 8128 に対応する。第五の完全数は何か。p = 11 はチョコレート・ソフィーなので M₁₁ は素数ではない。p = 13 は第五のメルセンヌ素数 M₁₃ = 2¹³ − 1 = 8191 を与えてくれる。対応する完全数 2¹³⁻¹ × M₁₃ = 4096 × 8191 = 33550336 は次の和に等しい:
　　1³ + 3³ + … + 127³ = 33550336

〔例4〕　p = 11 のとき M₁₁ = 2047 = 23 × 89 はメルセンヌ素数ではないのだから、対応する忍者数 2¹¹⁻¹ = 1024 と M₁₁ の積 2096128 は、完全数ではない。それでも依然として、定理3に基づく次の等式が成り立つ:
　　1³ + 3³ + … + 63³ = 2096128

証明済みの定理1のおかげで、定理2と定理3はほとんど同値。ただし、第一の完全数 6 について、定理2では普通に扱えるが、定理3では例外扱い（p = 2, N = 6 のケースを奇数の立方和で書こうとすると、「最初の 2^1/2 個の奇数の立方」となり、項の数が √2 になってしまい、うまくいかない）。

結局、定理2を証明すれば、定理3も証明したことになる。その証明は――

定理2の証明

自然数 n の全種類の（正の）約数（n 自身を含む）の和を σ(n) で表すことにする。例えば σ(6) = 1 + 2 + 3 + 6 = 12。

定理2の前半の証明　q = M_p = 2^p − 1 がメルセンヌ素数なら N = 2^p−1 q が完全数になる理由は、次の通り。N は、素因数 q を 1 個持つのだから、A = 1 or q で割り切れるし、素因数 2 を p−1 個持つのだから B = 1, 2, 4, 8, …, 2^p−1 のどれでも割り切れる。より一般的に、N は積 AB のどの組み合わせでも割り切れるが、それ以外の自然数では割り切れない。だから N の全種類の約数は、
　　σ(N) = (1 + q)(1 + 2 + 4 + … + 2^p−1)　　★
を展開した各項として過不足なく出現し、全種類の約数（N 自身を含む）の和は、上記の積に等しい。ところが:
　　1 + q = 1 + (2^p − 1) = 2^p　　なぜなら定義により q = 2^p − 1
　　1 + 2 + 4 + … + 2^p−1 = 2^p − 1 = q　　※注1
これら二つの事実から、★の積はこうなる:
　　σ(N) = (2^p)(q) = 2(2^p−1 q) = 2N　　なぜなら定義により N = 2^p−1 q
N の「全種類の約数」の和から N 自身を除外して「真約数の和」を求めるなら、結果は 2N − N = N となり、N 自身に等しい。要するに q がメルセンヌ素数なら N は（偶数の）完全数。□

〔※注1〕　左辺の和を X = 1 + 2 + 4 + … + 2^p−1 = 2⁰ + 2¹ + 2² + … + 2^p−1 とすると:
　　2⁰ + (2¹ + 2² + … + 2^p−1 + 2^p) = (2⁰ + 2¹ + 2² + … + 2^p−1) + 2^p
　　2⁰ + 2(2⁰ + 2¹ + … + 2^p−2 + 2^p−1) = (2⁰ + 2¹ + 2² + … + 2^p−1) + 2^p
　　つまり　2⁰ + 2X = X + 2^p
　　従って　X = 2^p − 2⁰ = 2^p − 1
このことの直観的説明として、1 + 2 + 4 + … + 2^p−1 は「二進法で 1 を p−1 個並べた数」。それは「二進法で 1 の後ろに 0 を p−1 個並べた p 桁の数」マイナス 1 に等しい（すなわち 2^p − 1）。

〔補足〕　p = 11 のときの忍者・メルセンヌ積 N = 2¹¹⁻¹(2¹¹ − 1) が完全数になってくれない理由も、同様に説明がつく（例4参照）。その場合 q = 2¹¹ − 1 = 23 × 89 が素数ではない結果として、N は A = 1 or q で割り切れるだけでなく、A = 1, 23, 89, q の4種類の奇数で割り切れるため、約数が多過ぎる。具体的に、この場合の全約数の和は:
　　(1 + 23)(1 + 89)(1 + 2 + 4 + … + 1024) = 24 × 90 × 2047 = 4421520
完全数になるためには、この和が 2N = 4192256 に等しい必要があるが、その目標値と比べ、上の左辺は (23 + 89) × 2047 だけ大き過ぎる。

定理2の後半の証明　逆に N を偶数の完全数としよう。偶数であるからには、素因数 2 を 1 個以上含むので、N = 2^eq と書ける（q は奇数、e は 1 以上の整数）――その書き方でも問題ないけど、代わりに忍者数を使って N = 2^f−1q と書いた方が、見通しがいいようだ（f = e+1 は 2 以上の整数）。まず N が完全数という仮定は σ(N) = 2N を意味するので（※注2）:
　　σ(N) = 2N = 2(2^f−1q) = 2^fq　　‥‥①
従って σ(N) は 2^f で割り切れる。一方、前半の証明と同様に考えると（※注3）:
　　σ(N) = σ(2^f−1q) = (1 + 2 + 4 + … + 2^f−1) σ(q) = (2^f − 1) σ(q)　　‥‥②
この数が 2^f で割り切れるわけだが、右辺の因子のうち、奇数 2^f − 1 は 2 で 1 回も割り切れないので、σ(q) の部分が 2^f で割り切れる。その割り算の商を σ(q)/2^f = x とすると（x は正の整数）:
　　σ(q) = 2^fx　　‥‥③

〔※注2〕　σ(N) は N の「全約数（N 自身を含む）の和」だから、そこから N 自身を除外した「真約数の和」は σ(N) − N。それが N 自身に等しいことが、完全数の条件。この条件は σ(N) − N = N つまり σ(N) = 2N と同値。

〔※注3〕　正確に言うと「2のべき 2^f−1 と奇数 q は互いに素で、σ は乗法的関数なので」。

①と②は等しいので:
　　2^fq = (2^f − 1) σ(q)
そこに③を代入して:
　　2^fq = (2^f − 1) 2^fx
両辺を 2^f で割ると:
　　q = (2^f − 1) x　　‥‥④
従って x は q の約数だが、2^f − 1 は 3 以上なので x = q ということは、あり得ない; つまり q は、q 自身とは異なる約数 x を持つ（従って q ≠ 1）。

④を展開すると q = 2^fx − x つまり q + x = 2^fx。この等式と③を組み合わせると:
　　σ(q) = q + x　　‥‥⑤

⑤の含意は、繊細にして重大だ。 q 自身はもちろん q の約数だが、x は「それとは異なる q の約数」だった。⑤によると q の「全種類の約数」の和は q + x に等しい。すなわち q は q 自身と x という2種類の約数を持ち、それ以外の約数を持たない。この「約数を 2 種類だけ持ち、それ以外のどの数でも割り切れない」という性質から、q は素数。つまり、自分自身と x = 1 でしか割り切れない。

〔注〕　q 自身と 1 は q の約数で、しかも q ≠ 1, q ≠ x であることが分かっている。だから、もしも q の約数 x が 1 と等しくないとしたら、q は少なくとも3種類の約数 q, x, 1 を持つことになり、σ(q) の値は、最低でも q + x + 1 になってしまう。それでは⑤と矛盾するので、x = 1 と考えるしかない。

のみならず、判明した事実 x = 1 と④によって、q はメルセンヌ素数 M_f = 2^f − 1 である！

結局、もし N = 2^f−1q が偶数の完全数なら、必ず N は「忍者数 2^f−1」と「メルセンヌ素数 q = M_f = 2^f − 1」の積。その形以外の偶数の完全数は、無い。□

もっとエレガントな証明法もあるのだろうが、一応これで定理1・定理2が証明されたので、本題の定理3も証明されたことになる: 7 以上のメルセンヌ素数 M_p に対応する完全数は、2^(p+1)/2 以下の奇数の、立方和に等しい。面白いだけで、何の役にも立たない定理かも…。

〔文献〕　定理2の逆の証明では、Sierpiński, Chap. IV, p. 172 を参考にした。

---