メモ（数論10）: 第三・第五補充法則 - 古風で優雅な珍品たち

チラ裏　＞　数論 i　＞　メモ10

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

• 2022-10-18　12k−1型（チョコ・ワッフル）素数の無限　ガウスの珍しい証明①
• 2022-10-19　チョコ・ミントとチョコ・ワッフル　次回予告
• 2022-10-21　12k+7型（チョコ・ミント）素数の無限　ガウスの珍しい証明②
• 2022-10-25　第三補充法則の完成　ガウスの珍しい証明③
• 2022-10-29　バニラ・ミントはバッハの調べ　12k+1型素数の無限
• 2022-12-30　バニラ・ワッフル　12k+5型素数の無限
• 2022-12-15　第五補充法則 Part 1　手品！
• 2022-12-12　第五補充法則 Part 2　A型奇数とB型奇数
• 2022-12-24　第五補充法則 Part 3　末尾1の素数たち
• 2022-11-07　第五補充法則 Part 4　より精妙な技法
• 2022-12-18　4x⁴ + 4x³ + 4x² + 4x + 4 などの変形　実践的アプローチ

2022-10-18　12k−1型（チョコ・ワッフル）素数の無限　ガウスの珍しい証明①

今日も気晴らしに、初等整数論で遊びましょう！

知っている？　素数にはいろんな香りがあることを…
　　　「13」はバニラ…　バニラ・ミント
　　　「11」はチョコレート…　チョコ・ワッフル
　テストじゃないのよ　あなたのイメージで…見ないでほしい
　　　素数は　ふしぎなお菓子なの

12の倍数（12, 24, 36, 48, 60, 72, …）から 1 を引いたものは、結構よく素数になるような感じがする:
　　11, 23, 35, 47, 59, 71, …　←　この6個の中では35以外、全部素数

けれど、必ず素数になるわけでもない。
　　「12の倍数マイナス1」が合成数になる例　35, 95, 119 (=7 × 17), 143 (=11 × 13), 155, …

では「12k−1型」の素数は無限に存在するのだろうか？

12の倍数は偶数で、しかも3の倍数なので、そこから 1 を引けば奇数で、しかも3の倍数と1ずれた数になる。だから「12の倍数マイナス1」の中には、2の倍数・3の倍数が入ってない。でも世の中には、5の倍数・7の倍数…など無限種類の倍数がある。「2の倍数・3の倍数が入っていない」というだけでは、「そこに素数が無限にある」とは言い切れない。

――この素朴な疑問は、次の（一見まるで無関係な）問題と関係している。

問題　5以上の素数 p が与えられたとき、その p に対して x² ≡ 3 (mod p) を満たす解 x があるか、ないか？

上記の問題は、相互法則を使えば簡単だけど、相互法則を使わずに直接検討することもできる。直接的アプローチは面白い。ガウスによるこの議論は、現代の教科書には載ってないし、ディリクレの整数論講義でも省略されている。それを3回くらいに分けて、研究してみたい。

〔参照〕　Gauß, DA, artt. 117–120。便宜上、ガウスの説明とは逆に、第118節を先に【1】で紹介して、第117節を後から【3】で紹介する。本来の順序に従って【3】を先に読んだ方が分かりやすいかもしれない。

【1】　5以上の素数は、12の倍数との関係では、12k±1型、12k±5型の4種類の分類できる。今回は、12k±5型の素数を問題にする（DA 118）。感覚的には「8k±3型の素数を法として2が非剰余」ということと、似ている。ガウスは「同様に証明できるので、われわれは面倒を省く」と書いているが、ガウスの方法は恐らく次のようなものだろう。

証明を分かりやすくするため、先に二つのことを観察しておく。

「観察1」　mod 12 では 5 の逆数（掛けると 1 になる相手）は 5 自身で、−5 の逆数は −5 自身。

実際 5 × 5 = 25 ≡ 1 (mod 12) になる。(−5) × (−5) = 25 ≡ 1 (mod 12) でもある。

このことから、例えば a ≡ ±5 (mod 12) のとき、もし ab ≡ 1 (mod 12) なら b ≡ ±5 (mod 12) となる（複号同順）。同様に、a ≡ ±5 (mod 12) のとき、もし ab ≡ −1 (mod 12) なら b ≡ ∓5 (mod 12) となる（複号同順）。例えば a = 5, b = −5 なら ab = −25 ≡ −1 (mod 12)。

「観察2」　「12k+5型または12k−5型」の数は、必ず「12k+5型または12k−5型」の素因数を少なくとも一つ持つ。

〔例1〕　72 は12の倍数だから 72 + 5 = 77 は12k+5型。そして 77 = 7 × 11 の素因数のうち 7 は12k−5型。

〔例2〕　24 は12の倍数だから 24 + 5 = 29 は12k+5型。この場合 29 自身が素数（29の素因数）で、12k+5型。

〔例3〕　1224 は12の倍数だから 1224 − 5 = 1219 は12k−5型。そして 1219 = 23 × 53 の素因数のうち 53 は12k+5型。

こうなる理由。12k ± 5 は奇数なので 2 では割り切れない。12k ± 5 は、3の倍数「12k ± 3」と ±2 ずれてるので、3 でも割り切れない。従って、12k ± 5 型の数 N の素因数は、5以上に限られるが、5以上の素数は 12k±1型、12k±5型のいずれか。ところが 12k±1型の素数――つまり ≡ ±1 (mod 12) の数――を何個掛け合わせても、≡ ±1 (mod 12) にしかならない。N は ≡ ±5 (mod 12) なので、それを作るためには、12k±5型の素因数がどうしても必要。

別の言い方をすると…。ある数 N について N ≡ ±5 (mod 12) が成り立つとき、その数 N は、q ≡ ±5 (mod 12) を満たす素因数 q を持つ（N 自身が素数 q という場合もある）。

☆　ここからが本題　☆

定理1　p が12k±5型の素数なら x² ≡ 3 (mod p) は解を持たない。

証明　x² ≡ 3 (mod p) が解 x を持つような、12k±5型の素数 p が存在する…と仮定して矛盾を導く。x² ≡ 3 (mod p) が解を持つような、最小の12k±5型素数を p としよう。

仮定により、この p に対して、x² ≡ 3 (mod p) を満たす x が存在。そのような x のうち、2 以上 p 未満の偶数を x = e とすると:
　　e² ≡ 3 (mod p)
つまり整数 f が存在して
　　『あ』　e² − 3 = pf
を満たす。e は偶数なので、左辺は奇数、従って f は奇数。e の値の範囲から、f は p 未満の正の奇数。

mod p の世界には 0, 1, 2, …, p−1 の p 種類の数しかない: x² ≡ 3 (mod p) に解があるなら、その範囲に解がある。x ≡ a が解なら、x ≡ −a ≡ p−a も解。もし a が偶数ならそれを e とし、a が奇数なら p−a（奇数引く奇数なので偶数）を e とすればいい。p ≥ 5 なので 0² ≡ 3 は不成立。だから e は 2 以上、『あ』の値は 2² − 3 = 1 以上で正。一方、『あ』左辺は p² − 3 未満なので p² 未満、それと等しい右辺 pf も p² 未満なので f は p 未満の正の数。

e は偶数なので、6n ± 2 の形、または 6n の形のいずれかを持つ。　← この場合分けが好手（ガウスDA 117）

第一に、e = 6n ± 2 なら e² = 36n² ± 12n + 4 ≡ 4 (mod 12) なので、『あ』を mod 12 で考えると:
　　4 − 3 ≡ pf　つまり　pf ≡ 1 (mod 12)
仮定により p ≡ ±5 (mod 12) なので、「観察1」から f は ≡ ±5 (mod 12)。従って「観察2」から f は12k±5型の素因数 q を持つ。『あ』を mod q で考えると:
　　e² − 3 ≡ 0　つまり　e² ≡ 3 (mod q)
これは「x² ≡ 3 (mod p) が解を持つような、最小の12k±5型素数は p」という仮定に矛盾する（なぜなら f は p 未満の正の数であり、f の因数 q は p より小さい）。

第二に、e = 6n なら e² = 36n² なので、『あ』はこうなる:
　　『い』　36n² − 3 = pf
この左辺は 3 で割り切れるので、それと等しい右辺 pf も 3 で割り切れるが、p は5以上の素数なので 3 では割り切れない。従って f が 3 で割り切れ、f/3 は整数。『い』の両辺を 3 で割ると:
　　12n² − 1 = p(f/3)
これを mod 12 で考えると:
　　0 − 1 ≡ p(f/3)　つまり　p(f/3) ≡ −1 (mod 12)
すなわち mod 12 において f/3 は、p ≡ ±5 の逆数の −1 倍。「観察1」から f/3 ≡ ∓5 (mod 12)。「観察2」から、整数 f/3 は12k±5型の素因数 q を持ち、第一の場合と同様、矛盾が生じる（f/3 < f < p なので f/3 の素因数 q は p より小さい）。□

〔コメント〕　技術的な理由で e, f が3で割り切れるかどうかの場合分けが生じる。e が偶数、e² が4の倍数なので『あ』を mod 4 で考えるのが自然なようだが（そして『あ』を mod 3 でも考えれば、mod 12 の議論が成立するのだが）、それだと遠回りになる（末尾の付録参照）。

巨匠ガウスの感覚　偶数が平方されるとき、mod 4 は平凡。偶数を mod 6 で 0 or ±2 に分類せよ。3 で割り切れるかどうかが絡むなら、なおさら。

【2】　この件に関するガウスの指摘はここまでだが、この議論を応用すると12k−1型素数が無限に存在することをエレガントに証明できる！

補題1　x² − 3 が 5 以上の素数 p で割り切れるなら、その p は12k±5型ではあり得ない。

証明　もしも p が12k±5型だとすると、x² − 3 ≡ 0 (mod 12k±5) となるが、それが不可能なことは、定理1の通り。□

補題2　12k+1型の数を何個掛け合わせても、12k−1型の数を作れない。

証明　12k+1型の数は ≡ +1 (mod 12) であり、12k−1型の数は ≡ −1 (mod 12) である。前者の型の数を何個掛け合わせても結果は ≡ +1 (mod 12) で、後者の型にならない。□

定理2　12k−1型の素数は無限個、存在する。

証明　12k−1型の素数が有限個（m 個）しかないと仮定して、それらを
　　S = {p₁, p₂, …, p_m}
とする。11 や 23 は12k−1型素数なので、S は空集合ではない。今、
　　A = p₁p₂…p_m
と置くと、p₁, p₂ などはどれも ≡ −1 (mod 12) なので A ≡ (−1)^m ≡ ±1 (mod 12) は、12の倍数±1。そこで A = 12u ± 1 とすると:
　　A² = (12u ± 1)² = 12²u² ± 24u + 1 = 24(6u² ± u) + 1
両辺から 3 を引くと:
　　『う』　A² − 3 = 24(6u² ± u) − 2

補題1により、『う』の整数は、12k±5型の素因数を持たない。

『う』右辺は、明らかに 2 で割り切れる。それと等しい『う』左辺も、もちろん 2 で割り切れる。そこで『う』の両辺を 2 で割ると:
　　『え』　(A² − 3)/2 = 12(6u² ± u) − 1

『え』左辺の整数 (A² − 3)/2 を B とすると、『え』右辺から分かるように B は12k−1型で、従って 2 でも 3 でも割り切れない。しかも B は、
　　「12k±5型の素因数を持たない『う』の数」の約数（2 で割ったもの）
なので、依然として12k±5型の素因数を持たない。つまり B = (A² − 3)/2 の素因数は「12k+1型または12k−1型」に限られる。

ところが補題2から、「12k+1型素数だけ」を掛け合わせても、12k−1型の整数 B を作れない。だから、B は「12k−1型」の素因数を少なくとも一つ含む。そのような素因数（複数ある場合はそのうちの任意の一つ）を q としよう: q は B = (A² − 3)/2 の約数だから、2B = A² − 3 も q で割り切れる。他方、集合 S に含まれるどの素数 p を考えても、A は p の倍数なので A² も p の倍数: p の倍数より 3 小さい A² − 3 は、p では割り切れない（p は12k−1型素数なので 11 以上）。

要するに、素数 q は A² − 3 の約数だが、素数 p はそうではない。

だから、12k−1型の素数 q は、集合 S に含まれるどの素数 p とも異なる。すなわち「12k−1型素数が有限個しかない」という最初の仮定は誤りで、どのような有限集合を考えても、必ず「そこに含まれてない別の12k−1型素数」が存在する。□

〔例1〕　12k−1型素数が {11, 23} だけだと仮定。A = 11 × 23 = 253（これは 12u + 1 の形: u = 21）。 A² − 3 = 2 × 32003。 B = 32003。この B はそれ自身が素数: その素因数 q = B = 32003 は12k−1型。

〔例2〕　12k−1型素数が {11, 23, 47} だけだと仮定。A = 11 × 23 × 47 = 11891（これは 12u − 1 の形: u = 991）。 A² − 3 = 2 × 13² × 418331。 B = 13² × 418331。B は12k−1型で、素因数 q = 418331 は12k−1型。

12k−1型素数についての上記の証明法は、8k−1型素数についての証明法（第二補充法則【6】）と平行的。ちなみに全くどーでもいいことだが、「12k−1型素数」の愛称は「チョコ・ワッフル素数」または「霜月（しもつき）素数」。愛称の一つは、旧暦の月の名から。

2022-10-19　チョコ・ミントとチョコ・ワッフル　次回予告

「チョコレート素数」というのは、4で割ると 3 余る素数（3, 7, 11, 19など）の愛称。4の倍数より 1 小さいともいえる。対比的に、4の倍数より 1 大きい素数（5, 13, 17など）を「バニラ素数」と呼ぶ。「バニラ」と「チョコレート」は、4で割った余りによる分類だ。

それとは別に、3で割った余りによる分類も考えられる: 3の倍数より 1 大きい場合を「ミント」、1 小さい場合を「ワッフル」という。

12 で割った余りで考えると: 余り 1, 5, 9 がバニラ、余り 3, 7, 11 がチョコレートだが、実際には余り 1 or 5 がバニラ、余り 7 or 11 がチョコレートと考えていい。

なぜなら、12の倍数より 3 または 9 大きい数は 3 で割り切れるので、3 自身を別にすれば、素数ではない。

「チョコ・ミント」は 12 で割った余りが 7 の場合、「チョコ・ワッフル」は 12 で割った余りが 11 の場合（前者は 3 の倍数より 1 大きく、後者は 3 の倍数より 1 小さい）。

前回は、チョコ・ワッフル素数が無限に存在することを証明した。今度は「チョコ・ミント素数が無限に存在すること」を示したい。

まず、p を 5 以上の素数として、次の定理を証明する: p がワッフル素数のとき x² ≡ −3 (mod p) は解を持たない（言い換えると、この2次式が解を持つのは p がミント素数の場合に限られる）。

この定理自体は難しくない。ガウスの DA 117 に直接的な証明が掲載されていて、前回の内容とペアになる。それはいいのだが、問題は「この定理から、どうやってチョコ・ミント素数の無限を導くか」。いったんは「この方法では無理かも？」と諦めかけた。−3 が mod p で「平方剰余になるか非剰余になるか」の区別は「p がミントかワッフルか」の区別なので、本質的には mod 3 での分類。mod 12 での細かい分類のためには、解像度が足らないのでは…。

けれど、次のアイデアを思い付いた！

チョコ・ミント素数（≡ 7 mod 12）が有限個しかないと仮定して、それを S = {p₁, p₂, …, p_m} とし、
　　A = p₁p₂…p_m
と置く。ここで B = (2A)² + 3 という数を考える。上の定理を使って、次のことが示される: B の素因数は、どれも ≡ 1 or 7 (mod 12) の形を持つ。

もしも B の素因数がどれもこれも ≡ 1 (mod 12) なら、それらの積である B 自身も B ≡ 1 (mod 12) になってしまう。ところが、チョコ・ミント素数の平方は ≡ 7² ≡ 49 ≡ 1 (mod 12) なので:
　　A² = p₁²p₂²…p_m² ≡ 1 × 1 × … × 1 ≡ 1 (mod 12)
　　だから実際には　B = 4A² + 3 ≡ 7 (mod 12)
従って「もしも」は無理な仮定。B は必ず ≡ 7 (mod 12) の型の素因数 q を少なくとも一つ持つ。

S に含まれる任意の素数 p について、B は p の倍数より 3 大きいので、p では割り切れない。一方、q は B の素因数なので、B は q で割り切れる。だから q は、S に含まれるどの素数とも異なるチョコ・ミント素数。

2022-10-21　12k+7型（チョコ・ミント）素数の無限　ガウスの珍しい証明②

【3】　「6k+5型」の素数（6で割ると5余る）――言い換えれば「6k−1型」の素数（6の倍数より1小さい）――を考える:
　　5, 11, 17, 23, 29, 41, 47, …

以下の議論は、前回の【1】とほとんど同じ（Gauß, DA 117）。話をスムーズに進めるため、ここでもまず二つのことを観察しておく。

「観察3」　mod 6 では −1 の逆数（掛けると 1 になる相手）は −1 自身。

(−1) × (−1) = 1 なのは当たり前。「マイナスかけるマイナスの計算は嫌いなんだよ～」という方は −1 ≡ 5 (mod 6) なので、5 × 5 = 25 ≡ 1 (mod 6) と考えてもいい。

このことから、例えば a ≡ −1 (mod 6) のとき、もし ab ≡ 1 (mod 6) なら b ≡ −1 (mod 6) となる。

「観察4」　6k−1型の自然数は、必ず同じ型の素因数を少なくとも一つ持つ。

〔例1〕　36 は6の倍数だから 35 は6k−1型。そして 35 = 5 × 7 の素因数のうち、5 は6k−1型。

〔例2〕　42 は6の倍数だから 41 は6k−1型。41 は素数なので、41自身がその素因数（もちろん6k−1型）。

〔例3〕　120 は6の倍数だから 119 は6k−1型。そして 119 = 7 × 17 の素因数のうち 17 は6k−1型。

こうなる理由。6k − 1 は奇数なので 2 では割り切れないし、（6k は3の倍数で、それと −1 ずれてるので）3 でも割り切れない。従って、6k − 1 型の数 N の素因数は5以上に限られるが、5以上の素数は 6k+1型、6k−1型 のいずれか。ところが 6k+1型の素数――つまり ≡ +1 (mod 6) の数――を何個掛け合わせても、≡ +1 (mod 6) にしかならない。N は ≡ −1 (mod 6) なので、それを作るためには、6k−1型の素因数がどうしても必要。

