メモ（数論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　完全数と忍者数　メルセンヌ数・再訪
• 2024-12-03　完全数と「奇数の3乗和」　1³ + 3³ + 5³ + 7³ などについて
• 2024-12-07　「2乗和・3乗和・4乗和の公式」の簡単な導出法
• 2024-12-08　行列方程式で遊んじゃえっ　（おまけ）
• 2024-12-04　メルセンヌ数 M_p の p の話　遊びをせんとや生まれけむ

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 は（wy ≡ 0 なので）消滅して、《え》は 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²(2c² − 1) = 3²(2⋅3² − 1) = 9 × 17 = 153　← ちゃんと和と一致

〔例2〕　c = 4, 2c = 8 の場合。1³ + 3³ + 5³ + 7³ = 1 + 27 + 125 + 343 = 496:
　　c²(2c² − 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の「奇数の立方和」に他ならない！

定理2の証明を後回しにして、とりあえず上記の観察を整理すると:

定理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 を参考にした。

2024-12-03　完全数と「奇数の3乗和」　1³ + 3³ + 5³ + 7³ などについて

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

28 を割り切る自然数は何か？　28 自身ももちろん 28 を割り切るが（商 1）、自分自身を別にすると 1, 2, 4, 7, 14 の五つの数が 28 を割り切る。この五つの数の和、
　　1 + 2 + 4 + 7 + 14 = 28
は 28 に戻る！　こういう性質を持つ数は、完全数と呼ばれる。他の小さい数で幾つか試してみると、 6 も同じ性質を持つが、
　　10　→　1 + 2 + 5 = 8　ちょっと不足
　　11　→　1　全然不足
　　12　→　1 + 2 + 3 + 4 + 6 = 16　過剰
···などとなって、それ以外の例はなかなか見つからない。「ちょうど自分自身に戻る」ってのは、かなり珍しい性質らしい。

ところで奇数 1, 3, 5, 7, ··· を小さい順に幾つか、それぞれ立方して足し合わせると、完全数になることがある。 28 の例では:
　　1³ + 3³ = 1 + 27 = 28

28 に続く完全数は 496 だが（本文参照）、これも:
　　1³ + 3³ + 5³ + 7³ = 1 + 27 + 125 + 343 = 153 + 343 = 496

「奇数を 3 乗して足し合わせる」ってことと「約数の和が自分自身に等しくなる」ってこと――まるで無関係に思えるその二つが、深く結び付いている（らしい）。この現象は、ちょっと不思議で、好奇心を刺激する。

完全数については、「奇数の立方和」との関係も含めて「完全数と忍者数」に一応記したけど、あらためて考えてみたい。

今回のテーマは、これ。

命題　奇数 1, 3, 5, ··· のうち、最初の c 個をそれぞれ 3 乗して足した和は 2c⁴ − c² に等しい。

〔例1〕　c = 2 のとき 1³ + 3³ = 1 + 27 = 28 だが、
　　2c⁴ − c² = 2(2)⁴ − (2)² = 2⋅16 − 4 = 32 − 4 = 28

〔例2〕　c = 3 のとき 1³ + 3³ + 5³ = 28 + 125 = 153 だが（28 は例1の結果を再利用したもの）、
　　2c⁴ − c² = 2(3)⁴ − (3)² = 2⋅81 − 9 = 162 − 9 = 153

〔例3〕　c = 4 のとき 1³ + 3³ + 5³ + 7³ = 153 + 343 = 496 だが（153 は例2の結果を再利用したもの）、
　　2c⁴ − c² = 2(4)⁴ − (4)² = 2⋅256 − 16 = 512 − 16 = 496

この命題については、既に定理1として工夫して（総和記号を使わずに）証明済みなのだが、今回は総和記号を使って、機械的に片付ける。少々学校的というか教科書くさいやり方になってしまうが、使えるオプションは何でも試してみるのが「遊びの数論」。

【1】　名高い数学者ガウス（現代の数論の基礎を築いた人。18世紀末から19世紀前半にドイツで活躍）の子ども時代のこと。有名な逸話がある。小学校の先生のような人が、足し算の授業（？）で「1 から 100 まで全部足しなさい」と生徒に指示したという。つまり、
　　1 + 2 + 3 + 4 + ··· + 97 + 98 + 99 + 100
を計算しろ、と。それを真面目に計算すれば、確かに足し算の計算練習になることはなるだろうが、もしかするとこの先生、「これで30分くらいは稼げるだろう。その間に他の業務をしよう」あるいは「ちょっと一息入れてお茶でも飲もう」と考えたのかもしれない。しかしその計画は、うまくいかなかった。なぜなら生徒の中にガウス少年がいて、一瞬で 5050 という答えを出してしまったから。

別にガウスは、足し算が超高速だったわけではない。その問題では、単に端から順に二つずつ数を足すと、
　　1 + 100 = 101
　　2 + 99 = 101
　　3 + 98 = 101
　　···
となって、100 個の数を二つずつペアにすれば、和が 101 のペアがちょうど 50 個できるので、
　　101 × 50 = 5050
と結論したのであるっ！

この「エレガント」で美しい解法は、現代では基本ツールの一つとされている。一般に、
　　1 + 2 + 3 + ··· + n = (1 + n) × n/2
となる。 n が偶数のときは、ガウスの説明の通り、ちょうど n/2 個のペアができるので、これが成り立つことは明白だろう。 n が奇数のとき、両端から二つずつペアを作っていくと、ど真ん中にペアにならない数が一つ余る。例えば n = 5 なら、
　　1 + 2 + (3) + 4 + 5
の (3) のように。この「真ん中で余る数」の左隣と右隣、つまり 2 と 4 は、通常のペアになる。「真ん中で余る数」を x とすると、 x−1 と x+1 は通常のペアなので、
　　(x−1) + (x+1) = x − 1 + x + 1 = 2x
は、通常のペアの和に等しく、従って x 自身は通常の一つのペアの和の半分に等しい。よって、
　　1 + 5 = 6　←　一つのペア
　　2 + 4 = 6　←　一つのペア
　　(3) = 6/2　←　一つのペアの半分
となって、これら五つの数の和は、「ペアが合計 2.5 個」あるのと同じこと。結局、
　　1 + 2 + 3 + 4 + 5 = (1 + 5) × 5/2 = 6 × 2.5 = 15
のような計算は、項数が奇数でも（ペアの総数に 0.5 の端数があっても）、成り立つ。

1 から n までの自然数の和　最小 1 と最大 n を足したものに、項数 n の半分を掛ければいい

ところで 1 + 2 + 3 + ··· + 100 のような表現は、数回書く分には何でもないが、「···」を使っても少々長ったらしいし、こういう表現を何十回、何百回も書くのは面倒。簡潔な省略記法を導入した方が、形式的・機械的に処理できて便利でもある。そんなわけで、しばしば次のような記号が使われる。
　　∑ { from k=1 to 100 } k
意味は「k を 1 から 100 まで変化させながら、足し合わせる」ということで、
　　1 + 2 + 3 + ··· + 100
と全く同じ。文字 k は、プログラミングでいう「ループ変数」（ループ構造を制御する一時的な形式変数）であり、他の文字を使っても構わない。例えば、
　　∑ { from i=1 to 100 } i　や　∑ { from j=1 to 100 } j
も、全く同じ和を表すし、そうしたければ ℓ や m などを使ってもいいし、きざにギリシャ文字、例えば ι や λ などを使ってもいい。既に使用中の他の変数名とダブらなければ、その文字は何でもいい（慣習として i, j, k あたりがよく使われる）。この ∑ という記号を「総和記号」と呼び、現代では、上の例のような書式を使って「ループ変数の最初の値」を ∑ の下に書き、「最後の値」を ∑ の上に書くことが多い（他にもバリエーションはあるけど）。［このページでは、CSS（スタイルシート）が無効の場合、本来下に書く部分・上に書く部分は、それぞれ横に「from k=1」と「to 100」のように表示される。］

ともあれ 1 から n まで足すと (n + 1) × n/2 = n(n + 1)/2 になるという前記の事実は、次のように記述可能。
　　∑ { from k=1 to n } k = n(n + 1)/2

〔例〕　n = 5 のとき:
　　∑ { from k=1 to 5 } k = 5(5 + 1)/2 = 15
これは 1 + 2 + 3 + 4 + 5 = 15 という足し算のショートカットに当たる。

【2】　ここで興味深い事実がある。 1 + 2 + 3 + 4 + 5 = 15 の代わりに、左辺の各項を立方しながら足すと、つまり、
　　1³ + 2³ + 3³ + 4³ + 5³
という和を考えると、右辺の 15 は平方されて 15² = 15 × 15 = 225 になるのだ。実際:
　　1³ + 2³ + 3³ + 4³ + 5³ = 1 + 8 + 27 + 64 + 125 = 36 + 64 + 125　　← とりあえず 1 + 8 + 27 = 9 + 27 = 36 だけ計算した
　　 = 100 + 125 = 225

より一般的に、
　　1³ + 2³ + 3³ + 4³ + ··· + n³ = (1 + 2 + 3 + 4 + ··· + n)²
が成り立つ。総和記号で書けば:
　　∑ { from k=1 to n } k³ = [∑ { from k=1 to n } k]² = [n(n + 1)/2]² = n²(n + 1)²/4

〔例〕　n = 5 のとき:
　　∑ { from k=1 to 5 } k³ = 5²(5 + 1)²/4 = 25 × 36 ÷ 4 = 25 × 9 = 225
これは 1³ + 2³ + 3³ + 4³ + 5³ = 225 という足し算のショートカットに当たる。

1 + 2 + ··· + n の和が n(n + 1)/2 であることさえ知ってれば（両端から二つずつペアにしていけば、そうなることは明らかだろう）、その n(n + 1)/2 を単に平方することで、立方和の公式が得られる――この事実はいわば偶然だが、非常に印象的だし、記憶の上でも便利。なぜそうなるかの証明は、それほど難しくない。

さて 1 + 2 + ··· + n と 1³ + 2³ + ··· + n³ を素早く計算するショートカットが分かった今、他の指数の和はどうなるのか？というのは自然な疑問だろう。残念ながら、さほど覚えやすい形でもないのだが、例えば次が成り立つ。
　　1² + 2² + ··· + n² = n(n + 1)(2n + 1)/6　　［証明］
　　1⁴ + 2⁴ + ··· + n⁴ = n(n + 1)(2n + 1)(3n² + 3n − 1)/30　　［証明］
以下では、この一つ目の式（2乗和の公式）を利用する部分がある。二つ目の式（4乗和の公式）は、以下では全く必要ない。

【3】　「最初の c 個の正の奇数」の立方和に、話を戻す。とりあえず「奇数の表現」が必要だが、ループ変数が k = 1, 2, 3, ··· のとき、値が奇数 1, 3, 5, ··· になるようにするには、どんな式表現を使えばいいか？

ターゲットは 2, 4, 6, ··· の各項から 1 を引いたもので、 2, 4, 6, ··· は k = 1, 2, 3, ··· に対する 2k なので、
　　k = 1, 2, 3, ···　⇒　2k − 1 = 1, 3, 5, ···
とすればいいだろう。 1³ + 3³ + 5³ + ··· という形の c 項の和を、こう書くことができる。
　　∑ { from k=1 to c } (2k − 1)³ = ∑ { from k=1 to c } (8k³ − 12k² + 6k − 1)　　《あ》

〔注〕　この等号は 3 乗の二項展開 (a + b)³ = a³ + 3a²b + 3ab² + b³ による（a = 2k, b = −1 としたもの）。

k = 1, 2, ···, c に対する (8k³ − 12k² + 6k − 1) の和を計算する代わりに、同じ範囲の k に対して、
　　8k³ の和を求め、
　　−12k² の和を求め、
　　6k の和を求め、
　　−1 の和を求め、
そして、それら全部を後から合算しても同じこと。例えば:
　　[8(1)³ − 12(1)² + 6(1) − 1] +
　　[8(2)³ − 12(2)² + 6(2) − 1] +
　　[8(3)³ − 12(3)² + 6(3) − 1]
を項ごとに縦に足せば:
　　= 8(1³ + 2³ + 3³) − 12(1² + 2² + 3²) + 6(1 + 2 + 3) − (1 + 1 + 1)

この考え方によると、《あ》を次のように変形できる。
　　《あ》 = 8 ∑ { from k=1 to c } k³ − 12 ∑ { from k=1 to c } k² + 6 ∑ { from k=1 to c } k − ∑ { from k=1 to c } 1　　《い》

《い》の最初の三つの総和記号については、われわれは既にショートカットを知っているので機械的に処理できるし、四つ目の総和記号は「ループカウンターが k = 1 から c まで動く間の回数、 1 を足す」要するに「c 個の 1 を足し合わせる」という意味なので、値が c であることは明白。前述のショートカット（1乗和・2乗和・3乗和の公式）を使うと:
　　《い》 = 8[c²(c + 1)²/4] − 12[c(c + 1)(2c + 1)/6] + 6[c(c + 1)/2] − [c]
　　 = 2c²(c + 1)² − 2c(c + 1)(2c + 1) + 3c(c + 1) − c
ここで全部の項を展開してもいいのだが、まぁ少し省力的に、共通因子 c をくくり出すことにすると:
　　 = c[2c(c + 1)² − 2(c + 1)(2c + 1) + 3(c + 1) − 1]
　　 = c[2c(c² + 2c + 1) − 2(2c² + 3c + 1) + 3c + 3 − 1]
　　 = c[(2c³ + 4c² + 2c) − (4c² + 6c + 2) + 3c + 2]
　　 = c[2c³ − c] = 2c⁴ − c²

これで今回のテーマの命題が証明された！　「変形して公式に当てはめる」という、なんとも味気ないやり方だが、その代わり工夫やインスピレーションは必要なく、機械的に淡々とできる。《あ》から《い》への変形の根拠――それは、総和記号の対象となっている多項式について、「3次の項だけ」「2次の項だけ」等々、公式適用に都合がいい部分を集めて、部分ごとにまとめて計算できるということ（足し算の交換法則・結合法則）、そして係数を総和記号の前にくくり出せるということ（分配法則）。当たり前か。

具体的な計算は微妙に面倒くさいけど、結局はただの単純計算。「足せない総和があるものか、順序を変えればちょちょいのちょい。ああ青春のベルヌーイ」ってな感じで、足してみるのも、たまには悪くないかと…

【4】　いずれにせよ c = 4 の場合には:
　　2(4)⁴ − (4)² = 2⋅256 − 16 = 512 − 16 = 496
検算として:
　　1³ + 3³ + 5³ + 7³ = 1 + 27 + 125 + 343 = 496

この 512 − 16 = 496 という計算は、 2 の累乗間の引き算だ。というのも 2¹⁰ = 1024 はコンピューター時代の常識であり（1ギガバイトのメディアが 1000 MiB でなく 953 MiB しかない、という謎の原因！）、その半分の 512 は 2⁹ に等しい。よって:
　　512 − 16 = 2⁹ − 2⁴ = 2⁴(2⁵ − 1) = 2⁴(32 − 1)
　　∴　496 = 2⁴ × 31

31 は素数なので、上記の最後の式は 496 を素因数にばらしたもの。「もうそれ以上は分解不可能」という素数の性質上、496 の（正の）約数は、 496 自身を構成する「部品」と同じ「部品」の組み合わせの範囲で、構成される――簡単に言えば 496 の約数は、因子として 2 を 0 個か 1 個か 2 個か 3 個 か 4 個、含んでいるし（5 個以上は不可）、 31 を 0 個か 1 個、含んでいるし（2 個以上は不可）、それ以外の素因子を含むことは、できない。つまり 496 の約数たちは、
　　2⁰, 2¹, 2², 2³, 2⁴,
　　2⁰⋅31, 2¹⋅31, 2²⋅31, 2³⋅31, 2⁴⋅31
の、ちょうど 10 個。ところが、
　　2⁰ + 2¹ + 2² + 2³ + 2⁴ = 1 + 2 + 4 + 8 + 16 = 31
　　よって　2⁰⋅31 + 2¹⋅31 + 2²⋅31 + 2³⋅31 + 2⁴⋅31 = (2⁰ + 2¹ + 2² + 2³ + 2⁴)⋅31 = 31 × 31
なので、これら 10 個の約数の和は:
　　31 + 31 × 31 = (1 + 31) × 31 = 32 × 31

496 の約数の和から、 496 自身、つまり 2⁴ × 31 = 16 × 31 を除外すると:
　　32 × 31 − 16 × 31 = (32 − 16) × 31 = 16 × 31
この 16 × 31 という積は 496 そのものなので、 496 の約数（自分自身を除く）の和は自分自身（496）であり、言い換えれば 496 の約数（自分自身を含む）の和は、自分自身の 2 倍。 496 は完全数なのだっ！

何となく、完全数ってのは「2 の累乗とちょっとだけずれた数」と関係してるっぽい――ってことが、感じられる。

2024-12-07　「2乗和・3乗和・4乗和の公式」の簡単な導出法

#遊びの数論　#べき和

このメモでは、簡易的な方法で、
　　1² + 2² + ··· + n² = n(n + 1)(2n + 1)/6
　　1³ + 2³ + ··· + n³ = n²(n + 1)²/4
　　1⁴ + 2⁴ + ··· + n⁴ = n(n + 1)(2n + 1)(3n² + 3n − 1)/30
の三つの基本公式と、対応するベルヌーイ形式を導く。

ベルヌーイ形式については、ほぼ予備知識ゼロでできる――小学校の算数（連立1次方程式）だけを使って。一般的な導出法――帰納法や二項展開からの畳み込み（telescoping）――と比べお手軽だが、その代わり「s 乗和の公式は s+1 次の多項式」という前提を受け入れる必要がある。関連事項として、「公式をだいたい覚えてるが部分的に度忘れした」ような場合に「記憶があやふやな部分を再建する方法」を付記。

1² + 2² + 3² + ··· について。面積 1², 2², 3², ··· の正方形を上空から地面に向かって中心を合わせて並べたら、（大ざっぱには）角すい。角すいの体積は立方メートル（m³）とかの単位なんで、きっと何らかの3次式があって、
　　最初の n 個の平方数の和 f(n) = An³ + Bn² + Cn　「仮想公式①」
と表せるはず（とりあえず係数 A, B, C の値は不明）。もしもこの公式の右辺に「0 以外の定数項」が有ったら、 n = 0 のときの値が 0 にならない。それは「0 項足した和＝無の状態」が 0 じゃないって意味で、どう考えても間違ってるので、定数項は無し（0）で良いだろう…。

仮想公式①に n = 1, 2, 3 を入れたとき、もしも公式が本物だったら、式の値は順に 1², 1² + 2², 1² + 2² + 3² つまり 1, 5, 14 になってくれていたはず。つまり、この仮想公式が本物の公式になるためには、次の条件が満たされねばならない:
　　f(1) = A⋅1 + B⋅1 + C⋅1 = 1　　ア
　　f(2) = A⋅8 + B⋅4 + C⋅2 = 5　　イ
　　f(3) = A⋅27 + B⋅9 + C⋅3 = 14　　ウ

アから C = 1 − A − B、それをイ・ウに代入すると、
　　8A + 4B + 2(1 − A − B) = 6A + 2B + 2 = 5
　　27A + 9B + 3(1 − A − B) = 24A + 6B + 3 = 14
つまり:
　　6A + 2B = 3　　エ
　　24A + 6B = 11　　オ
エを 3 倍した 18A + 6B = 9 をオから引くと:
　　6A = 2　　∴　A = 1/3
よってエから:
　　2B = 3 − 6A = 3 − 2 = 1　　∴　B = 1/2
最後にアから:
　　C = 1 − A − B = 1 − 1/3 − 1/2 = 1/6

仮想だった公式①が実体化したっ！
　　最初の n 個の平方数の和 = n³/3 + n²/2 + n/6 = (n/6)(2n² + 3n + 1)

上記の形でも十分実用になるが、この式は、丸かっこ内の2次式を分解した形で記されることが多い。2次式の分解は、小学校の算数では、ちょっと面倒かも…

もし「たすき掛け」を使って2次式を分解するなら、直ちに、
　　2n² + 3n + 1 = (n + 1)(2n + 1)
となるが、別のオプションもあって、そっちの方が応用が利く。

それは「分解したい多項式 2n² + 3n + 1 の有理数の根（言い換えれば 2n² + 3n + 1 = 0 の有理数解）を探す」――ってアプローチ。

一般論的には…。もし多項式が有理数の根を持つなら、その根は「分子が定数項の約数」（この例の定数項は 1 なので、可能性は 1 のみ）、「分母が最高次の係数の約数」（この例の最高次の係数は 2 なので、可能性は 1 or 2 のみ）、符号は ± どちらもあり得る。よって、2n² + 3n + 1 の場合、有理数の根になるかもしれない候補は n = ±1/1, ±1/2 つまり ±1 と ±1/2 の四つだけ。

ところが 2n² + 3n + 1 は全部の係数・定数項が正なので、 n に正の数を入れても式の値は正で、決して 0 にならない。つまり、根があるとすれば負の値。負の候補だけを試せばいい。 n = −1 のとき 2(−1)² + 3(−1) + 1 = 2 − 3 + 1 = 0 なので、 −1 は根。 n = −1/2 のとき 2(−1/2)² + 3(−1/2) + 1 = 1/2 − 3/2 + 1 = 0 なので n = −1/2 も根。よって、この2次式は n = −1 を根とする1次式 n + 1 で割り切れ、 n = −1/2 を根とする1次式 2n + 1 でも割り切れる（1次式と1次式の積は2次式なので、それ以外の因子はない）。再び、
　　2n² + 3n + 1 = (n + 1)(2n + 1)
という分解を得る。

〔注〕　2次式なら、もちろん直接分解した方が速い。「この方法は3次以上の多項式にも通用する」ってのがポイントで、少し後でそれを利用するであろう。

〔参考〕　実は s 乗和の公式（s: 自然数）の根は −1/2 を中心に左右対称に存在する。もしこのインサイダー情報を使うと（チートだが）…。 (n/6)(2n² + 3n + 1) の一つの根は明らかに n = 0 なので、別の一つの根が −1/2 を中心として n = 0 と対称の位置にある（n = −1）。3次式の根は、あと一つだけ。対称性の維持のためには、対称の中心 n = −1/2 自身が三つ目の根になるしかない。

いずれにしても、分解・整理すると「普通の形」の公式を得る。

1² + 2² + ··· + n² = n(n + 1)(2n + 1)/6

天下り的に公式だけ与えられると、ランダムで無味乾燥にも思えるが、分子の根が −1, −0.5, 0 であることに着目すると、意外と「等間隔に、きっちり」。分子はそれでいいとしても、分母が覚えにくい？

けど n = 1 のとき和が 1 ってことは明白、そのとき分子が 1⋅2⋅3 = 6 ってことも一目瞭然。ちょっと考えれば分母は 6 になるしかあるまい。

一つの例だけじゃ、いまいちピンとこないかもしれないんで、同様の方法で「3乗和の公式」を導いてみる。
　　最初の n 個の3乗和 = An⁴ + Bn³ + Cn² + Dn　　「仮想公式②」
に n = 1, 2, 3, 4 を代入すると:
　　A + B + C + D = 1　　カ
　　16A + 8B + 4C + 2D = 9　　キ
　　81A + 27B + 9C + 3D = 36　　ク
　　256A + 64B + 16C + 4D = 100　　ケ

カから得た D = 1 − A − B − C をキ・ク・ケに入れて:
　　16A + 8B + 4C + 2(1 − A − B − C) = 14A + 6B + 2C + 2 = 9　　ギ
　　81A + 27B + 9C + 3(1 − A − B − C) = 78A + 24B + 6C + 3 = 36　　グ
　　256A + 64B + 16C + 4(1 − A − B − C) = 252A + 60B + 12C + 4 = 100　　ゲ
つまり:
　　14A + 6B + 2C = 7　　サ
　　78A + 24B + 6C = 33　　シ
　　252A + 60B + 12C = 96　　ス

サの 3 倍 42A + 18B + 6C = 21 をシから引くと:
　　36A + 6B = 12　　セ
サの 6 倍 84A + 36B + 12C = 42 をスから引くと:
　　168A + 24B = 54　　ソ

セの 4 倍 144A + 24B = 48 をソから引いて:
　　24A = 6　　∴　A = 1/4
　　セから　6B = 12 − 36A = 12 − 9 = 3　　∴　B = 1/2
　　サから　2C = 7 − 14A − 6B = 7 − 3.5 − 3 = 0.5　　∴　C = 1/4
　　カから　D = 1 − B − C − D = 0

よって仮想公式②は、次のように実体化する:
　　最初の n 個の3乗和 = n⁴/4 + n³/2 + n²/4 = (n⁴ + 2n³ + n²)/4
　　 = n²(n² + 2n + 1)/4 = n²(n + 1)²/4

1³ + 2³ + ··· + n³ = n²(n + 1)²/4

最初の n 個の正の整数の和 = n(n + 1)/2 の平方に当たる――3乗和は。この性質は興味深いし、公式の記憶や実際の計算の上でも都合がいい。

4乗和バージョンに進み、ついでに一般の s 乗和がどうなるのか、垣間見ておくとしよう。
　　最初の n 個の4乗数の和 = An⁵ + Bn⁴ + Cn³ + Dn² + En　　「仮想公式③」

〔注〕　以下の話では、次の数値を使う。4乗は「平方の平方」なので 1, 2, 3, 4, 5 の4乗は順に「1, 4, 9, 16, 25 の平方」、つまり、
　　1, 16, 81, 256, 625　　☆
であり、従って 1, 2, 3, 4, 5 の5乗は、順に 1, 32, 243, 1024, 3125。一方、☆を順々に足したものは:
　　1⁴ + 2⁴ = 1 + 16 = 17
　　それ + 3⁴ = 17 + 81 = 98
　　それ + 4⁴ = 98 + 256 = 354
　　それ + 5⁴ = 354 + 625 = 979

今、仮想公式③に n = 1, 2, 3, 4, 5 を代入すると:
　　A + B + C + D + E = 1　　タ
　　32A + 16B + 8C + 4D + 2E = 17　　チ
　　243A + 81B + 27C + 9D + 3E = 98　　ツ
　　1024A + 256B + 64C + 16D + 4E = 354　　テ
　　3125A + 625B + 125C + 25D + 5E = 979　　ト

タから得た E = 1 − A − B − C − D をチ・ツ・テ・トに代入:
　　32A + 16B + 8C + 4D + 2(1 − A − B − C − D) = 17
　　243A + 81B + 27C + 9D + 3(1 − A − B − C − D) = 98
　　1024A + 256B + 64C + 16D + 4(1 − A − B − C − D) = 354
　　3125A + 625B + 125C + 25D + 5(1 − A − B − C − D) = 979
整理すると:
　　30A + 14B + 6C + 2D = 15　　ナ
　　240A + 78B + 24C + 6D = 95　　ニ
　　1020A + 252B + 60C + 12D = 350　　ヌ
　　3120A + 620B + 120C + 20D = 974　　ネ

ナから得た 2D = 15 − 30A − 14B − 6C をニ・ヌ・ネに代入:
　　240A + 78B + 24C + 3(15 − 30A − 14B − 6C) = 95
　　1020A + 252B + 60C + 6(15 − 30A − 14B − 6C) = 350
　　3120A + 620B + 120C + 10(15 − 30A − 14B − 6C) = 974
整理すると:
　　150A + 36B + 6C = 50　　ハ
　　840A + 168B + 24C = 260　　ヒ
　　2820A + 480B + 60C = 824　　フ

ハを 4 倍した 600A + 144B + 24C = 200 をヒから引いて:
　　240A + 24B = 60　　ヘ
ハを 10 倍した 1500A + 360B + 60C = 500 をフから引いて:
　　1320A + 120B = 324　　ホ
ヘを 5 倍した 1200A + 120B = 300 をホから引いて:
　　120A = 24　　∴　A = 1/5
　　ヘから　24B = 60 − 240A = 60 − 48 = 12　　∴　B = 1/2
　　ハから　6C = 50 − 150A − 36B = 50 − 30 − 18 = 2　　∴　C = 1/3
従ってナから:
　　2D = 15 − 30A − 14B − 6C = 15 − 6 − 7 − 2 = 0　　∴　D = 0
最後にタから、
　　E = 1 − A − B − C − D = 1 − A − B − C = 1 − (A + B + C)　　★
となるが（D = 0 だ）、
　　A + B = 1/5 + 1/2 = 7/10
　　∴　A + B + C = 7/10 + 1/3 = 31/30
なので ★ から、
　　E = 1 − 31/30 = −1/30
となる。わーい、係数が全部求まった！　4乗、4乗、うれしいなっ♪

結局、仮想公式③の実体は:
　　最初の n 個の4乗数の和 = n⁵/5 + n⁴/2 + n³/3 − n/30　　（♪）
　　 = (6n⁵ + 15n⁴ + 10n³ − n)/30 = n(6n⁴ + 15n³ + 10n² − 1)/30　　（♫）

（♪）は「ベルヌーイ形式」。この形式で書く場合、 s 乗和の公式は、次のおきてに従う。

べき和の道の五箇条　1^s + 2^s + ··· + n^s なる和は s+1 次の多項式にして、その性状は次のごとし。
　　一つ　最高次の項は常に　n^s+1/(s+1)　なり（上の例では s = 4）。これベルヌーイの初めなり。高校生以上の方は、原始関数をイメージするべし。
　　二つ　二つ目の項、つまり n^s の係数は　1/2　なり。これベルヌーイの中道なり。
　　三つ　三つ目の項、つまり n^s−1 の項あらば、その係数は　s/12　なり（上の例では 4/12 = 1/3）。
　　四つ　四つ目以下の「偶数番目に対応する次数」の項、つまり n^s−2 の項、 n^s−4 の項などは、存在せず（係数 0）。すなわち三つ目の項までは次数が一つずつ減り、それ以降の項があれば、次数が二つずつ減ると心得よ。
　　五つ　定数項は無し。ゆえに最低次の項は「s が 3 以上の奇数なら2次、それ以外なら1次」なり。

〔補足〕　この五箇条を知っていても、依然、不明な係数が残り得る。次の E, F が不明係数の最初の2例:
　　1乗和 = n²/2 + n/2
　　2乗和 = n³/3 + n²/2 + (2/12)n
　　3乗和 = n⁴/4 + n³/2 + (3/12)n²
　　4乗和 = n⁵/5 + n⁴/2 + (4/12)n³ + En
　　5乗和 = n⁶/6 + n⁵/2 + (5/12)n⁴ + Fn²
（♪）は、これを補う貴重な情報 E = −1/30 を含んでいる。逆に言うと A, B, C, D は、実は（計算するまでもなく）上の規則から機械的に決定可能だった。 E だけ求めればいいのだから、 n = 1 のとき和が 1 という事実を利用して 1/5 + 1/2 + 4/12 + E = 1 を解けば、それで話は終わりだったのだ。同様に、5乗和の公式の不明係数 F は、 1/6 + 5/2 + 5/12 + F = 1 から決定可能（F = −1/12）。

（♫）の形式は、比較的処理が面倒。丸かっこ内の4次式 6n⁴ + 15n³ + 10n² − 1 を分解できるか。この4次式に有理数の根があれば、それは、
　　n = ±1, ±1/2, ±1/3, ±1/6
の中の 1 個以上（理由については前述）。 6n⁴ + 15n³ + 10n² − 1 の n に正の数を入れると、定数項以外は正なので、最初の 3 項の和が 1 にならない限り、式の値は 0 にならない。 n = 1 は明らかに過大。 n = 1/2 も2次の項だけで 10/4 = 2.5 なので過大。一方、 n = −1 が根であることは、簡単に確かめられる: 6 − 15 + 10 − 1 = 16 − 16 = 0 なので。さらに n = −1/2 を入れると 6/16 − 15/8 + 10/4 − 1 = 3/8 − 15/8 + 2.5 − 1 = −12/8 + 1.5 = −1.5 + 1.5 = 0 なので、これも根。

〔注〕　前述のインサイダー情報を使うなら、この二つの根は直ちに求まる。

他方 n = ±1/3 は根ではない。前半 2 項で発生する「分母 3³ = 27 の分数」を消滅させるためには、後半 2 項で生じる分母 3² = 9 は小さ過ぎるので。同様の理由から n = ±1/6 も根ではない。

結論として 6n⁴ + 15n³ + 10n² − 1 は、 n = −1 を根とする1次式 n + 1 で割り切れ、 n = −1/2 を根とする1次式 2n + 1 でも割り切れるが、それ以外の（整係数の）1次式では割り切れない。 2 回割り算する代わりに (n + 1)(2n + 1) = 2n² + 3n + 1 でまとめて割ってもいいだろう（この2次式を得る掛け算は 11 × 21 = 231 と同様）。

                3n^2 +  3n   -  1
              ┌──────────────────────────────
2n^2 + 3n + 1 │ 6n^4 + 15n^3 + 10n^2 + 0n - 1
                6n^4 +  9n^3 +  3n^2
                ────────────────────
                        6n^3 +  7n^2 + 0n
                        6n^3 +  9n^2 + 3n
                        ─────────────────────
                               −2n^2 - 3n - 1
                               −2n^2 - 3n - 1
                               ──────────────
                                            0

上記のように、商は 3n² + 3n −1。次の結論に至る。

1⁴ + 2⁴ + ··· + n⁴ = n(n + 1)(2n + 1)(3n² + 3n − 1)/30

この右辺の分数は、 1² + 2² + ··· + n² の、
　　n(n + 1)(2n + 1)/6
とだいたい同じだが、分子に因子 (3n² + 3n − 1) が追加され、分母が 5 倍されて 30 に変わっている。大ざっぱに「さんさん、サンジュー」って覚えてもいいかも。えっ、定数項の −1 はどうした？　だから「大ざっぱに」って言ったじゃんｗ

ぶっちゃけ、一つくらい不明の係数や定数項があっても、次のようにすれば問題ない。例えば、
　　1⁴ + 2⁴ + ··· + n⁴ = n(n + 1)(2n + 1)(3n² + 3n + ●)/30
の ● の数字をうろ覚え・度忘れした・資料を開いて調べるのも面倒くさい、という場合、左辺が 1⁴ の 1 項だけだったら、右辺は明らかに 1。そのとき分子は 30 にならなければならないので、分子で n = 1 と置けば、
　　1(1 + 1)(2 + 1)(3 + 3 + ●) = 30　つまり　6(6 + ●) = 30
　　∴　6 + ● = 5　つまり　● = −1
となって、「記憶の虫食い部分」をその場で復元できる。

2024-12-08　行列方程式で遊んじゃえっ　（おまけ）

#遊びの数論　#べき和

前回、小学生の算数だけを使って、
　　1² + 2² + ··· + n² = n³/3 + n²/2 + n/6
を求めた。消去法を使って連立方程式をどーたらこーたらという、ありふれた解法だった。ただの算数じゃ退屈かもしれないので、同様のことをファンシーに、行列方程式でやってみたい――わざわざ大げさに行列を持ち出すほどの問題でもないけど、まぁ遊びってことで。

前回の方法では、2乗和の公式を仮に An³ + Bn² + Cn として、三つの未知数 A, B, C を決定するために、公式が満たすはずの三つの等式を作った（三つの等式は、正しいサンプルなら何でも良かったのだが、数が小さい方が楽なので、安易に n = 1, 2, 3 の三つのサンプルを考えた）。

ベルヌーイのおきて（前回参照）によれば、見た瞬間に A = 1/3, B = 1/2, C = 2/12 = 1/6 ということが分かって、実は計算するまでもない。しかしここでは話の便宜上、 A = 1/3 だけが既に分かっているものとする。ちなみに、このことは、
　　『n³　を n について微分すると　3n²　になる』
という微積分の基礎と関連している。『』の関係を 1/3 倍すると、
　　「1/3 × n³　を n について微分すると　n²　になる」
となるが、微分の反対は「積分」なので、逆に言えば、 n² を「積分」すると 1/3 × n³ になる。これが A = 1/3 という係数の正体だろう。

なぜそうなるか？　底面が正方形、高さが整数の角すいの体積は、「断面が正方形になるように（底面に平行に）、角すいを細かくスライスして得られる薄い板」たちの、体積を足し合わせたもの。分割を極限まで細かくした場合が「積分」（本当の体積）なんだけど、 1² + 2² + ··· は、（限りなく細かくスライスする代わりに）厚さ 1 刻みでスライスして正方形の板を作り、それを「高さ 1 の直方体」と見なした場合の体積の和に当たる。角すいの側面は斜めなんで、この「厚さ 1 の板」は本当は「直方体」ではないし、厚さ 1 では「限りなく細かくスライス」にもなってないけど、大ざっぱには「積分」の定義に近いので、「変化する正方形の面積 x² を x = 0 から x = n まで積分したもの」とだいたい同じに。結果として、2乗和の公式、
　　An³ + Bn² + Cn
のメインの項（第1項）は、 x² の上記の定積分と一致（しかし、2乗和の公式全体としては、原始関数とは多少ずれている）。例えば「球」などの「体積の公式」を思い出すと、そこにもしばしば 1/3 が絡んでる。

ともかく、仮に、
　　最初の n 個の平方数の和 = n³/3 + Bn² + Cn　　《式》
というところまでは分かっている――ということを前提として、 B と C を求めたい。

n = 1 の場合、《式》の左辺が 1² = 1 ということは明らかだが、右辺は、
　　1³/3 + B⋅1 + C⋅1
なので、要するに、
　　1 = 1/3 + B + C　つまり　B + C = 2/3
となる。同様に、 n = 2 の場合、左辺 1² + 2² = 5 と、右辺 2³/3 + B⋅2² + C⋅2 が等しいので、
　　5 = 8/3 + 4B + 2C　つまり　4B + 2C = 7/3
となる。

こうして生じる連立方程式、
　　1B + 1C = 2/3
　　4B + 2C = 7/3
を実直に解くことは、難しくない。第一式の 2 倍を第二式から引けば C が消去され、うんぬん。しかしここでは、これを行列方程式、
　　(1  1; 4  2)(B; C) = (2/3; 7/3)
として扱う。意味は、上記の連立方程式と全く同じだが、一応、各部を観察してみると…
　　(1  1; 4  2)
は、四つの数（この例では、連立方程式の係数だが）を2行2列に並べたもので、これが「行列」の例。この行列を M としよう。一方、
　　(B; C)
は、二つの数（この例では、未知数！）を2行1列に並べたもので、2行1列の「行列」と思ってもいいし、2次元の「縦ベクトル」（列ベクトル）と思ってもいいだろう（厳密には、その二つは違う概念かもしれないが、細かいことは気にしない方向で）。この「中身不明、2行1列」の謎の物体を X と呼ぶことにしよう。最後に、右辺の
　　(2/3; 7/3)
ってやつも2行1列の「行列」ないし縦ベクトルだが、こいつの名前は、まぁ P とでもしましょうか。

すると、われわれのミッションは、
　　MX = P
という方程式を X について解くこと。そのためには、 M の逆数 M⁻¹ を両辺に左から掛けて、
　　M⁻¹MX = M⁻¹P　つまり　X = M⁻¹P
とやればいいだろう。いきなり行列 M の「逆数」と言われても意味不明かもしれないけど、まぁ複素数や四元数にも逆数があるんだから、 M の逆数だってあるんじゃね？

ちなみに、行列は複素数や四元数と同様、結合法則を満たすので、
　　M⁻¹(MX)　が　(M⁻¹M)X　に等しいか？
という問題で悩む必要はない（八元数での苦労を思うと、実にありがたい）。 M⁻¹M という積は、数でいえば 1 のようなものなので、その結果、上記の「つまり」の後ろのようになって、謎の物体 X の正体が判明するだろう。たぶん。

四元数や八元数との比較は、参考までに記してるだけ。「四元数」等をよく知らない方は、これらのコメントを無視してください。

「数でいえば 1 のようなもの」の行列とは、実は、
　　(1  0; 0  1)
みたいな形をしている。どーしてこれが 1 のようなものなのか。実は「行列と行列の掛け算」は、次のように定義される。
　　(a  b; c  d)(タ  ダ; テ  デ) = (aタ+bテ  aダ+bデ; cタ+dテ  cダ+dデ)
簡単に言うと: 掛け算される二つの行列のうち、左の行列を「横・横」の 2 行と見て、右の行列を「縦・縦」の 2 列と見た場合、積の各要素は、対応する「横」（それを y₁, y₂ とする）と「縦」（それを t₁, t₂ とする）を使って、
　　y₁t₁ + y₂t₂
となる。分数の計算とかと同じで、慣れれば何でもないのだが、最初は訳が分からないかも…。あまり気にせず、とにかく ダ と テ が 0 だったら、それらを含む積は 0 になり、ないのと同じ。さらに タ = デ = 1 だとすると、「積の定義の右辺に生じる四つの要素は、左辺の（第一の）行列の要素 a, b, c, d と全く同じだよ」っと。そのことは、上記「掛け算の定義」に当てはめて考えれば、明らかだろう。

「ある数 k に 1 を掛けたら k になる」（当たり前）というのと同様に、ある2行2列の行列 (a  b; c  d) に (1  0; 0  1) を掛けた結果は (a  b; c  d) のまま。この意味で (1  0; 0  1) は、普通の数の掛け算の 1 のようなもの。

ところで、行列の積では、一般には交換法則が保証されない（この点は、実数や複素数と違い、四元数と似ている）。つまり、掛け算の順序を勝手にひっくり返してはいけない。ということは、 (1  0; 0  1) を右から掛けると「普通の数の 1 みたい」だとしても、同じものを左から掛けても「普通の数の 1 みたい」かどうかは、必ずしも明らかではないのだ…。とはいえ、積の定義から、
　　(1  0; 0  1)(a  b; c  d) = (1a+0c  1b+0d; 0a+1c  0b+1d)
なので、この (1  0; 0  1) という物体に限って言えば、左右どっちから掛けても「普通の数の 1 みたい」な性質を持つ。この 1 みたいな物体を大文字の I で表すことにする。

結局、われわれのミッションに必要な M⁻¹ とは、上記の積の定義の下で (M⁻¹)M = I を満たすような行列。それをどーやって求めるのか。面倒な理論を省き、やり方だけ書く。第一に、
　　M = (1  1; 4  2)
に対して、右下がりの対角線にある二つの数の積から、左下がりの対角線にある二つの数の積を引き算する:
　　1 × 2 − 1 × 4 = 2 − 4 = −2
この数は det M で表されるが、コンセプト的には複素数や四元数のノルムのようなものといえるかもしれない。でもって、第二に、 M の右下がりの対角線の要素を入れ替えて、左下がりの対角線の各要素を（入れ替えずに）単に −1 倍する。その結果は adj M で表される。
　　adj M = (2  −1; −4  1)　　← M の 1 と 2 を入れ替えて、残りの要素を −1 倍した
第三に、これが最後だが、この adj M の各要素を前記 det M = −2 で割ると、それが M⁻¹ なのだ:
　　M⁻¹ = (−1  1/2; 2  −1/2)
積の定義に当てはめれば、この行列を M に左から掛けても、右から掛けても、結果は I であることを確かめられる。もちろんなぜこの方法で M⁻¹ が求まったのか？というのは、本来、理論的な考察が必要であり、上記の説明はひどい手抜きである…。

その点に目をつぶるなら、 X = M⁻¹P を求めるのがわれわれのミッションなのだから、その答えは:
　　X = (−1  1/2; 2  −1/2)(2/3; 7/3) = (−1⋅(2/3) + (1/2)⋅(7/3); 2⋅(2/3) − (1/2)⋅(7/3))
右辺の二つの分数計算を実行すると、上にあるやつ（1行目）が、
　　−2/3 + 7/6 = −4/3 + 7/6 = 3/6 = 1/2
となり、下にあるやつ（2行目）が、
　　4/3 − 7/6 = 8/6 − 7/6 = 1/6
となって、 X = (B; C) = (1/2; 1/6) となる。すなわち B, C が正しく決定された！

この例題では、普通に連立方程式を解く方が、手っ取り早いように思える。でも行列の世界も、それはそれで面白そうだ。

2024-12-04　メルセンヌ数 M_p の p の話　遊びをせんとや生まれけむ

#遊びの数論　#メルセンヌ数

2³ = 2 × 2 × 2 = 8 のような数は「2 の累乗」とか「2 のべき（冪: ワかんむりに幕）」と呼ばれる。要するに 2ⁿ ――「2 の n 乗」――ってなわけ（n は自然数）。

このような数から 1 を引くと、時々「素数」（1 と自分自身でしか割り切れない数）になることがあって、
　　2³ − 1 = 8 − 1 = 7
　　2⁵ − 1 = 32 − 1 = 31
などは、その例。中には、
　　2¹²⁷ − 1 = 170澗（かん） 1411溝（こう） 8346穣（じょう） 0469𥝱（じょ） 2317垓（がい） 3168京 7303兆 7158億 8410万 5727
なーんていう39桁のでかい数も。これは20世紀中頃まで、人類が知ってる最大の素数だったそうだ。

このような 2ⁿ − 1 型の素数は「メルセンヌ素数」と呼ばれ、現在でもこのタイプが「知られている最大の素数」の世界記録となって、たぶんギネスブックにも載ってるのだろう。コンピューターを使って、今では39桁よりはるかに大きい素数が見つかっている。

2ⁿ − 1 が素数になるためには、必要条件として、指数の n 自身も素数でなければならない。上の例で 2 の肩に乗っている 3, 5, 127 は、実際どれも素数。なぜ n が素数以外だと駄目なのか？

0 以外の整数 1, 2, 3, ··· あるいは −1, −2, −3, ··· の中で 1 と −1 の二つは「基本単位」のような特別な性質を持っている。

例えば 1, 2, 3, 6 はどれも 6 を割り切るが、厳密に言えば −1, −2, −3, −6 も 6 を割り切る。では「6 は合計 8 個の約数を持つ」と言うべきだろうか。確かに正の約数と負の約数を別々に数えればそうだけど、 2 で割り切れる数が −2 でも割り切れること、 3 で割り切れる数が −3 でも割り切れることなどは、いちいち断るまでもない。この際「−1 倍の違いは無視。いちいち区別しない」とした方が、
　　6 の約数は 1, 2, 3, 6
と簡潔に表現でき、都合がいいような気がしないでもない。

さらに、
　　6 = 2 × 3
と分解されるが、分解の「部品」（素数）の中に 1 や −1 を含めると、
　　6 = 2 × 3 × (−1) × (−1) × 1
とも分解できるじゃないか、いやいや、
　　6 = (−2) × (−1) × 3
が正しい分解なのである、などと訳の分からないことになり、収拾がつかない。 1 と −1 の二つは、「部品」扱いしない方が話がすっきりする: 1 と −1 は、「素数」に含めず、素数の積から成る「合成数」にも含めない。名前が必要なときは「単数」と呼ぶ。

正の整数 1, 2, 3, ··· の範囲に限って、簡単にまとめると:
　　単数　1　＝　約数が 1 個（1 自身）
　　素数　2, 3, 5, 7, 11, ···　＝　約数が 2 個（1 と自分自身）
　　合成数　4, 6, 8, 9, 10, ···　＝　約数が 3 個以上

従って 1 番目のメルセンヌ数 2¹ − 1 = 2 − 1 = 1 は、素数ではない――まぁ、実用上、どっちでもいいことだが。

さて、メルセンヌ数 2^p − 1 を M_p と略すことにする（p は正の整数）。

最初の合成数は 4。そして 4 番目のメルセンヌ数 M₄ = 2⁴ − 1 = 16 − 1 = 15 は、素数ではない。自分自身と 1 以外の 3 や 5 でも割り切れて 15 = 3 × 5 と分解されるから。同様に、
　　M₆ = 2⁶ − 1 = 64 − 1 = 63 = 3 × 11
　　M₈ = 2⁸ − 1 = 256 − 1 = 255 = 3 × 5 × 17
　　M₉ = 2⁹ − 1 = 512 − 1 = 511 = 7 × 73
は、どれも、「合成数」番目のメルセンヌ数が素数でないことの実例。

では逆に、「素数」番目のメルセンヌ数は、素数だろうか？　最初の四つの素数 2, 3, 5, 7 で試すと···
　　M₂ = 2² − 1 = 4 − 1 = 3　素数
　　M₃ = 2³ − 1 = 8 − 1 = 7　素数
　　M₅ = 2⁵ − 1 = 32 − 1 = 31　素数
　　M₇ = 2⁷ − 1 = 128 − 1 = 127　素数
···どうやら答えは yes っぽい感じもするが、次の素数 p = 11 はどうか？
　　M₁₁ = 2¹¹ − 1 = 2048 − 1 = 2047

この 2047 という数が 3 や 5 や 11 で割り切れないことは一目で分かるし^†、 7 で割り切れないことも簡単に暗算できる^‡ので、「明らかに合成数」という証拠はないようだ。しかし「11 以下の素因数がない」というだけでは、まだ素数とは断定できない―― 13 や 17 や 19 など、もう少し大きい素数で割り切れる可能性もあるから。実は 2047 は 23 で割り切れる！
　　23 × 9 = 23 × 10 − 23 = 230 − 23 = 207
　　∴　23 × 90 = 2070
　　∴　23 × 89 = 2070 − 23 = 2047

†　桁の和が 3 の倍数のときに限って 3 で割り切れる。 2047 は (2+4) + 7 が 3 で割り切れないので駄目。このチェックでは、もともと 3 の倍数の桁（3, 6, 9）や、和が 3 の倍数になる桁がもしあれば、それらを 0 と見なしてもいい。「奇数番目の桁の和」と「偶数番目の桁の和」の差が 11 の倍数のときに限って 11 で割り切れる。 2047 の場合、 0+7 と 2+4 の差（1）は、この条件を満たさない。

‡　末尾 7 の 2047 が 7 で割り切れるとしたら、末尾を除去した 204 も 7 で割り切れる。しかし 204 = 4⋅51 は明らかに因子 7 を持たない。（普通に筆算方式で暗算しても同じ結論になる。）末尾ぶった切りの根拠は次の通り。もしも 2047 が 7 で割り切れれば、 2040 も 7 で割り切れる。 2040 は 10 の倍数なので、もしも同時に 7 の倍数だったら 2040 は 70 の倍数、だとしたら 204 は 7 の倍数（実際にはそうではない）。

実は、実際に割ってみなくても、 M₁₁ = 2047 が 23 で割り切れることは、予言可能。かなりマニアックな知識だが、参考までにそれを記すと:

チョコレート・ソフィーの法則　p を「4 の倍数より 1 小さい素数」とする（素数 p = 11 は、4 の倍数 12 より 1 小さいので、条件に当てはまる）。もし 2p + 1 も素数なら、 M_p は 2p + 1 で割り切れる（p = 11 のとき 2p + 1 = 23 も素数なので、 M₁₁ = 2047 は 23 で割り切れる）。［証明］

この 23 という素数をあらためて選び p = 23 とすると、それは 4 の倍数より 1 小さく、しかも 2p + 1 = 47 も素数なので、上記の法則が再び発動され、
　　M₂₃ = 2²³ − 1 = 8388607
は、 47 で割り切れる（商 178481 は素数）。

チョコレート・ソフィーは特殊な場合だが、それに限らず、一般論として p が素数だからといって M_p が素数になる保証はない。むしろ p が素数であっても M_p が素数になるということは、かなり珍しい。実は M_p が素数になるケースが無限にあるのかどうかも、たぶんまだ分かっていない。数論には、未解決の問題が多い…

他方、 p が合成数なら M_p も合成数（素数にならない）――ということなら、断言できる。証明は簡単で、次の形の恒等式に基づく。
　　x² − 1 = (x − 1)(x + 1)
　　x³ − 1 = (x − 1)(x² + x + 1)
　　x⁴ − 1 = (x − 1)(x³ + x² + x + 1)
　　x⁵ − 1 = (x − 1)(x⁴ + x³ + x² + x + 1)
　　···

一般に r を 2 以上の整数として、
　　A = x^r−1 + x^r−2 + x^r−3 + ··· + x² + x + 1　　《う》
を x − 1 倍すると、結果は A(x − 1) = Ax − A になる。これは A の x 倍から A 自身を引き算する、って意味だけど、 A の x 倍ってのは、 A の各項の指数がどれも 1 ずつ増えるってこと。
　　Ax = (x^r−1 + x^r−2 + x^r−3 + ··· + x² + x + 1)x
つまり:
　　Ax = x^r + x^r−1 + x^r−2 + ··· + x³ + x² + x　　《え》
《え》から《う》を引くと、《え》の右辺の x^r 以外の項は、全部消えてしまう――《う》の定数項 1 以外のどれかの項と等しいから。《う》の定数項 1 はどうなるか。《え》から《う》を引き算したのだから −1 となって残るだろう。要するに、《え》の x^r 以外の項は全滅し、それとは別に《う》に由来する定数項 −1 が残るので:
　　Ax − A = x^r − 1
　　∴　x^r − 1 = Ax − A = (x − 1)A　つまり
　　x^r − 1 = (x − 1)(x^r−1 + x^r−2 + ··· + x² + x + 1)　　《お》

今 r = 2, 3, 4 などとすれば、それぞれに対応して、上記 x² − 1 の展開、 x³ − 1 の展開、 x⁴ − 1 の展開などが、まとめて一挙に証明されたことになる。

で、まぁ、それがどうメルセンヌ数と関わってくるのか、っていうと…。

命題　p が合成数なら、メルセンヌ数 M_p は合成数。

証明　仮定により p は 1, p 以外の約数を持つ。その約数を q として p = qr とする（r は p を q で割った商）。このとき、
　　M_p = 2^p − 1 = 2^qr − 1 = (2^q)^r − 1
となるが、 2^q の値を x として、上記の恒等式《お》を使うと:
　　M_p = x^r − 1 = (x − 1)(x^r−1 + x^r−2 + ··· + x² + x + 1)
これは M_p が x − 1 = 2^q − 1 で割り切れることを意味している。仮定により q は 1 とも p とも異なる数なので、 2^q − 1 は M_p = 2^p − 1 自身ではなく、しかも 2¹ − 1 = 1 でもない。すなわち M_p は、自分自身とも 1 とも異なる約数を持つので、素数ではない。　∎

例1　p = 6 = 2 × 3 の場合（q = 2, r = 3）、 x = 2^q = 2² = 4 とすると:
　　M₆ = (2²)³ − 1 = 4³ − 1 = (4 − 1)(4² + 4 + 1) = 3 × 21
これは M₆ = 2⁶ − 1 = 64 − 1 = 63 が合成数である動かぬ証拠だ！
p = 6 = 3 × 2 とも書けるので q = 3, r = 2 としても良かった。その場合 x = 2³ = 8 となって:
　　M₆ = (2³)² − 1 = 8² − 1 = (8 − 1)(8 + 1) = 7 × 9
M₆ が素数でないことが、別の仕方で示された。

例2　p = 9 = 3 × 3 の場合（q = 3, r = 3）、 x = 2³ = 8 とすると:
　　M₉ = 8³ − 1 = (8 − 1)(8² + 8 + 1) = 7 × 73
M₉ = 511 が合成数であることが確かめられた。

問題1　p が偶数なら M_p は 3 で割り切れる。 p が 3 の倍数なら M_p は 7 で割り切れる。一般に p が q の倍数なら M_p は 2^q − 1 で割り切れる。

ヒント　x = 2^q を使う。

問題2　M₂₅ = 2²⁵ − 1 = 33554431 は素数か、合成数か？　もし合成数なら、1 と自分自身以外の約数を一つ見つけること。

33554431 は、下2桁を除けば、どれも偶数番目の桁の数とその右隣の桁の数が同じ（33, 55, 44）という特徴的な形を持つ。これは「偶然」の現象なのだろうが、この数だけが与えられた場合、それが素数かどうかは、にわかには明らかでない。しかし、これが M₂₅ だという認識があるなら、一つの約数は明らか。

関連して 2²⁵ + 1 = 33554433 は、さらにきれいな桁の配列を持つ。こいつが 11 で割り切れて商が 3050403 になることは一目瞭然だが、その商がさらに 3 で割り切れることも、一目瞭然だろう（3 の倍数でない桁の和 5 + 4 が 3 の倍数なので）。

すなわち、
　　2²⁵ − 1 = 33554431 = 31 × 1082401
　　2²⁵ + 1 = 33554433 = 3 × 11 × 1016801
という分解は機械的にできるのだが、それぞれの余因子（1082401 あるいは 1016801）が素数かどうか、つまりこれで分解完了なのかどうかは、一見しただけでは全く分からない。実は、前者は 601 × 1801 と分解され、後者は 251 × 4051 と分解される――これらの因子は、とうとう全部素数！

一般論として、素因数分解は、決して易しい問題ではない。このくらいの桁数なら、筆算でも試行除算が可能だし、コンピューターを使えば一瞬だが、桁数が 100 を超えるあたりから困難性が激増し、桁数が 1000 や 10000 のオーダーになると、現状、世界最強のスーパーコンピューターが束になっても、お手上げ。決して「計算が得意だから、素因数分解ができる」とか「数学は苦手だから、できない」とかの生易しい話じゃなく――トップレベルの研究者、最高レベルのコンピューターから見ても、事実上不可能なのだ、一般には。「素数ではない」と判定することはできても、「ではどういう約数があるのか」という当然の疑問に答えることができない。もどかしいっ！

でも、そうした難問題と関連して、その場しのぎにせよ巧妙なテクニックが幾つか発見され、少しずつ理論も発展を続けている。数論は深く、難しく、しかし美しい森。奥へ進めば限りがないけど、ほとんど誰もが、きっと自分に合った領域で遊ぶことができる――それは「四つの 4 を使って 24 を作る」（4 × 4 + 4 + 4）とか「四つの 4 を使って 25 を作る」みたいな、たわいもないパズルかもしれないけど、そのたわいもないことが多少の娯楽になるのなら、それはそれで良いことだろう。何の役にも立たないからこそ、純粋に楽しめる。

---