別の言い方をすると…。ある数 N について N ≡ −1 (mod 6) が成り立つとき、その数 N は、q ≡ −1 (mod 6) を満たす素因数 q を持つ（N 自身が素数 q という場合もある）。

定理3　p が6k−1型の素数なら x² ≡ −3 (mod p) は解を持たない。

証明　x² ≡ −3 (mod p) が解 x を持つような、6k−1型の素数 p が存在する…と仮定して矛盾を導く。x² ≡ −3 (mod p) が解を持つような、最小の6k−1型素数を p としよう。

仮定により、この p に対して、x² ≡ −3 (mod p) を満たす x が存在。そのような x のうち、2 以上 p 未満の偶数を x = e とすると:
　　e² ≡ −3 (mod p)
つまり整数 f が存在して
　　『か』　e² + 3 = pf
を満たす。e は偶数なので、左辺は奇数、従って f は奇数。e の値の範囲から、f は p 未満の正の奇数。

〔解説〕　e は p 未満、つまり p−1 以下なので、『か』左辺は、次の数以下:
　　(p−1)² + 3 = p² − 2p + 1 + 3 = p² + (4 − 2p)　★
ここで p は6k−1型の素数なので 5 以上、だから 4 − 2p = 2(2 − p) は負。従って ★ の数は p² より小さく、要するに『か』左辺は p² 未満。左辺に等しい『か』右辺 pf も p² 未満。だから f は p 未満。

さて e は偶数なので、e ≡ ±2 または e ≡ 0 (mod 6)。

第一に、e ≡ ±2 なら e² ≡ 4 (mod 6) なので、『か』を mod 6 で考えると:
　　4 + 3 ≡ pf　つまり　pf ≡ 1 (mod 6)
仮定により p ≡ −1 (mod 6) なので、「観察3」から f は ≡ −1 (mod 6)。従って「観察4」から f は6k−1型の素因数 q を持つ。『か』を mod q で考えると:
　　e² + 3 ≡ 0　つまり　e² ≡ −3 (mod q)
これは「x² ≡ −3 (mod p) が解を持つような、最小の6k−1型素数は p」という仮定に矛盾する（なぜなら f の因数 q は p より小さい）。

第二に、e ≡ 0 (mod 6) なら e = 6n と置くと、『か』はこうなる:
　　『き』　36n² + 3 = pf
この左辺は 3 で割り切れるので、それと等しい右辺 pf も 3 で割り切れるが、p は5以上の素数なので 3 では割り切れない。従って f が 3 で割り切れ、f/3 は整数。『き』の両辺を 3 で割ると:
　　12n² + 1 = p(f/3)
これを mod 6 で考えると:
　　0 + 1 ≡ p(f/3)　つまり　p(f/3) ≡ 1 (mod 6)
仮定により p ≡ −1 なので、「観察3」から f/3 ≡ −1 (mod 6)。従って「観察4」から、整数 f/3 は6k−1型の素因数 q を持ち、第一の場合と同様、矛盾が生じる。□

【4】　6k−1型素数は、12の倍数との関係では、次の二つのグループに分けられる。

バニラ・ワッフル素数　12k+5型（6の奇数倍より1小さい）

5, 17, 29, 41, …

チョコ・ワッフル素数　12k−1型（6の偶数倍より1小さい）

11, 23, 47, 59, …

ここで「バニラ」とは「4で割ると1余る」という意味、「チョコレート」略して「チョコ」とは「4で割ると3余る」という意味。「ワッフル」は「3で割ると2余る」という意味。

「ワッフル」は「ミント」（3で割ると1余る）と対になる。これらは便宜上の勝手な愛称であり、正式な用語ではないのだが、概念の整理や、簡潔な表現のために役立つことがある。

「ある整数 D が mod p において平方剰余か非剰余か」という区別を平方性と呼ぶことにすると、p がバニラなら D の平方性と −D の平方性は一致し、p がチョコなら D の平方性と −D の平方性は逆になる（この件については、第二補充法則【11】【12】に詳しい説明がある）。もっとも D = 0 なら D = −D となって例外的事態が発生するが、今は ±3 を考えているので、そんな特殊ケースは関係ない…。んでもって、定理3によれば、−3 の平方性は、p がバニラ・ワッフルでもチョコ・ワッフルでも「非剰余」。このことから +3 の平方性は、p がバニラ・ワッフルなら同じ「非剰余」だが、p がチョコ・ワッフルなら逆に「平方剰余」になる。

〔バニラ・ワッフル素数の例として 5 を考えると〕　x² ≡ −3 (mod 5) も x² ≡ 3 (mod 5) も解を持たない（バニラなので、両者の平方性が同じ）。実際 mod 5 での平方剰余は 0 を別にすれば (±1)² ≡ 1 ≡ −4 と (±2)² ≡ 4 ≡ −1 に限られる。

〔チョコ・ワッフル素数の例として 11 を考えると〕　x² ≡ −3 (mod 11) は解を持たないが（定理3）、x² ≡ 3 (mod 11) は解を持つ。実際 mod 11 での平方剰余は 0 を別にすれば…
　　(±1)² ≡ 1 ≡ −10, (±2)² ≡ 4 ≡ −7, (±3)² ≡ 9 ≡ −2
　　(±4)² ≡ 16 ≡ 5 ≡ −6, (±5)² ≡ 25 ≡ 3 ≡ −8
…であり、前者に解はなく、後者には x ≡ ±5 という解がある。チョコなので、両者の平方性が逆。

12k+5型（＝12k−7型）の素数（バニラ・ワッフル）を法として 3 で非剰余であることは、定理1として既に直接証明済みだが、12k−1型の素数（チョコ・ワッフル）を法として 3 が平方剰余になることは、新事実。他方、定理1によれば、12k−5型（＝12k+7型）素数（チョコ・ミント）を法とすると 3 が非剰余なので、この型の素数に対しては −3 は（法がチョコなので平方性が逆になって）平方剰余となる。

〔チョコ・ミント素数の例として 7 を考えると〕　x² ≡ −3 (mod 7) は解を持たないが（定理1）、x² ≡ 3 (mod 7) は解を持つ。実際 mod 7 では (±1)² ≡ 1 ≡ −6 と (±2)² ≡ 4 ≡ −3 と (±3)² ≡ 2 ≡ −5 が平方剰余であり、前者には解がないが、後者には x ≡ ±2 という解がある。チョコなので、平方性が逆。

±3の平方性

↓mod	3	−3	modの種類
12k+1	？	？	バニラ
12k+7	非剰余	平方剰余	チョコ
12k−7	非剰余	非剰余	バニラ
12k−1	平方剰余	非剰余	チョコ

mod 12k+1 で何が起きるかは（このメモ内では）未証明だが（次回のお楽しみ？）、属性がバニラなので、二つの「？」は一致する。対称性や、第二補充法則（下記）との類似性から、二つの「？」は「平方剰余」になると予想される。

±2の平方性

↓mod	2	−2	modの種類
8k+1	平方剰余	平方剰余	バニラ
8k+3	非剰余	平方剰余	チョコ
8k−3	非剰余	非剰余	バニラ
8k−1	平方剰余	非剰余	チョコ

このような検討や直接証明は、平方剰余の相互法則が確立していなかった時代の「アンティック」で^*1、現代の数論ではほとんど取り上げられない（そこがむしろ新鮮で面白い）。時代の境目の Gauß はこれを取り上げているが^*2、Dirichlet は既に「±3の平方性」の議論を省いている。現代では「+2の平方性」（第二補充法則）だけが取り上げられ、「−2の平方性」は第一補充法則の自明な系と見なされる。

*1　Euler: [E272] Supplementum quorundam theorematum arithmeticorum, quae in nonnullis demonstrationibus supponuntur (1763, written 1759?): Novi Commentarii academiae scientiarum Petropolitanae, Vol. 8, pp. 105–128
https://scholarlycommons.pacific.edu/euler-works/272/

*2　Gauß が「−2の平方性」を検討している一つの背景として、相互法則の第一証明には第二補充法則が必要で、それを導くために「−2の平方性」が使われている。

【5】　ガウスの議論からは脱線するが、これを利用して、以下の魅惑的な事実が得られる。

補題3　x² + 3 の 5 以上の素因数 q は、12k+1型または12k+7型に限られる。

証明　x² + 3 ≡ 0 つまり x² = −3 (mod q) が成り立つなら、q はワッフル素数ではないから（定理3）、ミント素数。□

定理4　「12k+7型」素数――すなわち、6の奇数倍より1大きい素数（7, 19, 31, etc.）――は、無限に存在する。

〔注意〕　「12k+7型」は「12k−5型」ともいえる。ミント素数（3k+1型）が無限に存在することは、既に分かっている。ミント素数は全て6k+1型でもあるので、6の倍数より1大きい素数は無限に存在する。ところが、それを「6の偶数倍より1大きい素数」（12k+1型＝バニラ・ミント）と「6の奇数倍より1大きい素数」（12k+7型＝チョコ・ミント）に細分しても、どちらの種類の素数も、なお無限に存在する…。ここでは、そのうち後者が無限にあることを証明する。これについても、もっと一般的な事実が証明されているのだから、個別的ケースについて考えるのは「無駄」かもしれないが、どんなことでも、どうせなら楽しもう！

証明　12k+7型素数が有限個で S = {p₁, p₂, …, p_m} の m 個だけだと仮定する。

それらの積を A = p₁p₂…p_m として B = (2A)² + 3 と置くと、補題3によって B の素因数は、12k+1型または12k+7型に限られる（B の素因数は 5 以上。なぜなら B は奇数なので 2 で割り切れず、A は 3 で割り切れないので B も 3 で割り切れない）。

p₁, p₂ などはいずれも ≡ 7 (mod 12) なので、その平方はいずれも ≡ 7² ≡ 1 (mod 12)、従って:
　　A² = p₁²p₂²…p_m² ≡ 1 × 1 × … × 1 ≡ 1
　　B = 4A² + 3 ≡ 4 + 3 ≡ 7 (mod 12)
つまり B は12k+7型の奇数。

もしも B の素因数がすべて12k+1型なら、B も同じ型になるが、それは上記の事実に反し不合理。従って B は12k+7型の素因数を少なくとも一つ持つ。q をそのような素因数（複数あるなら、そのうちの任意の一つ）とすると、B は q で割り切れるが、S に含まれるどの素数 p を考えても、B は p の倍数より3大きいので、B は p では割り切れない。すなわち q は S に含まれていない12k+7型素数。□

〔例1〕　12k+7型素数が {7, 19} だけと仮定。A = 7 × 19 = 133, B = (2 × 133)² + 3 = 70759。この B = 70759 は12k+7型の奇数で B = 13 × 5443 と素因数分解される。このうち 5443 は12k+7型素数。

〔例2〕　12k+7型素数が {7, 19, 31} だけと仮定。A = 7 × 19 × 31 = 4123, B = (2 × 4123)² + 3 = 67996519。この数は、それ自身12k+7型素数。

2022-10-25　第三補充法則の完成　ガウスの珍しい証明③

【6】　5 以上の任意の素数 p が与えられたとき、x² ≡ 3 や x² ≡ −3 (mod p) に解があるかないか？

前者の解の有無（「平方性」）・後者の解の有無（「平方性」）は、p を4で割った余りが 1（バニラ）なら一致し、3（チョコレート）なら逆になる（【4】参照）。だから、どちらか片方だけでも判定できれば、自動的に両方とも判定できる。p が12k+5型、12k+7型、12k+11型の場合に関しては、+3 と −3 の両方について結論が出ている。残った問題は、法が12k+1型（バニラ・ミント）素数の場合。第二補充法則の8k+1型（春素数）のケースと似た話になる。

ガウス自身の議論は、およそ次の通り（DA 119）。 p を12k+1型（バニラ・ミント）に限らず、より一般的に3k+1型（ミント素数）とする。フェルマーの小定理から、任意の a について a^p−1 ≡ 1 (mod p) だが（ただし a は p の倍数以外）、p = 3k+1 なので p − 1 = (3k+1) − 1 = 3k は 3 で割り切れる。従って、位数 3 の a が存在する。

〔解説〕　位数 3 の a とは、「3乗すると ≡ 1 になるが、1乗や2乗しても ≡ 1 にならないような数」。そのような a が存在することは、ガウスの DA 54 で証明されている―― DA 54 については別のメモで詳しく紹介しているが、以下のように考えれば（それほどエレガントではないものの）結論自体は容易に理解可能。

フェルマーの小定理によれば…
　　『さ』　y^p−1 ≡ 1　つまり　y^p−1 − 1 ≡ 0 (mod p)
…は p−1 種類の解 y ≡ 1, 2, 3, …, p−1 を持つ。p−1 = 3k なので:
　　『し』　y^3k − 1 ≡ 0　つまり　(y³)^k − 1 ≡ 0 (mod p)
今 y³ ≡ z と置くと:
　　『す』　z^k − 1 = (z − 1)(z^k−1 + z^k−2 + … + 1) ≡ 0 (mod p)

z についてのk次方程式『す』は、最大で k 種類の解を持ち、その k 種類の解の一つ一つについて、3次方程式 y³ ≡ z は最大3種類の解を持つ。従って『し』は y について最大 3k 種類の解を持つのだが、『し』すなわち『さ』は、上述のように実際 3k = p−1 種類の解を持つ。つまり、この「最大限度・目いっぱいの解」のケース。だから『す』は k 種類の解を持ち、そのためには
　　『せ』　z − 1 ≡ 0 (mod p) が 1 種類の解を持ち、
　　『そ』　z^k−1 + z^k−2 + … + 1 ≡ 0 (mod p) が k−1 種類の解を持つ。
『せ』についての事実から（y³ ≡ z と置いたのだから）…
　　y³ − 1 ≡ 0　つまり　y³ ≡ 1 (mod p)
…は、目いっぱいの 3 種類の解を持つ。その3解を y ≡ u, v, w とでもしよう。y ≡ 1 は明らかに y³ ≡ 1 の解なので、解 y ≡ u, v, w の一つは ≡ 1。仮に u ≡ 1 とすると、もちろん u¹ ≡ 1 なので u の位数は 1 であり、当たり前だが、1 は「3乗すると ≡ 1」という条件をちゃんと満たす。一方、v と w もそれぞれ3乗すると ≡ 1 なので、その位数は 3 の約数（つまり 1 or 3）だが、もはや位数 1 ということはあり得ない。なぜなら、もしも例えば v¹ ≡ 1 なら u¹ ≡ v¹ ≡ 1 となり、要するに u ≡ v ≡ 1 となってしまい、「u, v, w は不合同（種類が異なる）」という前提に反する。同様に w の位数も 1 ではない: v と w は位数 3。

〔参考〕　代わりに mod p の原始根の一つを g としてもいい: g^p−1 ≡ 1 だが、p−1 = 3k は 3 で割り切れるので、v ≡ g^(p−1)/3 と置けば、直ちに位数 3 の元 v が得られる（v³ ≡ g^p−1 ≡ 1）。ちなみに w ≡ v² ≡ g^2(p−1)/3 も位数 3（実際 w³ ≡ v⁶ ≡ (v³)² ≡ 1）。

いずれにせよ、位数 3 の元 v が存在するので、v³ ≡ 1 (mod p)、従って:
　　v³ − 1 ≡ 0　つまり　(v − 1)(v² + v + 1) ≡ 0 (mod p)
これは (v − 1)(v² + v + 1) が p で割り切れることを含意するが、v ≢ 1 なので（なぜなら v の位数は 1 ではない）、v − 1 ≢ 0 (mod p) であり、因子 v − 1 は p で割り切れない。必然的に、もう一方の因子 v² + v + 1 が p で割り切れる。従って、それを 4 倍した 4(v² + v + 1) も p で割り切れる^*3:
　　4v² + 4v + 4 ≡ 0　つまり　4v² + 4v + 1 ≡ −3 (mod p)
　　つまり　(2v + 1)² ≡ −3 (mod p)
すなわち x² ≡ −3 (mod p) は x ≡ 2v + 1 という解を持ち、−3 は平方剰余。次の定理が証明された。

定理5　3k+1型の任意の素数 p を法として −3 は平方剰余。

〔例〕　p = 7 は 3k+1型素数。 v = 2 は v³ = 8 ≡ 1 (mod p) を満たすが、v¹ = 2 ≢ 1 なので位数3。このとき x ≡ 2v + 1 = 5 は x² ≡ −3 (mod p) の解。実際、5² = 25 = 7 × 4 − 3 ≡ −3 (mod 7)。

*3　一般に p が3以上の素数のとき、xⁿ − 1 = (x − 1)(xⁿ⁻¹ + xⁿ⁻² + … + x + 1) の丸かっこ内の p−1 次式の4倍を、次の形に変形できる:
　　4X = Y² ∓ pZ²　（複号では p が4k+1型なら上、4k+3型なら下を選択）
この場合、p = 3, X = x² + x + 1, Y = 2x + 1, Z = 1 に当たる（Gauß, DA 357）:
　　4(x² + x + 1) = (2x + 1)² + 3⋅1²

【7】　自然数 k = 2n が偶数の場合、「3k+1型」素数は「6n+1型」素数になるが、実は「3k+1型」素数と「6n+1型」素数（あるいは n をあらためて k として「6k+1型」素数）は、完全に同じ対象を指す。というのも、もしも「3k+1型」で k が奇数（1, 3, 5, …）だと、「3k+1」は 4, 10, 16, … の偶数になってしまい、素数になり得ない。要するに「3k+1型の素数」という表現では、暗黙に k が偶数であることが含意されている。

他方、この「6n+1型」素数の n は偶数にも奇数にもなり得る。

「6n+1型」の n が偶数なら 13, 37 のような「12k+1型」素数になる（偶数 n をあらためて 2k と置いた）。

「6n+1型」の n が奇数なら 7, 19, 31 のような「12k+7型」素数になる（奇数 n をあらためて 2k+1 と置いた）。

どちらについても、3で割って1余ること――あるいは6で割って1余ること――には変わりなく、すなわち「3k+1型」なので、これらの素数を法として −3 は平方剰余（定理5）。他方 +3 に関しては、バニラ素数の一種「12k+1型」を法とする場合には同じく平方剰余になるものの、チョコ素数の一種「12k+7型」を法とする場合には、平方性が逆転し、非剰余となる（「12k+7型」言い換えれば「12k−5型」に関するこの事実は、定理1で証明済み）。

まとめると:

第三補充法則　法が12k±1型の素数なら 3 は平方剰余。法が12k±5型（言い換えれば12k±7型）の素数なら 3 は平方非剰余。

〔例〕　p = 13 は12k+1型素数なので、x² ≡ 3 と x² ≡ −3 (mod 13) はどちらも解を持つはず。実際 x ≡ ±4 は前者を満たし、x ≡ ±6 は後者を満たす。

±3の平方性

↓mod	3	−3	modの種類
12k+1	平方剰余	平方剰余	バニラ
12k+7	非剰余	平方剰余	チョコ
12k−7	非剰余	非剰余	バニラ
12k−1	平方剰余	非剰余	チョコ

相互法則を使えば、ルジャンドル記号の機械的操作で効率よく同じ結論が得られるものの、上記のような直接証明は――表面的には非効率かもしれないが――含蓄がある。実際、われわれはいつしか「1 の原始3乗根との類似性」の問題に極めて接近していて、「相互法則は整数の話のようだが、その本質には複素数や無理数が関係する」ということが、漠然と予感される。教科書的な「知識」からは得られない体験的な「手応え」。

この方向には、探検・冒険の余地がいっぱいある…。

12k+7型素数（チョコ・ミント）と12k+11型素数（チョコ・ワッフル）について、それぞれ無限にあることを証明したからには、「12k+1型素数（バニラ・ミント）と12k+5型素数（バニラ・ワッフル）もそれぞれ無限に存在するのか？」という問いに答えを出さないことには、中途半端で、すっきりしない。この問題をとりあえず解決したいところだが、12k+1型素数の無限性については、これまでのような「平方剰余の応用」だけでは対応できない。「円分多項式」という概念が必要となり、結構大掛かりなハイキングコースとなる。ここまで来たからには、行かねばなるまい！

第二補充法則との関係においては、「8k+1型」素数は四乗剰余と結び付き、さらに−1 の4乗根（1 の8乗根）との関連性が認められた。【6】の議論は、12k+1型素数についての同様の事実――立方剰余や 1 の複素立方根などとの関連性――を示唆している。こちらは、面白い散歩道となるだろう。

第ニ補充法則・第三補充法則の拡張として「±5 や ±7 の平方性についても、直接証明できるか？」というのも、自然な疑問だろう。相互法則を使えば、これらの平方性の判定は機械的計算なのだから、「本質的には上と同じような、古風でのんびりした議論になるだけ」と予想したくなるかもしれないが、果たしてそうだろうか？

数論とは何なのか。われわれは何者なのか。この道は、どこへ続くのか。

〔補足〕　自然数の範囲において、3k+1型素数（ミント素数）と「6k+1型」素数は、無条件で全く同じ意味だが、3k+2型素数（ワッフル素数）と「6k+5型」素数は、微妙に意味が異なる: 前者は 2 を含むが、後者は 2 を含まない（2 を別にして、5 以上に話を限るなら、ワッフル素数は「6k+5型素数」）。負の整数にまで範囲を広げると、ミント素数と「6k+1型」素数にも、同様の微妙な違いが生じる: 前者は −2 を含み、後者は −2 を含まない。

2022-10-17　付録・定理1の別証明

【1】の定理1については、なかなかうまい証明法が見つからず、最初にメモを書いたときには、以下のややこしい方法を使っていた。

末尾のコメントにあるように、この証明法（DA 112/113; VüZ §41のアレンジ）には不満が感じられた。さいわい、別の方法（DA 117のアレンジ）を試したら、本文で紹介した簡潔な方法が見つかった！　簡単そうに書いてるように思われるかもしれないが、実際にはさんざん苦労したり、悩んだり、試行錯誤したりしている。その赤裸々な記録として、旧バージョンも残しておく…。

2022-10-29　バニラ・ミントはバッハの調べ　12k+1型素数の無限

12の倍数（12, 24, 36, …）より 1 小さい素数（11, 23, etc.）が無限に存在することは、比較的簡単に証明できた。では、12の倍数より 1 大きい素数（13, 37, etc.）も無限に存在するのだろうか？

ちょっと敷居の高い円分（えんぶん）多項式の世界だが…。いきなり一般論をやらず、一つの具体例を実際に利用しながら「優しい入門」を試みたい…

【1】　バッハは…
　　《バ》　x¹² = 2
…の実数解を使ってオクターブを12等分した（詳細は末尾の【5】参照）。われわれは1の原始12乗根を使って、単位円を12等分する:
　　《ビ》　x¹² = 1
の複素数解を考えることに相当するのだが、この分野になみじがない人は「何が何やらさっぱり…」と感じるかもしれない。けどまぁ、《ビ》の右辺の 1 を移項すると:
　　x¹² − 1 = 0
y = x⁴ と置くと:
　　y³ − 1 = 0　つまり　(y − 1)(y² + y + 1) = 0
x⁴ を y に戻すと:
　　《ブ》　(x⁴ − 1)(x⁸ + x⁴ + 1) = 0

《ブ》左辺の因子のうち…
　　《ベ》　x⁴ − 1 = (x² + 1)(x² − 1) = (x² + 1)(x + 1)(x − 1)
…は難なく分解できるとして、8次式の方は y² + y + 1 の形で見ると、「1の複素立方根の式」なので、実数係数の範囲ではこれ以上分解できないようにも思える。けれど、次の（ちょっぴりトリッキーな）恒等式を考えてみよう:
　　(z² + 1)² − z² = (z² + 1 + z)(z² + 1 − z)　　← A²−B² = (A+B)(A−B) の形
　　z⁴ + 2z² + 1 − z² = (z² + 1 + z)(z² + 1 − z)
　　《ボ》　z⁴ + z² + 1 = (z² + z + 1)(z² − z + 1)
従って z = x² と思うと、《ブ》の因子の8次式はこうなる:
　　x⁸ + x⁴ + 1 = (x⁴ + x² + 1)(x⁴ − x² + 1)
この右辺・後半の因子 x⁴ − x² + 1 は、これ以上分解できないが、右辺・前半は再び《ボ》の形なので:
　　x⁸ + x⁴ + 1 = (x² + x + 1)(x² − x + 1)(x⁴ − x² + 1)
だから《ブ》の左辺をこう書くことができる:

《マ》　f(x) = x¹² − 1 = (x⁴ − 1)(x² + x + 1)(x² − x + 1)(x⁴ − x² + 1)

この4個の因数のうち、x⁴ − 1 の部分は《ベ》のように、さらに分解できるのだが、ゴチャゴチャするので、このままで…。もともとの12次方程式 f(x) = 0 は、上記右辺の4因数の積が 0 という意味なのだから、方程式を満たす x は、次のどれかを満たす:
　　①　x⁴ − 1 = 0　または
　　②　x² + x + 1 = 0　または
　　③　x² − x + 1 = 0　または
　　④　x⁴ − x² + 1 = 0

【2】　今回の本題とは関係ないが、せっかくなので方程式を解いておこう！　1の12乗根って具体的にどんな数？ってのは、普通に好奇心が湧くことだしネ…。①の解はもちろん x = ±1, ±i の4個。このうち −1 は 1 の原始2乗根、i と −i は 1 の原始4乗根。

「原始○乗根」とは、○乗して初めて = 1 になり、○未満の正の整数乗では = 1 にならない数を指す。例えば (−1) は4乗すると = 1 になるので「1 の4乗根」の一つには違いないが、4乗しなくても (−1)² で既に = 1 になるので「1 の原始4乗根」ではない。

②の解は、1 の複素立方根（原始3乗根）2個: (−1±i√3)/2。②は2次方程式なので、解の公式から直接これらを得ることもできるし、三角関数を使えば cos θ + i sin θ で θ = ±120° の場合に当たる。

三角関数での表現は単なる参考事項で、今回の本題とは全く関係ないけど、①の4解についても同様に考えると、θ = 0°, 180°, ±90° の場合に当たる。座標平面のx軸が実部、y軸が虚部と考えている。

③の解は、1 の原始6乗根2個: (1±i√3)/2。これも2次方程式なので直接解けるし、あるいは cos θ + i sin θ で θ = ±60° の場合に当たる。

最後に④の解は 1 の原始12乗根4個だが、これは③で x = r² と置いて r について解いたもの（要するに③の解の平方根）に他ならない: (√3±i)/2 と (−√3±i)/2 であり、cos θ + i sin θ で θ = ±30° or ±150° の場合。実際、例えば r = (√3 + i)/2 のとき:
　　r² = (3 + 2i√3 − 1)/4 = (1 + i√3)/2
これは③の解の一つであり、この r は (1 + i√3)/2 の平方根の一つ。

まとめると①に4個、②に2個、③に2個、④に4個の解があり、合計12個の複素数 x が《マ》の f(x) = x¹² − 1 = 0 を（言い換えれば x¹² = 1 を）満たす。これらが12種類の「1の12乗根」。音楽でいえば、1オクターブの12半音のようなもの…。イメージ的には、単位円というピザを30°ずつ12等分した切り口に当たる。

【3】　さて、差し当たり重要なのは、「1 の原始12乗根」に対応している④の形 g(x) = x⁴ − x² + 1。ここでは直接的に複素12乗根を使うのではなく、自然数を入力とするシンプルな関数として、これを扱う。

仮に12k+1型の素数が S = {p₁, p₂, …, p_m} の m 個しかないとして、それらの積を A = p₁p₂…p_m としよう。少なくとも 13 と 37 は S に属するので S は空集合ではない。p₁, p₂ などは、どれも ≡ 1 (mod 12) なので、それらの積も ≡ 1 (mod 12)。さらに（ちょっと天下り的だが）上記の多項式 g(x) を使って
　　B = g(A) = A⁴ − A² + 1
と置くと、この数も B ≡ 1⁴ − 1² + 1 ≡ 1 (mod 12) を満たす。つまり12k+1型の奇数。

〔例1〕　仮に12k+1型の素数（バニラ・ミント素数）が {13, 37} だけだとすると、A = 13 × 37 = 481, B = 481⁴ − 481² + 1 = 535億2768万0961。この11桁の数を12で割ると1余る。実際、下2桁の61を4で割ると1余る（100の倍数は4で割り切れるので、下2桁だけ考えれば十分）。さらに3の倍数を無視しながら桁の和を考えると:
　　(5+3+5) + (2+7+6+8) + (0+9+6+1) ≡ 10 + 8 + 1 ≡ 1 (mod 3)
従って、この数を3で割ると1余る。3で割っても4で割っても1余るのだから、12で割れば1余る。

もし B が素数なら、B は明らかに S のどの素数 p よりも大きいので、新しい12k+1型の素数が見つかったことになる。一方、B が合成数だとして、その任意の素因数 q は、S に属するどの素数 p とも異なる。実際、A は p の倍数なので B = A⁴ − A² + 1 は p の倍数より1大きく、すなわち B は p では割り切れない; q は B の素因数なので、B は q で割り切れる。「q はどの p とも異なる」という動かぬ証拠である！

〔例2〕　例1の数 A = 13 × 37 = 481, B = A⁴ − A² + 1 = 53527680961 について。Bは実は合成数で、601 × 2617 × 34033 と素因数分解される。B は A の倍数より1大きいが、その A は p = 13（あるいは p = 37）の倍数なので、B を p で割っても割り切れない（1余る）。一方、B の素因数（例えば q = 601）は、もちろん B を割り切る。

従って q は S に含まれない新しい素数だが、以下で証明するように、この q は、実は12k+1型の素数（バニラ・ミント）。

〔例3〕　例2の B = 53527680961 = 601 × 2617 × 34033 について。 q = 601 とすると、例1同様、下2桁から q はバニラ（4で割って1余る）、桁の和から q はミント（3で割って1余る）。q = 2617, q = 34033 も同様にバニラ・ミント。

q は A のどの素因数（p₁, p₂, …, p_m）とも異なる素数なので、もちろん A は q の倍数ではない。

《マ》で見たように、「ボス」4次式 g(x) = x⁴ − x² + 1 は、「大親分」 f(x) = x¹² − 1 の「子分」（約数・因数）なので、ボス g(x) の部下（約数）たちは、当然、大親分 f(x) の部下（約数）でもある。q が B = g(A) の約数であると仮定しているのだから、f(A) = A¹² − 1 も q で割り切れる:
　　《ミ》　A¹² − 1 ≡ 0 (mod q)　すなわち　A¹² ≡ 1 (mod q)

〔例4〕　A = 481 なら、ボスが B = A⁴ − A² + 1 = 53527680961、大親分…
　　481¹² − 1 = 153370176189268183007030246252160
…は、そのボスの倍数（B で割り切れる）。当然、ボスの子分たち B = 601 × 2617 × 34033 のどれから見ても、大親分は自分の倍数に当たる。例えば:
　　481¹² − 1 = 601 の倍数
両辺に 1 を足すと
　　481¹² = 601 の倍数 + 1
　　言い換えれば　481¹² ≡ 1 (mod 601)

mod q において A を12乗すると ≡ 1 になることが分かった。では、もし mod q で A の位数が12だとしたら――つまり A は12乗して初めて ≡ 1 になり、6乗や4乗などでは ≢ 1 (mod 12) だとしたら――どうなるか？

A は素数 q の倍数ではないので、フェルマーの小定理から A^q−1 ≡ 1 (mod q)。 A の位数 e は、この q−1 の約数なので（説明）、もし e = 12 なら、q−1 は 12 で割り切れる:
　　e = 12 なら q − 1 ≡ 0 (mod 12)　つまり　q ≡ 1 (mod 12)
これは「q が12k+1型の素数」ということであり、非常に望ましい結論である！

すなわち e = 12 を示せば、証明が完成する。e が12の約数であることは明らかなので、もし仮に e が12でないとすれば、それは 1, 2, 3, 4, 6 のどれか: e = 1, 2, or 4 なら A⁴ ≡ 1 (mod q) が成り立ち、さもなければ A³ ≡ 1 または A⁶ ≡ 1 が成り立つ。その「もし仮に」が無理な仮定であることを示そう。

e = 2 は A² ≡ 1 (mod q) を含意するが、その両辺を平方すれば A⁴ ≡ 1 (mod q)。 e = 1 は A¹ ≡ 1 (mod q) を含意するが、その両辺を4乗すれば A⁴ ≡ 1 (mod q)。

〔例5〕　例4から 481¹² ≡ 1 (mod 601)。従って 481^e ≡ 1 (mod 601) を満たす正の整数 e の例として e = 12 がある。けれど例えば…
　　もしも 481⁶ ≡ 1 が成り立つなら（実際には成り立たないが）
　　481¹² ≡ (481⁶)² ≡ (1)⁶ ≡ 1 (mod 601)
…というような可能性も考えられるので、「481 を12乗すると ≡ 1」というだけでは、481^e ≡ 1 を満たす最小の正の整数 e が12とは言い切れない。現時点では、「e が12未満」という可能性が否定されていないため、e は12の約数のどれにもなり得る。

もし仮に A⁴ ≡ 1 つまり A⁴ − 1 ≡ 0 (mod q) なら A⁴ − 1 は q で割り切れるが、そのとき (A + q)⁴ − 1 も q で割り切れる。というのも…
　　(A + q)⁴ = A⁴ + 4A³q + 6A²q² + 4Aq³ + q⁴
…と A⁴ の差は q の倍数なので^*、mod q では（つまり q で割った余りという観点では）違いがない:
　　A⁴ ≡ (A + q)⁴ (mod q)　両辺から 1 を引くと
　　A⁴ − 1 ≡ (A + q)⁴ − 1 (mod q)

*　(A + q)⁴ を展開したときの係数は、順に 1, 4, 6, 4, 1 （参考）。ここでは「大部分の項が q の倍数になること」が核心で、具体的な係数の値は重要ではない。

同様の理由から A² ≡ (A + q)² (mod q)、それを上の式から辺々引き算すると:
　　A⁴ − A² + 1 ≡ (A + q)⁴ − (A + q)² + 1 (mod q)　従って
　　B = g(A) ≡ g(A + q) (mod q)
全く同様にして、より一般的に、整数を係数とする任意の多項式 h(x) について h(A) ≡ h(A + q) (mod q) が成り立つ。従って:
　　f(A + q) ≡ f(A)　つまり　(A + q)¹² − 1 ≡ A¹² − 1 (mod q)
《マ》《ミ》を使うと:
　　《ム》　(A + q)¹² − 1 ≡ A¹² − 1 ≡ (A⁴ − 1)(A² + A + 1)(A² − A + 1)g(A) ≡ 0 (mod q)

ここでボス B = g(A) が部下 q の倍数というのは q の定義そのものだが、今は「もし仮に」として A⁴ − 1 も q の倍数と想定している。よって《ム》の4因子の積は q の倍数を（少なくとも）2個含んでいて、q で2回割り切れる――言い換えると q² で割り切れ、それと合同な大親分 A¹² − 1 や (A + q)¹² − 1 も q² の倍数になる。この最後の式を展開すると、二項定理から、こうなる:
　　A¹² + 12A¹¹q + (12⋅11/2!)A¹⁰q² + (12⋅11⋅10/3!)A⁹q³ + … + 12Aq¹¹ + q¹² − 1
　　≡ A¹² + 12A¹¹q − 1 ≡ 0 (mod q²)

ここで (12⋅11/2!) などは一定の整数（二項係数）だが、その具体的な値は重要ではない――q² を含む項から q¹² の項までは、明らかに q² で割り切れるので mod q² では ≡ 0 であり、無視していい。さて、この仮定上では大親分 A¹² − 1 も q² で割り切れるのだから、上の合同式はこうなる:
　　(A¹² − 1) + 12A¹¹q ≡ 0　つまり　12A¹¹q ≡ 0 (mod q²)
　　両辺を q で割って　12A¹¹ ≡ 0 (mod q)
これは、ばかげている！　A が q で割り切れないことは確定しているので、A¹¹ は決して q では割り切れないし、q は12k+1型の奇数 B（この B を 2 で割っても 3 で割っても 1 余って割り切れない）の素因数なのだから 2 or 3 の訳がなく、12 は決して q では割り切れない。すなわち A⁴ ≡ 1 (mod q) という仮定は不合理。

同様に、もし仮に e = 3 なら A³ − 1 = (A − 1)(A² + A + 1) が q で割り切れるが、e ≠ 1 なので A² + A + 1 が q で割り切れる。このことから《ム》の積は q² で割り切れることになり、矛盾が生じる。最後に、もし仮に e = 6 なら A⁶ − 1 = (A − 1)(A + 1)(A² + A + 1)(A² − A + 1) が q で割り切れるが、位数の条件から A² − A + 1 が q で割り切れ、やはり《ム》で矛盾。

A⁶ − 1 = (A − 1)(A + 1)(A² + A + 1)(A² − A + 1) の4因子のどれが q で割り切れるか？は、矛盾の本質と関係ない。どの因子が q で割り切れるにしても（もし仮に A⁶ − 1 が q で割り切れるのなら、因子のどれかが q で割り切れる）、同様の矛盾が生じる。

結論として e = 12。この方法で出てくる新しい素数 q は、必ず12k+1型（バニラ・ミント）。□

【4】　「12k+1型の素数は有限個しかない。このリストの数だけだ」と言い張る人がいたとして、そのリストの数を全部掛け合わせたものを A として上の方法を使うと、必ずリストにない新しい12k+1型素数 q が見つかる。最初の人が「おっと q を入れ忘れていた。最初のリストに q を付け加えれば、今度こそ12k+1型素数の完全リストです」と言い張ったとしても、その新しいリストの数を全部掛け合わせたものをあらためて A とすれば、またまたリストにない別の12k+1型素数 q が見つかる。…つまり、「12k+1」型素数は無限に存在する！

上記【3】では、g(A) = A⁴ − A² + 1 に「ボス」というニックネームを付けた。この「ボス」――正式名称「円分（えんぶん）多項式」――さえ正しく選べば、同様の方法で「13k+1」型、「14k+1」型など任意の「nk+1」型素数について、その無限性を示すことができる。一般論においては、ボスの具体的な形を示すことなく「とにかくボスが存在する」という事実を利用する。

原始12乗根を解に持つ g(x) = x⁴ − x² + 1 が、n = 12 の場合の円分多項式に当たる。

一般の場合の定理は標準的なもので、多くの文献・資料に掲載されているだろう。本文では S の全素数の積を A としたが、文献上の一般論では、その n 倍を A とすることが多い。そのようにすると、S が空集合の場合でも（その場合には A = n とすることで）、次々とその型の新しい素数をリストに加えていくことができる。一般論の場合、任意の n に対して S が空集合でないことを示すだけでも簡単ではないだろうから、重要な工夫だと思われる。A を事前に n 倍（例えば12倍）しておくことで「q は A を割り切らないから、12 を割り切らない」という議論も簡単にできる。

「A の位数が n = 12 ちょうどではなく、もっと小さい」と仮定して矛盾を導く部分については、次の方法もある。その仮定だと、実数の世界での f(x) = 0 は x = A において重解を持つ（《ム》参照）。従って、解析学によると、x = A は f(x) の導関数の零点: 要するに 12A¹¹ = 0、ゆえに 12A¹¹ ≡ 0 (mod q) となるが、それが不合理であることは本文の通り。

ここで解析学を絡めるのはスマートで格好いいし、それはそれで参考になるのだが、エリートのどや顔のようで、しゃらくさい気も…ｗ

円分多項式の世界を研究するには、メビウス反転などのツールが必要になり少し準備が必要だが、面白い探検には違いない…。自然数の世界の「素数の分布」に、自然と複素数の世界が絡んでくるのは、神秘的な感じがする！

【5】　音楽の12平均律では、周波数の比が「2 の12乗根」（の主値）のときを半音と定義することで、半音の「幅」（周波数比）がどこでも同じになる。この比を例えば s として、基準の「ラ」の音を440ヘルツとすると、半音上は周波数は次々と s 倍になるのだから…
　　「ラ」の周波数　440
　　「ラ」♯　　　　440 × s = 440s
　　「シ」　　　　　440s × s = 440s²
　　「ド」　　　　　440s² × s = 440s³
　　「ド」♯　　　　440s³ × s = 440s⁴
…等々となり、1オクターブ（つまり12半音）上の「ラ」は 440s¹² = 440 × 2 = 880 ヘルツ（なぜなら s は 2 の12乗根なので、s¹² = 2）。物理的な自然倍音との関係において「オクターブは2倍の周波数」というのは、つじつまが合っているようだが、オクターブ以外は、理論上の周波数比が「無理数」。純正な自然倍音と異なるのは、言うまでもない。このような「無理」をしてまでオクターブを12等分するのは、次のような判断からだろう:
　　（オクターブの違いを別にして）12種類のピッチだけ用意しておけば、12調の枠の中でなら自由自在に転調できる。
　　この便利さは「純正律と微妙にずれているという欠陥」を補って余りある。

〔注〕　音楽で単に「平均律」と言った場合、大抵は調律のことではなく、バッハの作品集を指す。ここでは調律の話をしている。バッハの「平均律」曲集には、調律の平均律の素晴らしさを実例で示す…というような狙いがあったのかもしれない。

平均律には長所もあれば、短所もある。

鍵盤楽器の生硬な平均律に慣れ切った耳には、トロンボーンや弦楽器の純正なハーモニーは、息をのむほど美しいと感じられることがある…。「和音の美しさ」という点では、例えば、純正な長3度の澄み切った響きの心地よさは、否定のしようがない。変ト長調と嬰ヘ長調が実は「同じ」調…といった「エンハーモニック」は、純正律の立場からは暴挙かもしれない。

他方において、「12種類の音だけで、全てが円環的に完結する」という12平均律の構造は、それ自体として、美しい。有限個の鍵盤しかない鍵盤楽器などでは「12種類の音を出せれば何でも演奏できる」というのは、実用上も極めて便利。事実このシステムは大成功して、現代でも圧倒的な主流となっている。クラシックも、ジャズも、軽音楽も、ほとんど12平均律だろう。

現代の電子楽器やデジタル技術なら、その気になれば仮想鍵盤をいくらでも追加して、簡単に純正律も使える。純正律の方がハーモニーが美しいのに、平均律がなくならないのは、なぜか…。やはり「実用性と美しさのバランス」が最適なのだろう。平均律では「ファの♯とソの♭が同じ」という「ある意味での欠陥」を逆用して「エンハーモニックの魔法」を使える。これは、純正律では実現できない。「広がって解決したい増4度の和音…と思わせておいて、いつしか雰囲気が変わって、減5度になって内側に解決する」という「だまし舟」のような進行は、後期ロマン派では、ありがちなものだろう。この手法は遠隔調への「ワープ転調」を可能にして、究極的には調性の崩壊を招くのだが、そこから、また新しい音楽の世界が生まれてきた。

自然数・整数を基本対象としているように思える数論においても、場合によっては、無理数や複素数を使うと便利なことがある――というより、整数の構造そのものの中に、無理数や複素数が初めから内在している。

このメモでは、一つの具体例として、次のことを観察した。
　　「12の倍数より1大きい素数が無限に存在する」という自然数の世界の事実が、
　　「複素数の世界で、1の原始12乗根を解とする4次式」の振る舞いと結び付いている。

「なぜそうなるのか？」というのは難しい問題かもしれないが、音楽の12平均律と同様、このようなアプローチが実用上便利であることは、間違いない。

〔参考文献〕
[1] B. Sury: Cyclotomy and Cyclotomic Polynomials - The Story of how Gauss Narrowly Missed Becoming a Philologist
https://www.ias.ac.in/listing/articles/reso/004/12
[2] Wikipedia: Cyclotomic polynomial
https://en.wikipedia.org/wiki/Cyclotomic_polynomial

2022-12-30　バニラ・ワッフル　12k+5型素数の無限

#数論　#第一補充法則　#第三補充法則

奇数の素数は、バニラとチョコに分類される:
　　バニラ素数（4の倍数より1大きい）　5, 13, 17, 29, 37, …
　　チョコ素数（4の倍数より1小さい）　3, 7, 11, 19, 23, 31, …

別の分類法として、3 以外の素数は、ミントとワッフルに分かれる:
　　ミント素数（3の倍数より1大きい）　7, 13, 19, 31, 37, …
　　ワッフル素数（3の倍数より1小さい）　2, 5, 11, 17, 23, 29, …

この二つを組み合わせると、5 以上の素数は、次の4種類に分類される:
　　バニラミント（12の倍数プラス1）　13, 37, …
　　バニラワッフル（12の倍数プラス5）　5, 17, 29, …
　　チョコミント（12の倍数プラス7）　7, 19, 31, …
　　チョコワッフル（12の倍数プラス11）　11, 23, …

どのタイプの素数も、無限個ある。このうち、チョコミントとチョコワッフルの無限については、第三補充法則によって比較的簡単に証明された。バニラミント素数が無限にあることは、円分多項式を使って証明された。残っているのは、バニラワッフル素数だが、それが無限にあることの証明は、4種類の中で一番シンプル。

【1】　12k+5型の素数が次の m 個しかないと仮定して、矛盾を導く:
　　S = {p₁, p₂, p₃, …, p_m}

S のどの要素 p もバニラワッフル素数なので p ≡ 5 (mod 12) を満たす――つまり 12 で割ると 5 余る。従って、その平方も p² ≡ 5² ≡ 25 ≡ 1 (mod 12) を満たし、そのことから、S の各要素の平方を掛け合わせたものもまた、次の関係を満たす:
　　p₁²p₂²p₃²…p_m² ≡ 1⋅1⋅1⋅…⋅1 ≡ 1 (mod 12)
x = p₁p₂p₃…p_m と置くと、上記の式はこうなる:
　　x² ≡ 1 (mod 12)
両辺を 4 倍して 1 を足すと:
　　4x² + 1 ≡ 5 (mod 12)　　‥‥①

この 4x² + 1 という数は、偶数 4x² より 1 大きいので奇数であり、その素因数は奇数に限られる。

今 4x² + 1 の任意の素因数を q とすると、4x² + 1 は q で割り切れるのだから:
　　4x² + 1 ≡ 0 (mod q)　つまり　(2x)² ≡ −1 (mod q)

これは −1 が mod q の平方剰余という意味なので、第一補充法則から q はバニラ素数に限られる。従って q ≡ 1 or 5 (mod 12) ――つまり q はバニラミントか、バニラワッフル。けれど、もしも 4x² + 1 の素因数が全て ≡ 1 (mod 12) だったら、それらの積である 4x² + 1 自身も ≡ 1 (mod 12) になってしまい、①の事実に反する。だから 4x² + 1 は、q ≡ 5 (mod 12) という性質の素因数 q を少なくとも一つ持つ――言い換えれば、バニラワッフル素数の因数 q を持つ; q としてこの型の素数を選ぶことにしよう。

さて S の各要素 p の積が x なのだから、x は当然 p の倍数。従って 4x² も p の倍数; 4x² + 1 は p の倍数より 1 大きいので p で割り切れない。一方 q は 4x² + 1 の素因数なので、4x² + 1 は q で割り切れる。だからバニラワッフル素数 q は、S に含まれるどのバニラワッフル素数 p とも異なる数。すなわち S に含まれていない新しいバニラワッフル素数が存在し、「バニラワッフル素数はリスト S の m 個だけしかない」という最初の仮定は不合理。□

〔例1〕　バニラワッフル素数が {5, 17, 29} の3個しかないと仮定。
　　x = 5⋅17⋅29 = 2465
　　4x² + 1 = 24304901 = 61 × 398441
これらの素因数のうち 61 はバニラミントだが、398441 (= 12 × 33203 + 5) はバニラワッフル素数。最初の仮定は誤り。

〔例2〕　バニラワッフル素数が {5, 17, 29, 41} の4個しかないと仮定。
　　x = 5⋅17⋅29⋅41 = 101065
　　4x² + 1 = 40856536901
この11桁の数は、それ自身バニラワッフル素数。最初の仮定は誤り。

ある数が「バニラワッフル」（12で割ると5余る）であることを検証するには、「4で割ると1余ること」と「3で割ると2余ること」を確かめればいい。「4で割ると1余るか」は、下2桁がその性質を持つかどうかで決まり（100は4の倍数なので、100の位より上の桁は無視していい）、簡単にチェックできる。「3で割った余り」は、桁の和を3で割った余りをチェックすればいい。398441 の例では、原理的にはこうなる:
　　3 + 9 + 8 + 4 + 4 + 1 = 29　　←　3 で割ると 2 余る
実際には、3の倍数を足しても「3で割った余り」には影響しないので、数字が 0, 3, 6, 9 の桁は無視して構わない:
　　3 + 9 + 8 + 4 + 4 + 1 = 17　　←　3 で割ると 2 余る
さらに、同じ理由から、桁の和の計算の途中で3の倍数ができたら、和を 0 にリセットして、そこから先の桁の和だけを考えれば十分。上の例では 8 + 4 = 12 が3の倍数なので、その和を捨てて、残りの 4 + 1 = 5 だけを計算すれば、「3 で割ると 2 余る」という同じ結論になる。

例2の「40856536901」を12で割った余りは、暗算での検算は困難に思えるかもしれない。ところが、下2桁が01なので、バニラ（4で割って1余る）ということは明白。次に、桁の和を考えると、左からまず 4 + 8 = 12 だが、これは3の倍数なので無視して、残りの桁（3の倍数以外）を足すと 5 + 5 + 1 = 11。つまりこの 11 を3で割った余り2が、「40856536901」を3で割った余りに他ならない。やり方を知ってれば（1桁の数字を足すだけなので）、数秒で暗算できるだろう。――もっとも「検算」は間違いがないか確認することなので、素早く計算することにこだわらず、むしろ慎重にゆっくり検討しよう。

【2】　4x² + 1 の代わりに x² + 4 を使った方が、数値的には少し簡単に（小さく）なる。x ≡ 1 (mod 12) の設定は【1】と同じなので、
　　x² + 4 ≡ 5 (mod 12)　　‥‥②
が成り立つ。x² + 4 の任意の素因数 q も、バニラ素数に限られる。なぜなら x は奇数なので x² + 4 も奇数であり、その素因数 q は奇数。さて q が x² + 4 の素因数なら:
　　x² + 4 ≡ 0 (mod q)　つまり　x² ≡ −4 (mod q)
q は奇素数なので −4 と互いに素、従ってそれと合同な x² とも互いに素。x の2乗が ≡ −4 なのだから、x は偶数でなければならず、従って x² は ４ の倍数。だから、上記 x² ≡ −4 の両辺を 4 で割って、次の形にできる:
　　(x/2)² ≡ −1 (mod q)　　ここで x/2 は整数

これは −1 が mod q の平方剰余という意味なので、第一補充法則から q はバニラ素数に限られ、以降の証明は【1】と同様に進む。□

〔例3〕　バニラワッフル素数が {5, 17, 29, 41, 53} の5個しかないと仮定。
　　x = 5⋅17⋅29⋅41⋅53 = 5356445
　　x² + 4 = 28691503038029 = 13 × 373 × 10453 × 566057
この4個の素因数のうち、最初の3個はバニラミントだが、最後の一つはバニラワッフル素数。14桁の整数の素因数分解が必要になるものの、4x² + 1 を使うと15桁の整数になるので、それに比べれば、少し計算量を節約できる。

以上によって、12k+1, 12k+5, 12k+7, 12k+11 のどの型の素数も、それぞれ無限にあることが証明された。証明の全体的な雰囲気は、8k+1, 8k+3, 8k+5, 8k+7 型の素数についての同様の考察と似ている。特に、12k+5型素数の無限は、8k+5型素数の無限と、よく似た方法で証明可能。

4k+1型素数、4k+3型素数は、それぞれ無限に存在する。このうち4k+1型を「8k+1型と8k+5型」に細分したり、あるいは「12k+1型と12k+5型」に細分したりしても、細分されてできた部分集合は、それ自体も無限集合。4k+3型素数の細分についても、同様のことがいえる。これらは非常に興味深い事実だが、個々の証明の関係については、必ずしも見通しがよくない。行き当たりばったりのような感じもする。さらに、このような初等的アプローチは、ごく限られた範囲にしか適用できない。例えば 10k+1, 10k+3, 10k+7, 10k+9 のどの型の素数も、事実としては無限に存在するのだが、10k+3型素数の無限、10k+7型素数の無限については、このような「ユークリッド的方法」では証明できない。

けれど、がっかりする必要はないだろう。「このルートからは到達できない高い山がある」ということは、「いつかは登ってみたい」という憧れをかき立てるし、たとえその山が険し過ぎるとしても、数論には、初等的な範囲でも、素晴らしいハイキングコースがたくさんあるのだから…。

2022-12-15　第五補充法則 Part 1　手品！

#数論　#平方剰余　#第五補充法則　#Disq. Arith.

☆　4 以上の偶数（10の倍数以外）を一つ思い浮かべてください。

☆　その数を2乗して 5 を引いてください。

☆　できた数の好きな約数をどれでも一つ選んでください。

あなたの選んだ約数は、末尾が 1 か 9 ですね！

――最初に 18 を思い浮かべたとすると、18² は 324、そこから 5 を引くと 319。この数の約数は 1, 11, 19, 319。最初に 14 を思い浮かべたとすると、14² は 196、そこから 5 を引くと 191。この数は素数で、約数は 1 と 191 自身だけ。いずれにしても末尾（最下位桁）が 1 or 9 になる。タネが分かるとくだらない手品かもしれないが、結構面白いかと…（出典: 今考えたｗ）。

この性質を応用して「9 で終わる素数（19, 29, 59, 79, …）は、無限に存在する」ということも、エレガントに証明できる。9 で終わる素数が無限個だろうが有限個だろうが、そんな知識は何の役にも立たないような気もするが、それ自体が面白いから、それでいい。無限って、ワクワクするよね！

「何かの役に立つ」というのは、その「何か」のための道具・手段に過ぎない。「それ自体が面白い」ということは「純粋にそれ自体」であり、それこそが人生において最も価値のあることではないだろうか。例えば「試験で役立つ」知識を「詰め込み勉強」で頑張って覚え、高得点を取り、他人に褒められ尊敬される。それは「他人にどう見られるか」という皮相の問題。「自分自身がそれを面白いと思う」とき、それは他人と無関係に、内在的に湧き出る泉であり、純粋に面白いので、頑張って努力する必要すらない。「他人の目」に従って生きるのではなく「自分の心」によって生きるのだ。

【1】　概要―― p を 2, 5 以外の素数とする。x² ≡ ±5 (mod p) に解があるかないかは、「平方剰余の相互法則」というものを使って、機械的に判定される。ところが Gauß の Disq. Arith. (DA) 第121～123節では、相互法則を使わない直接証明が行われている。大部分は平易で、相互法則の証明より分かりやすい。ただし、相互法則はより一般的で強力なツールであり、それを使えば機械的計算なのだから、このような直接証明にはあまり意味がない…という見方もできる。Gauß の伝道者 Dirichlet も同じ考えだったようで、Dirichlet の講義では第三・第五補充法則は省略されている。

半面、この個別のケースを検討することには、メリットもある。第一に、相互法則がどのように発見されたのかということを体感的に理解できる。抽象的で無味乾燥にも思える相互法則――Legendre 記号を「ひっくり返す」ことの意味――が、具体的な事例を通じて、なんとなく見えてくる。第二に、一部のケースの証明は玄妙で、Fibonacci 数列の Binet の公式と似た扱いを経由したり、円分多項式の理論と関連したり…。これらのケースでは、普通に相互法則を使った方がむしろ楽なのだが、あえてこの route を探索することは、決して無駄ではない。巨匠 Gauß の書いたものに直に触れることで、自然と体得される「感覚」は、想像以上に大きい。

このシリーズでは、4回に分けて検討を行う。その概要は次の通り。
　　Part 1　DA121節　p ≡ 2, 3 (mod 5) なら 5 は非剰余（易しい）
　　Part 2　DA122節　p ≡ 11, 13, 17, 19 (mod 20) なら −5 は非剰余（易しい）
　　Part 3　DA123節前半　p ≡ 1 (mod 5) なら 5 は平方剰余（易しいが奥深い）
　　Part 4　DA123節後半　p ≡ 4 (mod 5) なら 5 は平方剰余（難しい）

メモの日付の順序は Part 4 → Part 2 → Part 1 → Part 3 だが、上記の順序で並び替えてある。Part 2 は本質的には平易だが、Gauß は「同様にできる」で流しているので、省略された証明法を考える必要がある（Part 2 は論理的には必要ないけれど、理解を深める上で役立つ）。Part 4 は玄妙で、Fibonacci 数列の「素数+1」番目の項の分析に似ている。冒頭の手品のタネ（仕組み）については、下記定理1の下の〔注意〕参照。

【2】　mod 5 の世界（＝5の倍数の違いを無視する世界）では、0 を別にすると 1, 2, 3, 4 の4種類の数しかない。4 ≡ −1 (mod 5) で 3 ≡ −2 (mod 5) なので ±1, ±2 の4種類ともいえる。

この世界での「平方数」（平方剰余）は、0 を別にすると (±1)² ≡ 1 と (±2)² ≡ 4 の2種類のみ。2 と 3 は「非平方数」（平方非剰余、略して非剰余）。言い換えると ±1 が平方剰余で ±2 は非剰余。

〔例1〕　mod 5 の世界でもし 1, 3, 7, 9, 11, 13, 17, 19 の8整数を考えるなら、1, 9, 11, 19 は平方剰余、3, 7, 13, 17 は非剰余。この世界では 1 ≡ 6 ≡ 11 は「同じ」種類（5の倍数の違いは無視される）、2 ≡ 7 ≡ 12 ≡ 17 も同じ種類。同様に −2 ≡ 3 ≡ 8 ≡ 13 なども同じ種類だし、−1 ≡ 4 ≡ 9 ≡ 14 ≡ 19 なども同じ種類。

≡ ±1 (mod 5) の数（言い換えれば、5k±1型の数）を何個掛け合わせても、依然として ≡ ±1 にしかならない。従って ≡ ±2 (mod 5) の自然数（言い換えれば、5k±2型の自然数）は、必ず同じ型の素因数を持つ。特に、奇数が素因数 2 を持つことはあり得ないので、5k±2型の正の奇数は、必ず同じ型の奇数の素因数を少なくとも一つ持つ。

〔例2〕　143 は5k±2型なので、同じ型の素因数を持つ。実際 143 = 11 × 13 のうち 13 は5k±2型。

5k+2型の自然数（2, 7, 12, 17, etc.）は、偶数なら末尾が 2 で、奇数なら末尾が 7。一方、5k−2型（5k+3型）の自然数（3, 8, 13, 18, etc.）は、偶数なら末尾が 8 で奇数なら末尾が 3。だから、5k±2型の（正の）奇素数は、必ず末尾が 3 or 7 になる（言い換えれば、10k±3型）。同様に、5k±1型の素数は末尾が 1 or 9 になる（言い換えれば、10k±1型）。

定理1　p が5k±2型の奇素数なら x² ≡ 5 (mod p) は解を持たない。つまり 5 は、そのような奇素数 p の平方非剰余。

〔注意〕　p は10k+3型 or 10k+7型ともいえる。つまり定理1によれば、末尾が 3 or 7 の素数 p は x² ≡ 5 つまり x² − 5 ≡ 0 (mod p) を満たさない。これは「x² − 5 の約数の末尾は 3 or 7 ではない」ということ。これが冒頭の手品のタネ！

証明　矛盾を導くため「定理1は間違っている。よ～く探せば x² ≡ 5 (mod p) が解を持つような5k±2型の奇素数 p が見つかる」と仮定する。p として、そのような素数のうち、最小のものを選ぼう: つまり「x² ≡ 5 (mod p) は成り立つけれど、p より小さい5k±2型の奇素数 q が x² ≡ 5 (mod q) を満たすことはない」と仮定する。x = 0 は明らかに解ではないので、解 x = a があるとすれば 1 以上 p 未満の範囲に解がある。このとき（どうせ平方されるのだから a の符号はプラスでもマイナスでもいいわけで） −a ≡ p − a も解であり、この解も 1 以上 p 未満。p は奇数なので、解 a が偶数なら解 p − a は奇数、a が奇数なら p − a は偶数。そこで 1 以上 p 未満の偶数の解を考えることにして、その解を e と呼ぶと:
　　e² ≡ 5 (mod p)　つまり　e² − 5 ≡ 0 (mod p)
これは e² − 5 が p の倍数という意味を持つが、もしも偶数 e が = 2 なら、上記の最後の式は −1 ≡ 0 となって不合理。だから e は 4 以上。従って e² − 5 は正の奇数であり、前述のように、それに等しい p の倍数が存在する。つまり正の奇数 f が存在して、次を満たす:
　　e² − 5 = pf

この式を mod 5 で考えると、−5 ≡ 0 (mod 5) は消滅して、こうなる:
　　e² ≡ pf (mod 5)
従って pf は mod 5 の平方剰余。

もし偶数 e が 5 の倍数でなければ（そのとき e² も 5 の倍数でなく、それと合同な pf も ５ の倍数でないので）、f も 5 の倍数ではない。さて、積 pf は mod 5 の平方剰余だが、仮定により因子 p は5k±2型であり、つまり mod 5 の非剰余なので、因子 f も mod 5 の非剰余であり（このロジックについては冬【11】参照）、5k±2の形を持つ。従って f は5k±2型の素因数 q を持つが、そのことから矛盾が生じる。というのも e は p 未満なので e² − 5 = pf は p² 未満、従って f は p 未満、その f の素因数 q は当然 p より小さい。ところが e² − 5 = pf を mod q で考えると（pf は q の倍数、つまり ≡ 0 なので）…
　　e² − 5 ≡ 0　つまり　e² ≡ 5 (mod q)
…となってしまい、「この関係を満たす最小の5k±2型素数は p」という前提に反する。

一方、もし偶数 e が 5 の倍数なら、e² − 5 = pf の左辺は 5 の倍数なので、それに等しい pf も 5 の倍数。5k±2型の素数 p は 5 の倍数ではないから、f が 5 の倍数。そこで e = 5E, f = 5F とすると、e² − 5 = pf はこうなる:
　　(5E)² − 5 = p(5F)　両辺を 5 で割って
　　5E² − 1 = pF
この最後の式を mod 5 で考えると −1 ≡ pF つまり pF ≡ 4 ≡ 2² (mod 5) なので、pF は mod 5 の平方剰余。ところが p は mod 5 の非剰余なので F も非剰余、すなわち5k±2型。このことから、F は5k±2型の素因数 q を持ち、その q は f = 5F の素因数でもあるから、前半同様、矛盾が生じる。□

【3】　末尾が 9 の素数が無限に存在すること。そのような素数が S = {p₁, p₂, …, p_m} の m 個だけだと仮定して、矛盾を導く。末尾が 9 の任意の素数 p は ≡ 9 (mod 10) を満たすので、平方すると p² ≡ 81 ≡ 1 (mod 10)。従って S の各素数の2乗は ≡ 1 (mod 10) であり、それらの積も ≡ 1 (mod 10)。その積の 4 倍はもちろん ≡ 4、そこから 5 を引けば 4 − 5 ≡ −1 ≡ 9 (mod 10)。

〔例3〕　S = {19, 29} とすると、19²⋅29² = 361⋅841 = 303601 ≡ 1 (mod 10)、従ってその 4 倍から 5 を引くと ≡ 9。実際:
　　4⋅19²⋅29² − 5 = 1214399 ≡ 9 (mod 10)

x = 2p₁p₂…p_m とすると:
　　(4p₁²p₂²…p_m²) − 5 = (2p₁p₂…p_m)² − 5 = x² − 5
定理1により x² − 5 は、末尾 3, 7 の素因数を持たない。しかも x は（従って x² も）明らかに 5 の倍数ではないので、x² − 5 は 5 の倍数ではなく、素因数 5 を持たない。要するに x² − 5 の素因数は、末尾 1 or 9 に限られる。ところが、もし全部の素因数が末尾 1 つまり ≡ 1 (mod 10) だとすると、それらの積である x² − 5 も ≡ 1 (mod 10)。実際には、上述のように x² − 5 ≡ 9 (mod 10) なので、x² − 5 の全部の素因数が末尾 1 ということはあり得ず、x² − 5 は末尾 9 の素因数を少なくとも一つ持つ: それを q としよう。

x² − 5 は S に含まれるどの素因数 p から見ても、自分の倍数より 5 小さいので、p の倍数ではない（p は末尾 9 の素数なので最小でも 19）。つまり p は x² − 5 の約数ではない。従って x² − 5 の約数である q は、S のどの要素とも異なる――リスト S に含まれない「新しい」10k+9型素数。結局、この型の素数が、リスト S 内の m 個しかないという仮定は、正しくない。□

〔例4〕　S = {19, 29} とすると、x = 2⋅19⋅29 ≡ 1102、 x² − 5 = 241⋅5039。S に含まれない10k+9型の（＝末尾 9 の）新しい素数 5039 が見つかった。

〔参考〕　「10k+9型」（言い換えれば「5k−1型」）の素数が無限にあることは、Sierpiński, Chap. 9, §2, Theorem 4 (p. 323) でも証明されている。それは相互法則を使う現代の教科書的な証明で、上記の方法と比べ「何をやっているのか」見通しが悪いが、その代わり機械的記号操作で淡々とできる。

2022-12-12　第五補充法則 Part 2　A型奇数とB型奇数

#数論　#平方剰余　#第五補充法則　#Disq. Arith.

20 で割って余りが 1, 3, 7, or 9 の数をA型と呼ぶことにする。20 で割って余りが 11, 13, 17, or 19 の数をB型と呼ぶことにする。

A型の数の例:
　　1, 3*, 7*, 9; 21, 23*, 27, 29*; 41*, 43*, 47*, 49; …
B型の数の例:
　　11*, 13*, 17*, 19*; 31*, 33, 37*, 39; 51, 53*, 57, 59*; …
どちらも末尾が 1, 3, 7, 9 だが、A型の数は「10の位が偶数」、B型の数は「10の位が奇数」。*印は素数。

直接の計算で確かめられることとして、A型の数とA型の数の積は、再びA型。

〔例〕　3 と 7 はA型。3 × 7 = 21 もA型。

この結果、次が成り立つ。

補題1　B型の数は、必ずB型の素因数を（少なくとも一つ）持つ。

〔証明〕　もしもB型の数 b の素因数 p, q, r, … が全部A型だったら、それらの積である b はA型になってしまい、つじつまが合わない。□

〔例〕　1017 はB型だから、B型の素因数を持つ（B型の数が、それ自身B型素数である可能性も含まれる）。1017は、桁の和が9なので、9の倍数。9で割ると 1017/9 = 113: これは素数（そして予言通りB型）。要するに 1017 = 3 × 3 × 113 は、A型の素因数2個とB型の素因数1個の積。

本日のメインディッシュ:

定理2　p がB型の素数（20k+11型、20k+13型、20k+17型、20k+19型）のとき、
　　『な』　x² ≡ −5 (mod p)
は解を持たない。言い換えると、法がB型素数のとき −5 は平方非剰余。

〔解説〕　例えば p = 11 の場合…。x² ≡ −5 言い換えれば x² ≡ 6 (mod 11) は、解を持たない。事実 mod 11 においては、平方数は 0² = 0, (±1)² = 1, (±2)² = 4, (±3)² = 9, (±4)² = 16 ≡ 5, (±5)² = 25 ≡ 3 の6種類だけで、何を平方しても ≡ −5 ≡ 6 にはならない。p = 11 に限らず p = 13, 17, 19, 31, 37 など、p が何であれB型の素数なら、mod p においては、何を平方しても ≡ −5 にならない（それを今から証明する）。

普通に考えると、これは平方剰余の相互法則と第一補充法則の「簡単な練習問題」だが、以下では相互法則を使わない直接証明を行う。最近100年間（特に21世紀）において、この旧道を探索した者は、ほとんどいないだろう。Gauß はこの定理を記述しているが、「全く同様に証明される」の一言で流していて、具体的な説明をしていない。Gauß が省略した証明内容の再現を試み、その後で別証明を紹介したい。

【1】 x = 0 は明らかに『な』を満たさないので、もしも『な』に解が一つでもあるとすれば、1 以上 p 未満の範囲に解がある。その範囲の一つの解を x = a とすると、x = −a ≡ p − a も当然『な』の解。この p − a も 1 以上 p 未満の範囲にある。p は奇数なので、一方の解 a が偶数なら、他方の解 p − a は奇数。一方の解が奇数なら、他方の解は偶数。

今、矛盾を導くため、定理2が間違っていると仮定する。その場合、（p = 11 に対して定理2が正しいことは上記〔解説〕内で確認済みだが） p = 13, 17, 19, 31, 37, …などを考えいくと、どこかで定理2に反するような p が出現し、その p に対して『な』が解を持つ。最初の（最小の）反例となるB型素数を p として、その p に対して、『な』の偶数の解（1 以上 p 未満の範囲にあるもの）を x = e としよう。つまり:
　　e² ≡ −5 (mod p)
　　e² + 5 ≡ 0 (mod p)

最後の式は、e² + 5 が p の倍数であるという意味なので、整数 f が存在して、次を満たす:
　　『に』　e² + 5 = pf
e は 2 以上の偶数なので e² は 4 以上の4の倍数。従って『に』の左辺は 9 以上の奇数。それに等しい右辺 pf も正の奇数、従って f も正の奇数。のみならず f は p より小さい。

なぜなら式『に』が取り得る最大値は e = p−1 の場合の (p−1)² + 5 = p² − 2p + 6。ここで −2p + 6 は、p が3より大きければ負―― p はB型素数であり、最低でも11なので、−2p + 6 は負であり、従って pf = p² − 2p + 6 は、最大でも p² 未満。だから f は p 未満。

ここまでは、おなじみのパターン（第二補充法則・第三補充法則の直接証明でもさんざん使った）。問題は、ここからどう進めるか…

【2・新版】　ガウスが考えていたと思われる方法は、次の通り。『に』の左辺は、4の倍数 e² と 5 = 4 + 1 の和なので、4 で割ると 1 余る。それと等しい右辺 pf も、4 で割ると 1 余る:
　　pf ≡ 1 (mod 4)

次に『に』を mod 5 で考えると…
　　『ぬ』　e² ≡ pf (mod 5)
…なので pf は mod 5 の平方剰余。従って、もし e が5の倍数でないとすれば（そのとき『ぬ』の両辺は5の倍数ではない）、次のようになる。

以下では「積 pf が平方剰余か非剰余か」と「その因子 p, f がそれぞれ平方剰余か非剰余か」の関係を基礎とする。Part 1 でも使ったが、冬【11】参照。

第一に、p が 20k+11 or 20k+19 の形なら、一方において p は mod 5 の平方剰余なので f も mod 5 の平方剰余であり、f を 5 で割ると 1 または 4 余る。他方において p ≡ 3 (mod 4) なので、pf ≡ 1 (mod 4) という条件から f を 4 で割ると 3 余る。この二つを両立させるためには f 自身も 20k+11 or 20k+19 の形を持たねばならない（Part 1〔例1〕参照）。従って、補題1から f はB型の素因数 q を持つ。今、『に』を mod q で考えると―― f は（従って pf も） q の倍数なので:
　　e² + 5 ≡ 0　つまり　e² ≡ −5 (mod q)
これは「p は『な』を成立させる最小のB型素数」という前提と矛盾。なぜなら f の素因数 q は当然 f 以下、その f は p 未満なので、q は p より小さい。

第ニに、p が 20k+13 or 20k+17 の形なら、一方において p は mod 5 の非剰余なので f も mod 5 の非剰余であり、f を 5 で割ると 2 または 3 余る。他方において p ≡ 3 (mod 4) なので、pf ≡ 1 (mod 4) という条件から f を 4 で割ると 1 余る。この二つを両立させるためには f 自身も 20k+13 or 20k+17 の形を持たねばならない。第一の場合同様、矛盾が生じる。

一方、もし偶数 e が5の倍数なら、e = 5E とすると、『に』はこうなる:
　　(5E)² + 5 = pf
この左辺は明らかに5の倍数。それと等しい右辺も5の倍数だが、B型素数 p は5の倍数になり得ないので、f が5の倍数。f = 5F とすると:
　　(5E)² + 5 = p(5F)　両辺を 5 で割って
　　5E² + 1 = pF
これは pF ≡ 1 (mod 5) を含意するので pF は mod 5 の平方剰余。上記第一または第二の場合と同様、F はB型の素因数 q を持ち、この q は f = 5F の素因数でもあるから、矛盾が生じる。

いずれにしても『な』に解があるという仮定は不合理。□

【2・旧版】（別証明）　直接の計算で確かめられることだが、A型の数とB型の数の積は、B型; B型の数とB型の数の積は、A型。

〔例〕　11 と 19 はB型。11 × 19 = 209 はA型。

〔参考〕　11, 13, 17, 19 をそれぞれ ≡ −9, −7, −3, −1 (mod 20) と見ると、B型は「マイナスA型」と解釈可能。「プラスA型」同士の積が再び「プラスA型」であるからには、「プラスA型」と「マイナスA型」の積が「マイナスA型」であること、そして「マイナスA型」同士の積が「プラスA型」であることは、不思議ではない。

補題2　mod 20 において、A型の数の逆数はA型で、B型の数の逆数はB型。

〔証明〕　逆数とは、掛けると ≡ 1 になる相手。1 × 1 ≡ 3 × 7 ≡ 9 × 9 ≡ 1 (mod 20) だから、A型の数 1, 3, 7, 9 の逆数はそれぞれ 1, 7, 3, 9（再びA型）。11 × 11 = 121 ≡ 1, 13 × 17 = 221 ≡ 1, 19 × 19 = 361 ≡ 1 (mod 20) だから、B型の数 11, 13, 17, 19 の逆数はそれぞれ 11, 17, 13, 19（再びB型）。□

さて『に』の左辺は、4の倍数 e² と 5 = 4 + 1 の和なので、4 で割ると 1 余る。それと等しい右辺 pf も、4 で割ると 1 余る。他方、『に』を mod 5 で考えると…
　　『ぬ』　e² ≡ pf (mod 5)
…なので pf は mod 5 の平方剰余。ゆえに、もし e が5の倍数でないとすれば（そのとき『ぬ』の両辺は5の倍数ではない）、pf を 5 で割ると 1 または 4 余る; この条件と前記「4 で割ると 1 余る」という条件が両立するためには、pf を 20 で割ると 1 または 9 余ることが必要。一方、もし e が5の倍数なら、『ぬ』の両辺は 5 の倍数。

第一に、pf を 20 で割ると 1 余るなら、pf ≡ 1 (mod 20)。つまり mod 20 において f はB型素数 p の逆数であり、補題2から f はB型。従って、補題1から f はB型の素因数 q を持つ。今、『に』を mod q で考えると―― f は（従って pf も） q の倍数なので――こうなる:
　　e² + 5 ≡ 0　つまり　e² ≡ −5 (mod q)
これは「p は『な』を成立させる最小のB型素数」という前提と矛盾。なぜなら f の素因数 q は当然 f 以下、その f は p 未満なので、q は p より小さい。

第ニに、pf を 20 で割ると 9 余るなら pf ≡ 9 (mod 20)。その両辺を 9 倍すると（9 × 9 = 81 ≡ 1 (mod 20) なので）:
　　9pf ≡ (9p)f ≡ 1 (mod 20)
ここでA型の 9 とB型の p の積 9p はB型。その逆数 f もB型だから（補題2）、B型の素因数 q を持ち（補題1）、第一の場合同様、矛盾が生じる。

第三に、偶数 e が5の倍数なら、e = 5E とすると（E: 偶数）、『に』はこうなる:
　　(5E)² + 5 = pf
この左辺は明らかに5の倍数。それと等しい右辺も5の倍数だが、B型素数 p は5の倍数になり得ないので、f が5の倍数。f = 5F とすると:
　　(5E)² + 5 = p(5F)　両辺を 5 で割って
　　5E² + 1 = pF
ここで E は偶数なので E² は4の倍数、5E² は20の倍数であり、pF は20の倍数より1大きい。つまり pF ≡ 1 (mod 20) だが、このことから、F はB型素数 p の逆数（B型）で、補題1からB型の素因数 q を持つ。この q は f = 5F の素因数でもあるから、第一の場合と同様、矛盾が生じる。

いずれにしても『な』に解があるという仮定は不合理。□

【3】　mod 5 における平方剰余・非剰余を mod 4 での分析と組み合わせて、中国剰余定理風に mod 20 に持ち込むことが、証明の鍵となった。2・旧版については、次のように進めるといくらか簡単化できる。

まず「偶数を10で割った余りは 4 or 6 か、または 2 or 8 か、または 0」ということは明白。つまり、任意の偶数は 10k±4 の形か、または 10k±2 の形か、または 10k の形を持つ。

第一に e が 10k±4 の形を持つとすると、『に』の左辺は、こうなる:
　　(10k±4)² + 5 = 100k² ± 80k + 16 + 5 = 20(5k² ± 4k + 1) + 1
すなわち20の倍数より 1 大きいので、この場合、『に』は pf ≡ 1 (mod 20) を含意する。ここから矛盾が生じるのは、2・旧版と同じ。

第ニに e が 10k±2 の形を持つとすると、『に』の左辺は、こうなる:
　　(10k±2)² + 5 = 100k² ± 40k + 4 + 5 = 20(5k² ± 2k) + 9
すなわち20の倍数より 9 大きいので、この場合、『に』は pf ≡ 9 (mod 20) を含意。後は2・旧版と同じ。

第三に e が 10k 言い換えれば 5(2k) の形を持つとして E = 2k と置くと、E は偶数で e = 5E。以下同じ。

2・旧版と 3 では、第二の場合で「両辺を 9 倍する」という変形が必要; そこが唐突で天下り的に思えるかもしれない。これは単に pf ≡ 9 の右辺を ≡ 1 に変えて逆数の議論に持ち込めるように、mod 20 における 9 の逆数 9⁻¹ を掛け算してるだけ:
　　pf ≡ 9　⇒　9⁻¹pf ≡ (9⁻¹)9　⇒　9pf ≡ 1 (mod 20)
　　　　mod 20 では 9⁻¹ が 9 自身に等しいので、ちょっと紛らわしいけど
　　　　左辺の係数 9⁻¹ の値が 9 で、右辺の (9⁻¹)9 は逆数の定義から 1
「右辺を 1 にしたいから、両辺を 9 で割った」と考えると、分かりやすいかも:
　　pf ≡ 9　⇒　pf/9 ≡ 1　⇒　pf(9⁻¹) = 9pf ≡ 1 (mod 20)

【4】　「この証明法の舞台となる世界」の構造について。「20で割った余りが 1, 3, 7, 9 の場合」がA型奇数――と言われると、「余りが 5 のケースをなぜ無視するのか」という疑問が湧く。

2・旧版と 3 では、逆数を含めて、mod 20 の世界での四則演算が使われている。ところで（全部の可能性を試せば直接確かめられることだが）、5 は mod 20 において逆数を持たない: 5x ≡ 1 (mod 20) を満たす x は存在しない。原因は「5 は法の 20 と互いに素でない」ということ…。事実 x, y にどんな整数を入れても、
　　5x + 20y
は5の倍数にしかならない（5x も 20y も5の倍数なのだから、その和が5の倍数なのは、当たり前）。mod 20 の世界では、20の倍数の違いは無視されるので（つまり 20y ≡ 0 だから）、
　　5x + 20y ≡ 5x + 0 ≡ 5x (mod 20)
もまた、5の倍数にしかならず、従って ≡ 1 にはならない（この単純で当たり前のことが、Bézout の定理のエッセンス）。逆数がないということは、割り算（それは、逆数を掛け算することに当たる）ができないということで、四則演算の対象としては、使い物にならない。余りが 15 のケースをB型に含めないのも同じ理由による（その関係で qf が5の倍数の場合とそうでない場合を別扱いする必要がある）。そもそも奇数だけを考えて、20で割って余りが偶数になる場合を はなから無視してるのも同じ理由。20 と互いに素な数だけをピックアップしている！

要するに、mod 20 の世界には20種類の要素があるものの、逆数を利用したい場合 1, 3, 7, 9; 11, 13, 17, 19 の 8 種類の要素だけを使うことになる（この 8 という個数は、オイラーのファイ関数を使うと φ(20) に当たる）。足し算・引き算の原点ともいえる 0 が含まれていないので、ある意味、不完全な世界かもしれないが、とりあえず全員逆数を持ち、単位元の 1 もあるので、この 8 種類の要素の間では掛け算・割り算が自由にでき、結合法則やら何やらも普通に成り立つ（近代的な用語を使うと「乗法について可換群を成す」）。

【5】　Gauß の議論からはそれるが、同様の手法を使って、B型素数が無限に存在することを証明できる。仮にB型素数が次の m 個しかないとしよう:
　　S = {p₁, p₂, …, p_m}
mod 20 において、B型の数の平方は ≡ 1 or 9 であることに注意する。9² = 81 ≡ 1 なので、1 or 9 (mod 20) をどういう順序でいくつ掛け合わせても、結果は依然として 1 or 9 (mod 20) のまま。すると、その4倍は ≡ 4 or 36 つまり ≡ ±4。このことから、「S の各要素の平方」の積を4倍した数 t について、次が成り立つ:
　　t = 4p₁²p₂²…p_m² ≡ ±4 (mod 20)
　　［x = 2p₁p₂…p_m とすると t = x² に当たる］
もし t ≡ 4 なら t − 5 ≡ −1 ≡ 19 (mod 20) はB型。もし t ≡ −4 なら t − 5 ≡ −9 ≡ 11 (mod 20) は、やはりB型。いずれにしても t − 5 はB型なので、B型の素因数 q を持つ（補題1）。ところが t は、S に含まれるどの素数 p から見ても自分の倍数; p の倍数より 5 小さい t − 5 は p では割り切れない（p はB型だから 11 以上）。つまり t − 5 のB型素因数 q は、S には含まれていない「新しいB型素数」であり、B型素数の個数が有限という最初の仮定は不合理。

〔例〕　B型素数が 11 と 13 の2個しかないと仮定すると:
　　t − 5 = (2⋅11⋅13)² − 5 = 81791 = 89⋅919
これら2個の素因数のうち 89 はA型だが、919 は（新しい）B型素数なので、仮定は誤り。

この方法で見つかる新しいB型素数 q は、20k+11型または20k+19型に限られ、B型といっても q ≡ 13 or 17 (mod 20) の可能性はない。なぜなら、この x は5の倍数ではないので、t − 5 = x² − 5 の素因数は、A型であれB型であれ、最下位桁が 1 or 9 に限られる（Part 1 参照）。つまり、B型素数が全体として無限にあるばかりか、より強く「20k+11型素数または20k+19型素数」だけでも無限にある（実際には、さらに強く、「20k+11型素数」だけでも無限にあり、「20k+19型素数」だけでも無限にあるはずだが、上の方法ではそこまでの結論は出せない）。

【6】　A型素数も無限に存在する。証明は【5】と同様。仮にA型素数が、
　　S = {p₁, p₂, …, p_m}
の m 個しかないとして、それらの積の 2 倍（つまり 2p₁p₂…p_m）を x とする。mod 20 において S の各要素の2乗は ≡ 1 or 9、それら全部の積も ≡ 1 or 9、ゆえに x² は 4 or 36（つまり 4 or −4）と合同。従って x² + 5 は ≡ 9 or 1 (mod 20) であり、A型の奇数。この奇数は、それ自身がA型の素数であるか、または自分より小さい素因数を持つ。ところが x² + 5 の任意の素因数 q はA型（定理2により x² + 5 はB型の素因数を持ち得ない）。さらに、x² + 5 は q で割り切れるが S のどの要素でも割り切らないので、q は S のどの要素とも異なる。

〔例〕　A型素数が 3, 7, 23, 29 の4個しかないと仮定すると:
　　x = 2⋅3⋅7⋅23⋅29 = 28014
　　x² + 5 = 784784201 = 163⋅449⋅10723
これら3個の素因数はいずれもA型であり、最初の仮定は誤り。

「B型素数を法として −5 は平方非剰余」という定理2については Disq. Arith. の art. 122 に記されているが、既に触れたように Gauß は Potest vero prorsus simili modo demonstrari（しかるに全く同様の方法で証明され得る）の一言で済ませている。直前の議論において、Gauß は mod 5 を使い、得られた結論を mod 4 で検討しているので、【2】の方法が Gauß の意図なのだろう; pf ≡ 9 のケースの扱いは自明とはいえず、これを「全く同様」で済ませるのは、ちょっと行間が広過ぎる気もする。Gauß にとっては、このくらい「説明するまでもないこと」なんだろうけど…。あるいは、もっとうまいやり方があって、mod 20 での pf の場合分けを前面に出さずに証明できるのだろうか？

追記（2022年12月13日）　うまいやり方が見つかったので、それを【2・新版】とした。これこそが Gauß の真意だろう。本質的に三つに場合分けする必要があることに違いはないが、逆数などの演算は必要なくなった。【2・旧版】も残しておく。

2022-12-24　第五補充法則 Part 3　末尾1の素数たち

5k+1型の自然数（5で割って1余る）は、k が奇数なら 6, 16, 26, … のように 6 で終わり、k が偶数なら 1, 11, 21, 31, … のように 1 で終わる。「5k+1型の素数」に話を絞るなら、後者の一部だけを考えればよく、「10k+1型の素数」と言っても全く同じ意味。

5k+1型の素数（＝10k+1型の素数）――要するに末尾が 1 の素数――は、「20k+1型」（41, 61, 101, 181, etc.）と「20k+11型」（11, 31, 71, 131, 151, 191, etc.）に細分される。

121 = 11², 141 = 3 × 47, 161 = 7 × 23; 91 = 7 × 13, 111 = 3 × 37, 171 = 3² × 19 は合成数。

もし p が「20k+11型」なら、p を 4 で割ると 3 余るので、(−1/p) = −1 となる^*: つまり −1 は mod p の非剰余（第一補充法則）。さらに、p はB型素数なので (−5/p) = −1 となる（Part 2、定理2）。この二つのことから:
　　(5/p) = (−1/p)(−5/p) = (−1)(−1) = 1
つまり 5 は mod p の平方剰余。例えば x² ≡ 5 (mod 11) は解を持つ（x ≡ ±4）。 x² ≡ 5 (mod 31) も解を持ち（x ≡ ±6）、 x² ≡ 5 (mod 71) も解を持つ（x ≡ ±17）。

*　ここで (m/p) は Legendre 記号（m は整数、p は素数）。

【1】　実は p が「20k+1型」の場合にも、5 は mod p の平方剰余。両方をまとめて:

定理3　p が5k+1型の素数なら、5 は mod p の平方剰余。（この型の素数は「20k+1型」「20k+11型」に分類可能。）

証明　素数 p = 5k+1 について {1, 2, 3, …, p−1} の任意の元 a は a^p−1 ≡ a^5k ≡ 1 (mod p) を満たす（フェルマーの小定理）。言い換えると
　　『は』　5k 次の合同式　a^5k − 1 ≡ 0 (mod p)
は 5k (= p−1) 種類の解を持つ。いったん z = a⁵ と置くと a^5k = (a⁵)^k = z^k だから、『は』はこうなる:
　　z^k − 1 = (z − 1)(z^k−1 + z^k−2 + … + z² + z + 1) ≡ 0 (mod p)
z を を a⁵ に戻すと:
　　(a⁵ − 1)(a^5(k−1) + a^5(k−2) + … + a¹⁰ + a⁵ + 1) ≡ 0 (mod p)
これが 5k 種類の解 a を持つのだから、a⁵ − 1 ≡ 0 が 5 個の解を持ち、a^5(k−1) + a^5(k−2) + … + 1 ≡ 0 が 5(k−1) 個の解を持つ。そのうち、
　　a⁵ − 1 = (a − 1)(a⁴ + a³ + a² + a + 1) ≡ 0
が 5 個の解を持つということは、a − 1 ≡ 0 が 1 個の解を持ち、a⁴ + a³ + a² + a + 1 ≡ 0 が 4 個の解を持つ。

今 a⁴ + a³ + a² + a + 1 ≡ 0 を満たす任意の a を選び、両辺を 4 倍すると:
　　4a⁴ + 4a³ + 4a² + 4a + 4 ≡ 0　つまり^{（※注1）}
　　『ひ』　(2a² + a + 2)² − 5a² ≡ 0　従って
　　『ふ』　(2a² + a + 2)² ≡ 5a² (mod p)
ゆえに mod p において、5a² は平方剰余、a² はもちろん平方剰余なので、5 も平方剰余。□

（※注1）　多項式として 4(a⁵ − 1)/(a − 1) = 4(a⁴ + a³ + a² + a + 1) が『ひ』左辺に等しいことは、直接計算で確かめられる（詳細は「4x⁴ + 4x³ + 4x² + 4x + 4 などの変形」参照）。より一般的に、n が 3 以上の素数のとき、4(aⁿ − 1)/(a − 1) について、同種の変形が成り立つ。

例えば p = 11 つまり mod 11 の場合。a ≡ 3 は a⁴ + a³ + a² + a + 1 ≡ 0 (mod 11) を満たす（81 + 27 + 9 + 3 + 1 = 121 ≡ 0）。この a = 3 を『ふ』に代入すると 23² ≡ 5⋅3² つまり 1² ≡ 5⋅3² (mod 11)、なぜなら 23 ≡ 1。ここで 5⋅3² ≡ 1² と 3² が平方剰余であることは明白。さらに:
　　『ヘ』　5 ≡ 1² / 3² ≡ 1²⋅4² ≡ 4² (mod 11)
も平方剰余（ここで 1/3 = 3⁻¹ ≡ 4 を使った。実際 3⋅4 = 12 ≡ 1）。

【2】　「法が5k+1型素数なら x² ≡ 5 に解があること」が明らかになった。もっとも、具体的に x² ≡ 5 を満たす x を求めたい場合、この方法ではまず a⁴ + a³ + a² + a + 1 ≡ 0 を満たす a を求める必要がある。2次合同式を解くために、4次合同式を解くというのは、問題がかえって複雑になるだけで、あまり実用的ではない。けれど理論的な確認の意味で（単なる好奇心だけど…）、内容を検討してみたい。

4次合同式 y⁴ + y³ + y² + y + 1 ≡ 0 の解 y は、y⁵ − 1 ≡ 0 つまり y⁵ ≡ 1 の5種類の解のうち y ≡ 1 以外の4種類。従って、いずれも位数 5。 y ≡ a がそのような解ならば y ≡ a², a³, a⁴ も解。例えば y ≡ a⁴ は
　　y⁵ ≡ (a⁴)⁵ ≡ (a⁵)⁴ ≡ 1⁴ ≡ 1
を満たす（なぜなら a⁵ ≡ 1）。さらに、a⁴a = a⁵ ≡ 1 なので a⁴ ≡ a⁻¹。同様に a³ ≡ a⁻²。

一方、『ふ』の両辺を a² で割ると:
　　(2a² + a + 2)² / a² ≡ 5
　　[(2a² + a + 2) / a]² ≡ 5
　　(2a + 1 + 2a⁻¹)² ≡ 5　つまり　[2(a + a⁻¹) + 1]² ≡ 5
従って x² ≡ 5 の解は 2(y + y⁻¹) + 1 の形を持つ（y ≡ a, a², a³, or a⁴）。a と a⁴ は互いに逆数なので、y ≡ a と y ≡ a⁴ のどちらの選択でも、丸かっこ内は等しく、同一の解が得られる。同様に y ≡ a² と y ≡ a³ は同一の解を与える。要するに 4 種類の y の選択から、実際には 2 種類の解が得られる。

x が x² ≡ 5 の解なら、当然 −x も同じ合同式の解なので、上記 2 種類の解は ±x の形になるはず。事実 y ≡ a が解
　　x ≡ 2(y + y⁻¹) + 1 ≡ 2(y + y⁴) + 1
を与えるとき、その両辺を −1 倍すれば
　　『ほ』　−x ≡ 2(−y − y⁴) − 1
となるが、y⁴ + y³ + y² + y + 1 ≡ 0 だから:
　　−y − y⁴ ≡ y² + y³ + 1
従って『ほ』の右辺は 2(y² + y³ + 1) − 1 ≡ 2(y² + y⁻²) + 1。これはまさに第2の解で、『ほ』の右辺 −x に等しい。

〔例〕　mod 11 の y ≡ 3 の場合（y⁻¹ ≡ 4）、第1の解は:
　　x ≡ 2(3 + 4) + 1 = 15 ≡ 4 (mod 11)　　『へ』と一致
第2の解 −x について、y² ≡ 9 を使うと（y⁻² ≡ 5）:
　　2(9 + 5) + 1 = 29 ≡ 7 ≡ −4 (mod 11)　　確かに −x と合同

実際上、p = 5k+1 のとき mod p において位数 5 の元 y を求めるには、4次合同式を解くよりも、g を任意の原始根として y ≡ g^k とすればいいだろう。そのとき y⁵ ≡ g^5k ≡ g^p−1 ≡ 1。

【3】　±5 が各種の法において平方剰余か非剰余かをまとめると、次のようになる。いつもと同じように、法がバニラ（4n+1の形）なら、+5 の平方性と −5 の平方性は一致し、法がチョコレート（4n+3の形）なら両者は逆になる。

±5の平方性の直接証明: ○は平方剰余 ✖は非剰余

↓mod	↓mod	5	−5	mod	根拠
5k+1	20k+1	○	○	バニラ	Part 3
5k+2	20k+3	✖	○	チョコ	Part 1
5k+3	20k+7	✖	○	チョコ	Part 1
5k+4	20k+9	○*	○*	バニラ	Part 4
5k+1	20k+11	○	✖	チョコ	Part 2 (or 3)
5k+2	20k+13	✖	✖	バニラ	Part 1 (or 2)
5k+3	20k+17	✖	✖	バニラ	Part 1 (or 2)
5k+4	20k+19	○	✖	チョコ	Part 2 (or 4)

8種類に分類すると複雑そうだが、+5 に関しては法が 5k±1 なら剰余、5k±2 なら非剰余; −5 に関しては法が 20k+9 まで（A型素数）なら剰余、20k+11 以降（B型素数）なら非剰余。5k+4型素数のうち、20k+19型については Part 2 だけからでも簡単に結論を出せるが、20k+9型（*印）については、直接的考察はかなりややこしい。下記 Part 4 では、その最後の難関に挑む。

2022-11-07　第五補充法則 Part 4　より精妙な技法

#数論　#平方剰余　#第五補充法則　#Disq. Arith.

p を 7 以上の素数とする。mod p で 5 が平方剰余か非剰余かという区別は、Fibonacci 数列の第 p 項の振る舞いに大きな影響を及ぼす（今回の話とは直接関係ないが、興味深い現象には違いない）。

さて p が5k+4型の素数の場合には、逆に Fibonacci 数列 の Binet の式のようなものを使って、mod p で 5 が平方剰余であることを証明できる。

相互法則の確立により、このような議論は必要なくなったようだが、「無理数の累乗の形で整数を表現する」という手法それ自体は、依然として興味深い。

【1】　p を 3 以上の素数として、その p に応じて p 次関数 f を次のように定義する:
　　『た』　f(x) = [(x + y)^p+1 − (x − y)^p+1] / y
　　　　ここで y = √b は定数
　　　　b は 0 以上の整数で mod p の平方非剰余の一つ

まず f(x) が実際に p 次関数であることを確かめ、次に f(x) ≡ 0 (mod p) が p 種類の解を持つことを示す。

『た』の分子（角かっこ内）を展開して引き算を実行すると、y の奇数乗を含む項だけが残る。

〔例1〕　p = 3 のとき:
(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
(x − y)⁴ = x⁴ − 4x³y + 6x²y² − 4xy³ + y⁴
　［よろしい　←係数 4, 6, 4］
上から下を引くと
(x + y)⁴ − (x − y)⁴ = 2(4x³y + 4xy³)

〔例2〕　p = 5 のとき:
(x + y)⁶ = x⁶ + 6x⁵y + 15x⁴y² + 20x³y³ + 15x²y⁴ + 6xy⁵ + y⁶
(x − y)⁶ = x⁶ − 6x⁵y + 15x⁴y² − 20x³y³ + 15x²y⁴ − 6xy⁵ + y⁶
　［ジャム！　いちごの煮汁　いちごジャム］
上から下を引くと
(x + y)⁶ − (x − y)⁶ = 2(6x⁵y + 20x³y³ + 6xy⁵)

〔例3〕　p = 7 のとき:
(x + y)⁸ = x⁸ + 8x⁷y + 28x⁶y² + 56x⁵y³ + 70x⁴y⁴ + 56x³y⁵ + 28x²y⁶ + 8xy⁷ + y⁸
(x − y)⁸ = x⁸ − 8x⁷y + 28x⁶y² − 56x⁵y³ + 70x⁴y⁴ − 56x³y⁵ + 28x²y⁶ − 8xy⁷ + y⁸
　［ハチ！　庭で転んで難渋　転んで庭でハチ］
上から下を引くと
(x + y)⁸ − (x − y)⁸ = 2(8x⁷y + 56x⁵y³ + 56x³y⁵ + 8xy⁷)

関連する二項係数は、残存する両端の項（それらの係数は p + 1）を例外として、いずれも p の倍数（Fibonacci 数列の第 p+1 項の計算と同様、p が素数の場合に起きる現象で、「一年生の夢」の一種）。『た』の分数の計算（y で割る）を行うと、分子の各項に含まれる y の奇数乗（1乗以上）は、指数が 1 ずつ減って y の偶数乗（0乗以上）に変わる; y の偶数乗 を一般的に y^2m と書くと、定義『た』から y² = b だから y^2m = b^m となり、この数は整数 b の自然数乗に等しい（左端の項では y⁰ = b⁰ = 1）。要するに『た』の f(x) は「整数を係数とする多項式」に等しく、無理数を含まない―― x が整数なら、整数値を持つ^*1。上記の例からも明らかなように、この多項式は x の p 次式（p+1 乗の項は、最初の引き算で消滅）。

*1　正確に言うと: 分子は √b の整数倍（無理数）だが、分母が √b なので、この分数は（約分すると）整数値を持つ。

p = 7 の〔例3〕でいえば:
　　f(x) = [(x + y)⁸ − (x − y)⁸]/y = 2(8x⁷y + 56x⁵y³ + 56x³y⁵ + 8xy⁷)/y
　　= 2(8x⁷ + 56x⁵y² + 56x³y⁴ + 8xy⁶) = 2(8x⁷ + 56x⁵b + 56x³b² + 8xb³)
ここで b は整数。右端の項に含まれる b のべきは、y⁶ = b³、一般の p については y^p−1 = b^(p−1)/2。

p を法として、p の倍数の項を無視し、両端の項だけを考えると、p = 7 の例では:
　　f(x) ≡ 2(8x⁷ + 8xb³) ≡ 2⋅8(x⁷ + xb³) (mod 7)
一般の p について:
　　f(x) ≡ 2[(p + 1)x^py + (p + 1)xy^p]/y ≡ 2(p + 1)(x^p + xy^p−1)
　　つまり f(x) ≡ 2(p + 1)(x^p + xb^(p−1)/2) (mod p)
この右辺において^†、フェルマーの小定理から x^p ≡ x; オイラーの基準から b^(p−1)/2 ≡ −1。従って、x の値と無関係に、常にこうなる:
　　f(x) ≡ 2(p + 1)(x − x) ≡ 2(p + 1)⋅0 ≡ 0 (mod p)
言い換えると、p 次方程式 f(x) ≡ 0 (mod p) は、p 種類の解 x ≡ 0, 1, 2, …, p−1 を持つ。

†　あるいは x を1個くくり出すと、右辺 ≡ 2(p + 1)x(x^p−1 + b^(p−1)/2) ≡ 2(p + 1)x(1 + (−1)) ≡ 0。

〔例4〕　p = 3 の場合。〔例1〕から f(x) = 2(4x³y + 4xy³)/y = 2(4x³ + 4xy²)
mod 3 の平方非剰余 b = 2 を使い y² = 2 を代入すると: f(x) = 2(4x³ + 8x)
f(0) = 0, f(1) = 24, f(2) = 96 は、いずれも 3 の倍数。つまり ≡ 0 (mod 3) を満たす。
もしも b として（間違って）平方剰余の 1 を使い、y² = 1 を代入すると f(x) = 2(4x³ + 4x)。この場合 f(1) = 16, f(2) = 80 で、3の倍数にならない（オイラーの基準の符号が逆になるため）。

〔例5〕　p = 19 の場合:
　　f(x) = (x²⁰ + ₂₀C₁x¹⁹y + ₂₀C₂x¹⁸y² + … + ₂₀C₁₉xy¹⁹ + y²⁰)/y
　　      − (x²⁰ − ₂₀C₁x¹⁹y + ₂₀C₂x¹⁸y² − … − ₂₀C₁₉xy¹⁹ + y²⁰)/y
　　= 2(₂₀C₁x¹⁹y + ₂₀C₃x¹⁷y³ + … + ₂₀C₁₇x³y¹⁷ + ₂₀C₁₉xy¹⁹)/y
　　= 2(₂₀C₁x¹⁹ + ₂₀C₃x¹⁷y² + … + ₂₀C₁₇x³y¹⁶ + ₂₀C₁₉xy¹⁸)
上記の二項係数は ₂₀C₁ = ₂₀C₁₉ = 20 を除き、どれも19の倍数なので:
　　f(x) ≡ 2(20x¹⁹ + 20xy¹⁸) ≡ 2⋅20(x¹⁹ + xb^(19−1)/2) ≡ 2⋅20(x − x) (mod 19)

b の例として b = 2 とすると（第二補充法則から 2 は mod 19 の非剰余）、f(1) = 31988856, f(2) = 32756588544 などは、どれも19の倍数。

別の例として b = 3 とすると（第三補充法則から 3 も mod 19 の非剰余）、f(1) = 309895168, f(2) = 158631825968 などは、どれも19の倍数。

〔追記〕　明示的な20乗の二項展開は次の通り。
(x+y)^20==x^20+ 20*x^19*y+ 190*x^18*y^2+ 1140*x^17*y^3
+ 4845*x^16*y^4+ 15504*x^15*y^5+ 38760*x^14*y^6
+ 77520*x^13*y^7+ 125970*x^12*y^8+ 167960*x^11*y^9+ 184756*x^10*y^10
+ 167960*x^9*y^11+ 125970*x^8*y^12+ 77520*x^7*y^13
+ 38760*x^6*y^14+ 15504*x^5*y^15+ 4845*x^4*y^16
+ 1140*x^3*y^17+ 190*x^2*y^18+ 20*x*y^19+ y^20
ポイントは、19 から 184756 までの係数が19で割り切れること、つまり mod 19 で ≡ 0 であること。それもそのはず、19 = 19/1! や 190 = 20⋅19/2! や 1140 = 20⋅19⋅18/3! や 4845 = 20⋅19⋅18⋅17/4! などの分子には因子19があるが、分母には19がないので、約分してできる整数には因子19が残る（後半 x^9 から x^0 までの係数は、前半 y^9 から y^0 までの係数と同じ、言い換えれば x^20 から x^11 までの係数の逆順）。重要なのは「係数のほとんどが ≡ 0 になること」であり「具体的な係数の値」は関係ない。けれどもし、この二項定数をベタに暗記したい物好きな人がいれば、次の語呂合わせを使うことができる（0 を「ラブ」と読む）:
　　二人でラブ　一休ラブ　いいよラブ
　　よっぱらったヨーコ　イチゴ困るよ　実（み）はなろうラブ
　　菜々子にラブ　一二を争う酷なラブ　いろんな苦労のラブ　一夜限りよ夏の頃
（ちなみに、15乗の展開の語呂合わせによると「ヨーコ」には「イチゴ」という子がいて、19乗の展開の語呂合わせには「一休」「実はなろう」という部分がある。それらのフレーズが再登場している。）

【2】　以下では、p が5k+4型の素数^*2（19, 29, 59 など）の場合を考える。

*2　「5k−1型」「10k+9型」「10k−1型」とも呼べる。±5 の平方性の直接証明において、この型の素数が最も難しいが、このメモで紹介する手法が奏功する（実用上は、わざわざ直接的に証明する必要はなく、平方剰余の相互法則を使って簡単に処理される）。

次の4次関数 g は、関数 f が含むのと同じ b を含む:
　　g(x) = [(x + y)⁵ − (x − y)⁵] / y　　‥‥①
　　 = (x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵)/y
　　  −(x⁵ − 5x⁴y + 10x³y² − 10x²y³ + 5xy⁴ − y⁵)/y
　　 = 2(5x⁴y + 10x²y³ + y⁵)/y
　　 = 10x⁴ + 20x²y² + 2y⁴ = 10x⁴ + 20bx² + 2b²　　‥‥②

f(x) の定義式では (x + y) などの指数が「素数+1」だが、g(x) では、その指数が素数 5 になっている。

説明の便宜上 U = (x + y)⁵, V = (x − y)⁵ と置くと、①をこう書ける（②と等しい多項式関数）:
　　『ち』　g(x) = (U − V)/y

今 p + 1 = 5n とすると（p は5k+4型なので n は整数）、【1】の関数…
　　f(x) = [(x + y)⁵ⁿ − (x − y)⁵ⁿ] / y = (Uⁿ − Vⁿ)/y
　　 = (U − V)(Uⁿ⁻¹ + Uⁿ⁻²V + … + UVⁿ⁻² + Vⁿ⁻¹)/y　　‥‥③
…は、多項式として、明らかに『ち』で割り切れる。f(x) = g(x) h(x) として③を参照すると:
　　h(x) = Uⁿ⁻¹ + Uⁿ⁻²V + … + UVⁿ⁻² + Vⁿ⁻¹
これは x について p−4 次式なので^*3、mod p において h(x) ≡ 0 の解は p−4 種類以下。4次関数 g(x) ≡ 0 の解は、もちろん 4 種類以下。他方 f(x) ≡ 0 が p 種類の解を持つことは分かっているので（【1】）、g(x) ≡ 0 も h(x) ≡ 0 も可能な上限いっぱいの解を持つ必要がある。すなわち g(x) ≡ 0 を満たす4種類の x が存在する。

*3　p 次式を 4 次式で割った商なので。別の観点として、h は U や V の n−1 次式だが、U や V 自体は x の5次式なので、h は x の 5(n−1) 次式。ところが n = (p+1)/5 なので、その両辺から 1 を引くと n−1 = (p−4)/5 すなわち 5(n−1) = p−4。従って x の 5(n−1) 次式 h とは、x の p−4 次式に他ならない。

〔例6〕　例5について: p = 19, b = 2 のとき g(x) = 10x⁴ + 40x² + 8 ≡ 0 (mod 19) は、4種類の解 x ≡ ±3, ±5 を持つ。例えば g(3) = 1178 は 19 の倍数。

〔例7〕　例5について: p = 19, b = 3 のとき g(x) = 10x⁴ + 60x² + 18 ≡ 0 (mod 19) は、4種類の解 x ≡ ±2, ±3 を持つ。例えば g(−2) = 418 は 19 の倍数。

g(x) = 10x⁴ + 20bx² + 2b² ≡ 0 (mod p) を成立させる4種類の x のどれを考えても（②参照）、解 x 自身が ≡ 0 になることは、あり得ない。なぜなら、もしも g(0) ≡ 0 が成立するなら 2b² ≡ 0 つまり b ≡ 0 (mod p) となるが、それは「b が平方非剰余」という前提に反する。

【3】　g(x) = 10x⁴ + 20bx² + 2b² ≡ 0 (mod p) に（4種類の）解があることは確定したので、その一つを x = a とすると:
　　g(a) = 2(5a⁴ + 10a²b + b²) = 2[(5a² + b)² − 20a⁴] ≡ 0
両辺を 2 で割ると (5a² + b)² − 20a⁴ ≡ 0、移項して…
　　(5a² + b)² ≡ 20a⁴ (mod p)
…は平方剰余。右辺は 5 と 4a⁴ の積で、4a⁴ = (2a²)² は平方剰余なので、5 も平方剰余。実際…
　　(5a² + b)² ≡ 5(2a²)² (mod p)
…の両辺に (2a²)² の逆数^*4を掛けて、整理すると:
　　『つ』　[(5a² + b)(2a²)⁻¹]² ≡ 5 (mod p)

*4　逆数が存在するためには (2a²)² ≢ 0 すなわち a ≢ 0 でなければならないが、前述のように、その条件は満たされている。

合同式『つ』によって、法が5k+4型の素数のとき、5 は平方剰余。すなわち
　　『て』　x ≡ (5a² + b)(2a²)⁻¹
を平方すると ≡ 5 (mod p) になる。□

x² ≡ 5 (mod p) の具体的な解を知りたい場合、『て』はあまり便利ではない。計算に必要な a を得るには、まず mod p での非剰余 b を見つけ、4次方程式 g(x) = 10x⁴ + 20bx² + 2b² ≡ 0 すなわち 5x⁴ + 10bx² + b² ≡ 0 を解かねばならない。y = x² と置くと…
　　5y² + 10by + b² ≡ 0
…となるが、シンプルな2次方程式 x² ≡ 5 が、むしろ複雑になったように思える。けれど x² ≡ 5 (mod p) が与えれたとき、何らかの仕組みを使わないことには「そもそも解があるのか？」ということすら、明らかでない。『つ』『て』は解を求めるための「公式」というより（原理的にはそういう使い方もできるが）、「5k+4型の任意の素数 p について x² ≡ 5 (mod p) を満たす x がある」という存在証明を目的としている。

〔例8〕　例6について: p = 19, b = 2, a = ±3 のとき (5a² + b)(2a²)⁻¹ = 47⋅18⁻¹ ≡ 10 (mod 19)。確かに 10² ≡ 5。一方 a = ±5 のとき (5a² + b)(2a²)⁻¹ = 127⋅50⁻¹ ≡ 9 (mod 19)。確かに 9² ≡ 5。要するに（10 ≡ −9 に注意すると）、x² ≡ 5 (mod 19) の解は x ≡ ±9。

〔例9〕　例7について: p = 19, b = 3, a = ±2 のとき (5a² + b)(2a²)⁻¹ = 23⋅8⁻¹ ≡ 10。a = ±3 のとき (5a² + b)(2a²)⁻¹ = 48⋅18⁻¹ ≡ 9 (mod 19)。

Binet の公式のようなこのアプローチは、Gauß のオリジナルではなく、Lagrange によるものらしい。個々のケースについて平方性を直接（相互法則を使わずに）証明しようとすると、このように、小さな素数 5 でも複雑な議論になり、その先で行き詰まる（Gauß 自身、±7 の平方性については、直接には証明を完成させていない）。一般のケースを自由に扱える「相互法則」との関係でいえば、この手法は「あまり拡張性のない窮余の策」かもしれない。けれど、手法それ自体が面白い。5n+4型素数についてのこの議論は、歴史に埋もれている珠玉だろう。Gauß 自身「より精妙な技法たち」（subtiliora artificia）と記している（DA 123）。

このメモでは、g の定義式で (x + y) の肩に付く指数を最初から 5 に固定している。手法自体の一般論としては、この指数として p+1 の任意の（2 以上 p 以下の）約数 e を使うことができる。「整数 b が負でない」という指定は便宜上のもので、原文にはない。

2022-12-18　4x⁴ + 4x³ + 4x² + 4x + 4 などの変形　実践的アプローチ

#数論　#円分多項式　#第五補充法則　#Disq. Arith.

4x⁴ + 4x³ + 4x² + 4x + 4 を
　　= (2x² + x + 2)² − 5x²
としたり、4x⁶ + 4x⁵ + 4x⁴ + 4x³ + 4x² + 4x + 4 を
　　= (2x³ + x² − x − 2)² + 7(x² + x)²
としたりする変形は、それ自体として面白く、場合によっては重要な切り札となる。ところが――変形結果を見せられて、それが正しいことを確認するのは機械的にできるものの――自力でこのタイプの変形をやろうとすると、何がどうなるのか見通しにくい。このメモでは、理論的な深い分析には立ち入らず、とりあえずツールとして、この種の変形を一応自由に使えるように準備したい。p が 3 以上の小さい素数のとき、
　　4(x^p−1 + x^p−2 + … + x + 1) = Y² ∓ pZ²
の形の多項式 Y, Z が何になるか、手っ取り早く調べておく。

【1】　上記 Y² ∓ pZ² の複号は p が4k+1型なら上（マイナス）、4k+3型なら下（プラス）を選ぶ必要がある。p = 3 のときの 4(x² + x + 1) = 4x² + 4x + 4 = (2x + 1)² + 3 については、悩む余地はないだろう。Y² ∓ pZ² の形に当てはめれば Y = 2x + 1, Z = 1 に当たる。

p = 5, 7 の場合の変形は、自明ではない:
　　《ア》　4(x⁴ + x³ + x² + x + 1) = (2x² + x + 2)² − 5x²
　　　　つまり Y = 2x² + x + 2, Z = x
　　《イ》　4(x⁶ + x⁵ + x⁴ + x³ + x² + x + 1) = (2x³ + x² − x − 2)² + 7x²(x + 1)²
　　　　つまり Y = 2x³ + x² − x − 2, Z = x(x + 1)

《ア》《イ》の検証や以降の検討では、次のような恒等式を利用する:
　　(a + b + c)² = a² + b² + c² + 2(ab + ac + bc)
各項の2乗を足し合わせ、さらに「全部の項を（自分自身以外と）総当たりで掛け合わせた積の和」の2倍を足し合わせる（この式の導出については『メ』～『モ』参照）。これは基本公式
　　(a + b)² = a² + b² + 2(ab)
の拡張版に当たる。さらに4項に拡張すると:
　　(a + b + c + d)² = a² + b² + c² + d² + 2(ab + ac + ad + bc + bd + cd)
5項以上でも同様。

m 項式の平方は次のように展開される:
　　(a₁ + a₂ + a₃ + a₄ + … + a_m)²
　　 = a₁² + a₂² + a₃² + a₄² + … + a_m²　　←各項の2乗の和
　　 + 2(a₁a₂ + a₁a₃ + a₁a₄ + … + a₁a_m)　　←a₁ を a₂ 以降の各項と総当たりで掛け算
　　 + 2(a₂a₃ + a₂a₄ + … + a₂a_m)　　←a₂ を a₃ 以降と総当たりで掛け算
　　 + 2(a₃a₄ + … + a₃a_m)　　←a₃ を a₄ 以降と総当たりで掛け算
　　 + …
　　 + 2(a_m−1a_m)

特に (az² + bz + c)² = a²z⁴ + 2abz³ + (b² + 2ac)z² + 2bcz + c²
(az³ + bz² + cz + d)² = a²z⁶ + 2abz⁵ + (b² + 2ac)z⁴ + 2(ad + bc)z³ + (c² + 2bd)z² + 2cdz + d²

《ア》の検証（p = 5）:
Y² = (2x² + x + 2)² = 4x⁴ + x² + 4 + 2(2x³ + 4x² + 2x) = 4x⁴ + 4x³ + 9x² + 4x + 4
だから Y² − 5Z² = (2x² + x + 2)² − 5x² = 4x⁴ + 4x³ + 4x² + 4x + 4 = 《ア》左辺

《イ》の検証（p = 7）:
Y² = (2x³ + x² − x − 2)²
= 4x⁶ + x⁴ + x² + 4 + 2(2x⁵ − 2x⁴ − 4x³ − x³ − 2x² + 2x)
= 4x⁶ + 4x⁵ − 3x⁴ − 10x³ − 3x² + 4x + 4;
7Z² = 7x²(x² + 2x + 1) = 7x⁴ + 14x³ + 7x²
だから Y² + 7Z² = 4x⁶ + 4x⁵ + 4x⁴ + 4x³ + 4x² + 4x + 4

p が 5 以上の素数の場合、次のような特徴がある。第一に、Y は p/2 次式（端数切り捨て）。例えば p = 7 なら3次式になる。第二に、Y の最高次の係数は 2 で、その次の係数は 1。例えば Y が3次式なら 2x³ + x² … と始まる。第三に、Y の係数は、回文的（左から読んでも右から読んでも絶対値が同じ）: p が4k+1型なら符号も含めて回文、4k+3型なら「逆さまに読むと符号が反対」の回文になる。例えば p = 5 の場合、左から順に 2, 1, 2。 p = 7 の場合 2, 1, −1, −2。この回文的性質と、前述の「係数が 2, 1 から始まる」という性質を組み合わせれば、《ア》《イ》については個別的に覚えるまでもなく、多項式 Y の係数は自動的に決まる。

第四に、Z は必ず因子 x を持ち、従って Z = xW, Z² = x²W² と書ける。W の次数は Y の次数より 2 小さい（例: Y が3次式なら W は1次式）。p = 7 の場合の Z = x(x + 1) でいえば W = x + 1、 pZ² = 7[x(x + 1)]² = 7x²W² となる。第五に、W の最高次の係数は 1。第六に、W の係数は、符号も含めて回文的（p = 7 の場合 1, 1）。従って、W の定数項は 1。――これらの観察から、p = 5, 7 の場合の Y と W（従って Y と Z）は、完全に確定する！

【2】　以上の観察だけから p = 11 の場合の式を自力で作れるか、試してみる。その場合には…
　　Y は5次式で、係数は逆符号の回文 2, 1, q, −q, −1, −2　（係数 q は不明）
　　つまり　Y = 2x⁵ + x⁴ + qx³ − qx² − x − 2 の形

分からないのは q だけなので、そのくらいなら係数の比較で何とかなるだろう。4(x¹⁰ + x⁹ + x⁸ + … + 1) が Y² + 11x²W²、つまり…
　　《ウ》　(2x⁵ + x⁴ + qx³ − qx² − x − 2)² + 11x²W²
…に一致するように係数 q を決定すればいい。試行錯誤によっても解決可能だが、次のようにすれば、構成的な議論ができる。

《ウ》の和が 4(x¹⁰ + x⁹ + x⁸ + … + 1) に等しいのだから:
　　《エ》　4(x¹⁰ + x⁹ + x⁸ + … + 1) − (2x⁵ + x⁴ + qx³ − qx² − x − 2)² = 11x²W²
右辺は、多項式として11の倍数なので、それに等しい左辺も11の倍数: 左辺を整理すると、各係数が11の倍数（−11, 0, 11 など）になるはず（そうでないと左辺の式は 11 で割り切れず、つじつまが合わない）。

《エ》左辺・第1項について、10次・9次の係数はもちろん 4。《エ》左辺・第2項（丸かっこ2乗の部分）について、10次・9次の項はそれぞれ (2x⁵)² = 4x¹⁰ と 2(2x⁵⋅x⁴) = 4x⁹ なので、引き算をすると《エ》左辺の10次・9次の係数は 0。ゼロだから無いのと同じだが、11 の倍数には違いない。

同様に《エ》左辺・第1項の8次の係数は 4。《エ》左辺・第2項の8次の項は (x⁴)² + 2(2x⁵qx³) = (1 + 4q)x⁸ なので、係数の引き算をすると、《エ》左辺の8次の係数は 4 − (1 + 4q) = 3 − 4q。これが11の倍数になるように、整数 q を選ぶ:
　　3 − 4q ≡ 11　つまり　−4q ≡ 8 (mod 11)
絶対値最小の解は q = −2。この他、q = 9, −13 など −2 + 11n の形の数（n は任意の整数）は上記の条件を満たすが、Y に含まれる係数はどれも比較的小さい――実は p が 40 以下なら（つまり数値計算上、現実的に必要になるほぼ全範囲において）、どの係数も絶対値 p/2 未満であり、係数における p の整数倍の違いが曖昧さを生じさせることはない。

今 q = −2 とすると、《エ》左辺・第2項について:
　　(2x⁵ + x⁴ − 2x³ + 2x² − x − 2)²
　　= 4x¹⁰         + x⁸          + 4x⁶         + 4x⁴             + x²            + 4
　　    + 2(2x⁹ − 4x⁸ + 4x⁷ − 2x⁶ − 4x⁵)
　　                      + 2(−2x⁷ + 2x⁶ − x⁵ − 2x⁴)
　　                                        + 2(−4x⁵ + 2x⁴ + 4x³)
　　                                                         + 2(−2x³ − 4x²) + 2(2x)
　　= 4x¹⁰ + 4x⁹ − 7x⁸ + 4x⁷ + 4x⁶ − 18x⁵ + 4x⁴ + 4x³ − 7x² + 4x + 4
従って《エ》左辺の引き算を行うと、《エ》はこうなる（全部の係数は11の倍数）:
　　11x⁸ + 22x⁵ + 11x² = 11x²W²　両辺を 11x² で割ると
　　x⁶ + 2x³ + 1 = W²　すなわち　(x³ + 1)² = W²

きっちり、希望通りの形になった！　これで係数 q = −2 と多項式 W² が確定し、《ウ》はこうなる:
　　《オ》　4(x¹⁰ + x⁹ + … + 1) = (2x⁵ + x⁴ − 2x³ + 2x² − x − 2)² + 11x²(x³ + 1)²

〔検算〕　x = 1 のとき《オ》左辺は 4(11) = 44、右辺は 0² + 11(2)² = 44、一致。x = −1, 2, −2 のとき、両辺はそれぞれ 4, 8188, 2732 で一致。ちなみに、左辺は多項式として f(x) = 4(x¹¹ − 1)/(x − 1) に等しいが、この f に直接 x = 1 を代入することはできない（分母が 0 になってしまうため）。

n が素数のとき、ある変数の 0 乗から n−1 乗までを足し合わせた多項式は（n 番目の）「円分多項式」に呼ばれるものに当たる。例えば
　　x⁴ + x³ + x² + x + 1
は、5番目の円分多項式。

〔参考〕　n が素数でない場合にも「円分多項式」は定義されるが、上記とは形が異なる。別のメモで、12k+1型素数が無限に存在することを証明するとき、12番目の円分多項式を使っている。

【3】　ここまでのまとめ。p が奇素数のとき、p 番目の円分多項式 X の4倍…
　　4X = 4(x^p−1 + x^p−2 + … + 1) = 4x^p−1 + 4x^p−2 + … + 4
…は、「平方」と「平方の p 倍」の差または和 Y² ∓ pZ² の形で表現可能（Y = g(x), Z = h(x) は整数係数の多項式）。ここではそれを一般的に証明したわけではないが、小さい p について、事実そうなることを確かめた。p = 3 の場合の次の恒等式は自明だが、役立つことがある:

円分多項式に関するガウスの公式（p = 3）
　　4x² + 4x + 4 = (2x + 1)² + 3

p = 3 のケースは、第三補充法則の定理5の証明の鍵となった。p = 5 のケースは第五補充法則 Part 3 で必要になり、p = 7 のケースは「第七補充法則」と関係するだろう。

p = 5, 7 の場合、一見予想がつかないような形をしているが、全ては一定のパターンに従っているのだった:

円分多項式に関するガウスの公式（p = 5, 7）
　　4x⁴ + 4x³ + 4x² + 4x + 4 = (2x² + x + 2)² − 5x²
　　4x⁶ + 4x⁵ + 4x⁴ + 4x³ + 4x² + 4x + 4 = (2x³ + x² − x − 2)² + 7x²(x + 1)²

パターンを復習すると: p ≥ 5 のとき、右辺は Y² ∓ px²W² の形。p が4k+1型なら ∓ の複号はマイナスだが、Y の回文はシンプル（符号が入れ替わらない）。p が4k+3型なら複号はプラスだが、その代わり Y の回文は、順方向で読んだ場合と逆方向で読んだ場合で、符号が反対になる。Y の次数は、左辺の次数の半分で、係数は 2, 1 と始まる。W の次数は Y の次数より 2 小さく、最初の係数は 1 で、符号も含めて回文的（p = 5 の場合の0次式 W = 1 については、上記では表記省略）。

p = 11 の場合、上のパターンだけでは確定できない係数 q, a がある:
　　4x¹⁰ + 4x⁹ + … + 4x + 4 = (2x⁵ + x⁴ + qx³ − qx² − x − 2)² + 11x²(x³ + ax² + ax + 1)²

これについては q = −2 を覚えておいてもいいが、覚えてなくても【2】のように導出できる（q を決定すると a = 0 は自動的に決まる）。

円分多項式に関するガウスの公式（p = 11）
　　4x¹⁰ + 4x⁹ + 4x⁸ + … + 4x² + 4x + 4 = (2x⁵ + x⁴ − 2x³ + 2x² − x − 2)² + 11x²(x³ + 1)²

【4】　p = 13 の例。q, r を未知の係数として、
　　Y² = (2x⁶ + x⁵ + qx⁴ + rx³ + qx² + x + 2)²
から 13x²W² を引いたものが、多項式として次の式に等しくなる:
　　4X = 4x¹² + 4x¹¹ + 4x¹⁰ + 4x⁹ + … + 4x + 4

これは【2】と似ているが、p が4k+1型なので、4X = Y² ∓ px²W² の ∓ の選択が逆（マイナス）になる。それでも Y² と 4X の差が、多項式として p の倍数 px²W² になることに変わりはない。この例では、Y² の12次の項は (2x⁶)²、11次の項は 2(2x⁶x⁵)。Y² − 4X の引き算を行うと、それぞれ 4X の12次・11次の項と打ち消し合う。W は4次式、px²W² は10次式になるはずだから、12次・11次の項が消滅するのは、つじつまが合っている。

だからこそ Y の係数は 2, 1 と始まるのであり、同様の打ち消し合いは p = 11, 13 に限らず、p が 5 以上の素数のとき、一般的に成り立つ: その結果、pZ² = px²W² は X や Y² より次数が 2 小さい。

Y² の10次の項 (x⁵)² + 2(2x⁶qx⁴) の係数は 1 + 4q。そこから 4X の10次の係数 4 を引いた 4q − 3 が 13 の倍数になるのだから、q = 4 と推定される。

Y² の8次の項 (qx⁴)² + 2(x⁵rx³ + 2x⁶qx²) の係数は q² + 2(r + 2q) = 32 + 2r。そこから 4X の8次の係数 4 を引いた 28 + 2r が 13 の倍数になるのだから、r = −1 と推定される。

実際、q = 4, r = −1 とすると:
　　13x²W² = Y² − 4X
　　= (2x⁶ + x⁵ + 4x⁴ − x³ + 4x² + x + 2)² − 4(x¹² + x¹¹ + … + x + 1)
　　= 13x¹⁰ + 26x⁸ + 39x⁶ + 26x⁴ + 13x²
予定通り、13 で割り切れる回文的多項式（符号も回文）が得られた！　両辺を 13x² で割って:
　　W² = x⁸ + 2x⁶ + 3x⁴ + 2x² + 1　　(*)
この式から、下記のようにして、容易に次の結論を得る:
　　W = x⁴ + x² + 1

すなわち W² が (*) の右辺の8次式（それは偶数次の項だけを持つ）に等しく、しかも W の最高次の係数と定数項が 1 なのだから（このことは式の形からも明らかだが、【1】の観察の第五・第六に当たる）、
　　W = x⁴ + ax² + 1
と置いて、その平方と (*) の係数を比較すれば a = 1。あるいは、同じことだが、z = x², W = z² + az + 1 と置いて、その平方と
　　z⁴ + 2z³ + 3z² + 2z + 1
を比較してもいい。

〔付記〕　天下り的に恒等式 (z² + z + 1)² = z⁴ + 2z³ + 3z² + 2z + 1 を使うなら、(*) で z = x² と置けば、直ちに同じ結論を得る。

円分多項式に関するガウスの公式（p = 13）
　　4x¹² + 4x¹¹ + 4x¹⁰ + … + 4x² + 4x + 4 = (2x⁶ + x⁵ + 4x⁴ − x³ + 4x² + x + 2)² + 13x²(x⁴ + x² + 1)²

【5】　このような導出は、体系的な理論に裏打ちされたものではなく、その場しのぎで不透明だが、一応実用になるだろう。

同様に、ゴチャゴチャするが本質的には単純な機械的計算により、p = 17 の場合の式も導出可能。16次式 Y² の3個の不明な係数 q, r, s は、係数が17の倍数（絶対値 17/2 未満）ということから順に 5, 7, 4 となり、引き算などによって12次式 W² が確定。それが
　　(x⁶ + ax⁵ + bx⁴ + cx³ + bx² + ax + 1)²
と等しいことから、係数を比較すると a, b, c は順に 1, 1, 2 となる。

その場しのぎではない理論と計算については、[1][2][3][4] 参照。

〔文献〕
[1] Gauß: Disq. Arith., art. 357
[2] Riesel: Prime Numbers and Computer Methods for Factorization (2nd ed.), “A Formula by Gauss for xⁿ − yⁿ” in Appendix 6; “Gauss’ Formulas for Cyclotomic Polynomials” (Table 23)
[3] Dirichlet & Dedekind: Vorlesungen, Supplement VII (§§138–140)
[4] Brent: On computing factors of cyclotomic polynomials
https://arxiv.org/abs/1004.5466
「p を素数に限らず、平方因子を含まない 3 以上の奇数に一般化したのは Kraïtchik だ」と [2] に記されているが、実際には Dirichlet & Dedekind [3] が既に p = 15 を扱っている。Kraïtchik の研究については、確認できなかった。

---