メモ（数論8）: 平方剰余の相互法則

チラ裏　＞　数論　＞　メモ8

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

Gauß / Dirichlet の源流を訪ね、どうやって発見されたのか一歩一歩たどる。目指すは世界一分かりやすい説明！

• 2022-07-26　ウィルソンの定理から第一補充法則　びっくりマークの謎！
• 2022-07-23　第二補充法則の簡単な証明・夏秋　教科書の方法より10倍簡単（当社比ｗ）
• 2022-07-27　第二補充法則の簡単な証明・冬
• 2022-07-29　第二補充法則の簡単な証明・春
• 2022-08-03　ガウスの補題　Gauß の第三証明 Dirichlet 版・完全解説 1/3
• 2022-08-07　平方剰余の相互法則　Gauß の第三証明 Dirichlet 版 2/3
• 2022-08-09　平方剰余の相互法則（続き）　Gauß の第三証明 Dirichlet 版 3/3
• 2022-08-19　知られざるアイゼンシュタイン　Eisensteinによる相互法則の証明 1/2
• 2022-08-20　アイゼンシュタインのトリック　Eisensteinによる相互法則の証明 2/2
• 2022-09-06　アイゼンシュタインの証明の現代化　目で見る相互法則
• 2022-08-25　第二補充法則の散歩道　数論のスローライフ
• 2022-09-01　第二補充法則の散歩道・2　四乗剰余の冒険
• 2022-09-03　第二補充法則の散歩道・3　ガウスの手書きメモ

2022-07-26　ウィルソンの定理から第一補充法則　びっくりマークの謎！

いわゆる Wilson の定理を導入し、オイラーの基準、フェルマーの小定理の別証明、第一補充法則を導く。

【1】　1 から n までの全部の整数を掛け合わせたものを n! で表し、n の階乗という（n は自然数）。

〔例〕　4! = 1 × 2 × 3 × 4 = 24。　6! = 1 × 2 × 3 × 4 × 5 × 6 = 720。

n! に 1 を足したものを n + 1 と比較すると…

n = 1 のとき n! = 1

n! + 1 = 2 は n + 1 = 2 で割り切れる

n = 2 のとき n! = 1 × 2 = 2

n! + 1 = 3 は n + 1 = 3 で割り切れる

n = 3 のとき n! = 1 × 2 × 3 = 6

n! + 1 = 7 は n + 1 = 4 で割り切れない

n = 4 のとき n! = 1 × 2 × 3 × 4 = 24

n! + 1 = 25 は n + 1 = 5 で割り切れる

n = 5 のとき n! = 1 × 2 × 3 × 4 × 5 = 120

n! + 1 = 121 は n + 1 = 6 で割り切れない

n = 6 のとき n! = 1 × 2 × 3 × 4 × 5 × 6 = 720

n! + 1 = 721 は n + 1 = 7 で割り切れる

n = 7 のとき n! = 1 × 2 × 3 × 4 × 5 × 6 × 7 = 5040

n! + 1 = 5041 は n + 1 = 8 で割り切れない

n = 8 のとき n! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 = 40320

n! + 1 = 40321 は n + 1 = 9 で割り切れない^*1

n = 9 のとき n! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 = 362880

n! + 1 = 362881 は n + 1 = 10 で割り切れない

n = 10 のとき n! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 = 3628800

n! + 1 = 3628801 は n + 1 = 11 で割り切れる^*2

n + 1 が素数なら、その素数で n! + 1 は割り切れるようだ。n + 1 を p と置くと、n = p − 1 となって:

Wilson–Lagrange の定理　p が素数なら、(p−1)! + 1 は p で割り切れる。

この法則は、英国の Wilson によって観察され、Lagrange によって証明された。以下では、Dirichlet の伴侶論法^*3を使ってこれを証明し、話を発展させたい。

直接の目標は、8k+3型・8k+7型素数がそれぞれ無限に存在することを証明し、8k+○型シリーズを完成させること。そのために、第二補充法則を使いたい。そのために、第一補充法則とガウスの基準を使いたい。…この流れで、平方剰余の相互法則について、ガウスの第三証明を紹介したい。

ところで、上記のパターンは、フェルマーの小定理と似ている（両者は本質的に同じ現象）。

*1　「9で割り切れるか」を調べるショートカットとして、その数の各桁を足す方法がある: 40321 → 4+0+3+2+1 = 10 は 9 の倍数でないので、40321 も 9 で割り切れない。

*2　「11で割り切れるか」を調べるショートカットとして、奇数桁の和から偶数桁の和を引く方法がある: 3628801 → (3+2+8+1)−(6+8+0) = 14−14 = 0 は 11 の倍数なので、3628801 も 11 の倍数。

*3　Dirichlet: Vorlesungen (1863), §34。高木 (1931): §12.2。Hardy & Wright (1938): §6.5。Sierpiński (1964): Chap. V, §5。これはオイラーの基準の証明であり、Wilson の定理は、その特別な場合に当たる（cf. Gauß DA art. 76, 77）。

【2】　p を 3 以上の素数として、
　　S = {1, 2, 3, … , p−1}
という p−1 個の数を考える。D を p の倍数以外の定数とするとき、S から一つの数 a を選ぶと、S の中には必ず ax ≡ D (mod p) を満たす数 x がある（合同記号（≡）の説明）。

〔例1〕　p = 7, S = {1, 2, 3, 4, 5, 6} のとき D = 5 とすると:
　　a = 1 なら x = 5　つまり ax = 5 ≡ 5 (mod 7)
　　a = 2 なら x = 6　つまり ax = 12 ≡ 5 (mod 7)
　　a = 3 なら x = 4　つまり ax = 12 ≡ 5 (mod 7)

☆　上の例では、S の 6 要素が過不足なく (1, 5), (2, 6), (3, 4) の3ペアに分かれ、どのペアも積が D ≡ 5 になっている。このようになる理由は単純だが、話がそれるので、ここでは「そういうものだ」ということにしておく。

〔補足〕　掛け算の順序は積に影響しないので、a と x を入れ替えても構わない。例えば a = 1, x = 5 の代わりに a = 5, x = 1 としてもいい。積の順序を入れ替えただけのペアを別々にカウントするなら、S の各要素は、a として1回ずつ、x として1回ずつ、計2回ずつ現れる。ここでは、単純に (1, 5) と (5, 1) は同じカップルと見なし、1回だけカウントする。過不足が起きない理由は「日付を○倍したときの曜日の話」と本質的に同じ。ax ≡ D は1次方程式なので、解があるならちょうど1個の解を持ち、a が複数の x のペアとなることはない。こっそり二股かける「三角関係」のペアは生じない…ってわけ。

☆　ax ≡ D の解 x が、たまたま a に等しくなることはあり得る。

〔例2〕　p = 7, S = {1, 2, 3, 4, 5, 6} のとき D = 4 とすると:
　　a = 1 なら x = 4　つまり ax = 4 ≡ 4 (mod 7)
　　a = 2 なら x = 2　つまり ax = 4 ≡ 4 (mod 7)　　←特例（a = x）
　　a = 3 なら x = 6　つまり ax = 18 ≡ 4 (mod 7)
　　a = 5 なら x = 5　つまり ax = 25 ≡ 4 (mod 7)　　←特例（a = x）

この例では S の 6 要素のうち 4 要素が、(1, 4) と (3, 6) の2ペアに分かれ、どちらのペアも積が D ≡ 4 になっている。それとは別に 2 は、いわば自分自身とペアになり 2 × 2 つまり 2² が ≡ D となる。5 についても同様。このように、ax ≡ D で a ≡ x となる場合――言い換えれば x² ≡ D に解がある場合――、それは2次方程式なので、2種類の解を持つ（r が解なら −r ≡ p − r も解）: この場合、S の要素のうちその2種類は特例的になるが、それ以外の要素は、例1同様、過不足なくペアを作る。対照的に、例1は x² ≡ D に解がない場合。

☆　x² ≡ D (mod p) に解があるとき、D は mod p において平方剰余と呼ばれる。x² ≡ D (mod p) に解がないとき、D は mod p において平方非剰余と呼ばれる。文脈から意味が明らかなときは、「mod p において」も「平方」も略して、それぞれ単に剰余・非剰余とも呼ばれる。

「平方剰余」は、通常の整数の世界における「平方数」（1, 4, 9, 16, 25 など）の、mod p バージョン。「非剰余」は「非平方数」に当たる。これらの概念は、古典数論において重要な役割を果たす。

【3】　特例的な要素がない場合（＝D は平方非剰余）、p−1 個ある S の要素たちは2個ずつペアになるのだから、ペアの数は (p−1)/2 個。一つ一つのペアの積はどれも ≡ D だから、もし全部のペアが作る積を掛け合わせると、結果は…
　　D^(p−1)/2 (mod p)　　‥‥『あ』
…となる。例1（p = 7, D = 5）で言えば:
　　(1 × 5) × (2 × 6) × (3 × 4) ≡ 5 × 5 × 5 ≡ 5³　　←これが D^(p−1)/2
　　右端の指数の 3 は (p−1)/2 = (7−1)/2

S の各要素が過不足なくペアを作っているのだから、上記の D^(p−1)/2 は、S = {1, 2, 3, …, p−1} の各要素を掛け合わせたのと同じこと。つまり
　　(p−1)!　　‥‥『い』
例1で言えば、
　　(7−1)! = 1 × 2 × 3 × 4 × 5 × 6
に他ならない。『い』は『あ』と同じ積なので:
　　(p−1)! ≡ D^(p−1)/2 (mod p)　　‥‥『う』

一般に D が平方非剰余の場合、『う』が成り立つ。

【4】　他方、特例的な要素がある場合（＝D は平方剰余）、S の要素たち p−1 個のうち、2個は特別で他とペアを作らず、残りの p−3 個が2個ずつペアになるのだから、ペアの数は (p−3)/2 個。一つ一つのペアの積はどれも ≡ D だから、全部のペアが作る積を掛け合わせると、結果は…
　　D^(p−3)/2 (mod p)
…となる。例2（p = 7, D = 4）で言えば:
　　(1 × 4) × (3 × 6) ≡ 4 × 4 ≡ 4²　　←これが D^(p−3)/2
　　右端の指数の 2 は (p−3)/2 = (7−3)/2

特例の2個は x² ≡ D の解だから ±x の形を持つ。その2個の積は:
　　x(−x) ≡ −x² ≡ −D　　← x² ≡ D だから
例2（p = 7, D = 4）で言えば x ≡ 2 と x ≡ −2 ≡ 5 が特例で:
　　2 × 5 = 10 ≡ −4 (mod 7)

S の全要素の積に当たるものは: 特例の2要素の積 −D と、それ以外の（ペアを作っている）要素たちの積 D^(p−3)/2 を掛け合わせて:
　　−D × D^(p−3)/2 ≡ −D^(p−1)/2
　　↑1個のDと、(p−3)/2個のDの積なので 1+(p−3)/2個のDの積になる: 1+(p−3)/2 = (p−1)/2

これも S の全要素の積なので、『う』と似た関係になる:
　　(p−1)! ≡ −D^(p−1)/2 (mod p)　　‥‥『え』

『う』『え』を見比べると、いずれにしても (p−1)! ≡ ±D^(p−1)/2 の形。ただし符号の部分は、D が平方剰余ならマイナス、非剰余ならプラス。

【5】　さて D = 1 の場合、x² ≡ D ≡ 1 (mod p) には、もちろん解があるので（x ≡ ±1）、1 は平方剰余。『え』のケースになって:
　　(p−1)! ≡ −1^(p−1)/2 ≡ −1 (mod p)　　‥‥『お』
　　↑ 1 は何乗しても 1 だから（p は 3以上）。−1^(p−1)/2 は (−1)^(p−1)/2 ではない。

ところで p = 2 のときも『お』は成り立つ: (p−1)! = 1! = 1 ≡ −1 (mod 2) なので。結局、任意の素数 p について:
　　(p−1)! ≡ −1 (mod p)　　‥‥『か』
　　言い換えれば　(p−1)! + 1 ≡ 0 (mod p)　つまり　(p−1)! + 1 は p で割り切れる

これで Wilson の定理が証明された！

【6】 再び p = 2 を除外し、p を 3 以上の素数とする。p が平方非剰余の場合、『う』の
　　(p−1)! ≡ D^(p−1)/2 (mod p)
…の左辺と右辺を入れ替え、『か』と組み合わせると:
　　D^(p−1)/2 ≡ (p−1)! ≡ −1 (mod p)
同様に、p が平方剰余の場合、『え』と『か』を組み合わせると:
　　−D^(p−1)/2 ≡ (p−1)! ≡ −1 (mod p)
　　両辺を −1 倍すると　D^(p−1)/2 ≡ 1 (mod p)

まとめると:

オイラーの判定基準（Euler’s criterion）　p を 3 以上の素数とする。p の倍数ではない D について:
　　D^(p−1)/2 ≡ ±1 (mod p)　　‥‥『き』
　　右辺の ±1 の符号によって D が平方剰余（プラス）か非剰余（マイナス）か判定される

〔例〕　p = 7 の場合。2^(7−1)/2 = 2³ = 8 ≡ +1 (mod 7) ⇒ 判定結果＝mod 7 において 2 は平方剰余
一方、3^(7−1)/2 = 3³ = 27 ≡ −1 (mod 7) ⇒ 判定結果＝3 は平方非剰余

【7】　フェルマーの小定理の別証明。D が平方剰余か非剰余かにかかわらず、『き』の両辺を平方すると:
　　(D^(p−1)/2)² ≡ (±1)² (mod p)
　　D^p−1 ≡ 1 (mod p)
フェルマーの小定理が（エレガントに？）証明された！

【8】　第一補充法則　p が「4k+1型」の素数なら x² ≡ −1 (mod p) は解を持つ（言い換えると −1 は平方剰余）。p が「4k+3型」の素数なら x² ≡ −1 (mod p) は解を持たない（言い換えると −1 は平方非剰余）。

〔意味〕　素数 p が「4k+1型」か「4k+3型」かに応じて、「mod p において −1 は平方剰余か非剰余か？」が決まる。

証明　オイラーの基準で D = (−1) とすると…。p = 4k+1 なら、『き』左辺の指数 (p−1)/2 = (4k+1−1)/2 = 2k は偶数なので、左辺は (−1) の偶数乗で ≡ +1。従って、平方剰余。一方、p = 4k+3 なら、『き』の左辺の指数 (p−1)/2 = (4k+3−1)/2 = 2k+1 は奇数なので、左辺は (−1) の奇数乗で ≡ −1。従って、平方非剰余。□

〔例題〕　① x² ≡ −1 (mod 13) に解があるか？　13 は4k+1型なのでYes。② x² ≡ −1 (mod 17) に解があるか？　17 も4k+1型なのでYes。③ x² ≡ −1 (mod 19) に解があるか？　19 は4k+3型なのでNo。具体的な解は、①が ±5 ≡ 5 or 8（平方すると ≡ −1 ≡ 12 になる。つまり 25 or 64 を 13 で割ると 12 余る）、②が ±4 ≡ 4 or 13（平方すると ≡ −1 ≡ 16 になる。つまり 16 or 169 を 17 で割ると 16 余る）。

第二補充法則へ続く。

付記: 「伴侶」は、もともと D = 1 の場合に、互いに逆数のペア a, a⁻¹ についてオイラーが使った概念らしい（sŏcĭī、単数形 socius）。一般の D についての a の伴侶は a⁻¹D。

2022-07-23　第二補充法則の簡単な証明・夏秋　教科書の方法より10倍簡単（当社比ｗ）

☆　第二補充法則の内容は難しくないが（後述）、普通の証明法では細かい「符号数え」が行われ、結構面倒くさい。高木も Hardy & Wright も Sierpiński も同じ面倒な方法を使っている。

☆　このメモでは、もっと簡単で分かりやすい直接証明を紹介する（ガウスの補題も、オイラーの基準も、フェルマーの小定理も不要）。その代わり今回は、法則の内容も半分だけ。遊びの数論はのんびりと…

☆　元ネタは Dirichlet。上記の日本語・英語の教科書には載ってない全然別ルートの証明法。実に明快で、目からうろこ。ドイツの数論、代数学は世界一ィィィ！

Dirichlet, Vorlesungen, §41 (cf. DA 112)

この前編は「読み切り」。第一補充法則を知ってても知らなくても、理解可能。一方、「平方剰余の相互法則」の証明を理解したいだけなら、第二補充法則（前編・中編・後編）は全く必要ない。

【1】　3 以上の素数は、8で割った余りによって、8k+1型、8k+3型、8k+5型、8k+7型の四つに分けられる。それぞれ春素数・夏素数・秋素数・冬素数と呼ぶことにしよう。

春素数（8k+1型）　8の倍数より1大きい

17, 41, 73, 89, 97 など

夏素数（8k+3型）　8の倍数より3大きい

3, 11, 19, 43, 59, 67, 83 など

秋素数（8k+5型）　8の倍数より5大きい　（別名8k−3型＝8の倍数より3小さい）

5, 13, 29, 37, 53, 61 など

冬素数（8k+7型）　8の倍数より7大きい　（別名8k−1型＝8の倍数より1小さい）

7, 23, 31, 47, 71, 79 など

「外側2レーン」の春・冬素数は 8 の倍数と 1 違い。「内側2レーン」の夏・秋素数は、8 の倍数と 1 違いではない（3 違い）。

別の角度から言うと、「バニラ素数」（4k+1型）が春素数・秋素数に分類され、「チョコレート素数」（4k+3型）が夏素数・冬素数に分類される。

ここまでは大したことじゃないが、本題の法則とは…

第二補充法則（半分）　p が夏素数か秋素数のとき、x² ≡ 2 (mod p) を満たす x はない。言い換えると、8k±3型素数を法として 2 は平方非剰余。

…な、何を言ってるんだ？

〔解説〕　p が春素数か冬素数なら x² ≡ 2 (mod p) は解を持つ。例えば p = 17 のとき:
　　6² = 36 ≡ 2 (mod 17)　なので　x = 6 は一つの解。
また例えば p = 23 のとき:
　　5² = 25 ≡ 2 (mod 23)　なので　x = 5 は一つの解。
ここで ≡ 2 (mod □) という記号については「余りは 2 だよ、□で割ると！」と解釈しておこう（もっと正確な説明）。
一方、p が夏素数か秋素数のとき、x² ≡ 2 (mod p) は解を持たない。例えば p = 11 のとき、どんな整数を2乗しても ≡ 2 (mod 11) にはならない。総当たりで、試してみよう。mod 11 の世界のメンバーは、
　　x ≡ 0, 1, 2, 3, 4, 5, 6 (≡−5), 7 (≡−4), 8 (≡−3), 9 (≡−2), 10 (≡−1)
…の11種類。そこで 0, ±1, ±2, ±3, ±4, ±5 を2乗すると、それぞれ 0, 1, 4, 9, 16 ≡ 5, 25 ≡ 3 で、2 は出てこない。

個々の p については、解があるかないか、総当たりで試せば判定できるけど、素数は無限にあるので、一つ一つ試していては、きりがない。一般論として上記の法則を証明したいところだが…。

教科書通りの正攻法で第二補充法則を証明しようとすると、かなり長い論理の連鎖が必要。数論らしい繊細さ・醍醐味（だいごみ）がある半面、ちょっと神経質でピリピリした感じがするのも確か…。以下のショートカットは、単純明快で気持ちがいい。

【2】　x² ≡ 2 (mod p) が解を持つような、夏または秋素数（つまり8k±3型の素数）p が存在する…と仮定する（当然 p は奇数）。もちろん「事実の反対をあえて主張し、矛盾を発生させてやる」という魂胆である。兵は詭道（きどう）なり！

x が x² ≡ 2 (mod p) の解なら、当然 −x ≡ p − x も同じ2次式の解。x が奇数だったら、それをそのまま使い、x が偶数だったら他方の解 p − x をあらためて x と置くと（新しい x は「奇数ひく偶数」で奇数）、どちらの場合も奇数の解 x が選択される。

仮定から:
　　x² ≡ 2 (mod p)　ここで p は夏 or 秋素数　　‥‥『さ』
　　移項して　x² − 2 ≡ 0 (mod p)
つまり x² − 2 は p で割り切れる。商を Q とすると:
　　x² − 2 = pQ　　‥‥『し』

x は奇数なので、x = 2n + 1 とでも置くと:
　　x² = (2n + 1)² = 4n² + 4n + 1 = 4n(n + 1) + 1　　‥‥『す』
n と (n + 1) の一方は奇数・他方は偶数なので、それらの積 n(n + 1) は偶数。従って、
　　4n(n + 1)
…は偶数の4倍、つまり 8 の倍数。だから『す』は 8 の倍数より 1 大きい。言い換えると:
　　x² ≡ 1 (mod 8)　　‥‥『せ』

奇数の2乗を 8 で割ると 1 余る。1² = 1, 3² = 9, 5² = 25, 7² = 49…おおぉホントだっ！

【3】　『し』の両辺は等しいのだから、その左辺を 8 で割った余りと、右辺を 8 で割った余りは、当然、等しい:
　　x² − 2 ≡ pQ (mod 8)
この左辺に『せ』を代入する。右辺については、p は夏または秋素数なので p ≡ ±3 (mod 8) となって:
　　1 − 2 ≡ (±3)Q (mod 8)
左辺と右辺を入れ替えると:
　　±3Q ≡ −1 (mod 8)　　‥‥『そ』

『そ』は、8 の倍数より 1 小さい数なので、奇数。従って Q も奇数（もし偶数なら、『そ』左辺が偶数になってしまい、つじつまが合わない）。だから Q は（素数であるとすれば）奇素数、さもなければ（合成数だとすれば）2個以上の奇素数の積に等しい。のみならず、もしも Q ≡ 1 or −1 (mod 8) なら、明らかに『そ』は成り立たない。『そ』の左端の符号に対応して Q ≡ ∓3 (mod 8) でなければならない（そのとき『そ』左辺は (±3)(∓3) ≡ −9 ≡ −1 となり（複号同順）、ちゃんと右辺と合同になる）。

ところが、もしも Q の素因数が全部 ≡ 1 or −1 (mod 8) の形（春・冬素数）だとすると、1 or −1 の積は再び ≡ 1 or −1 (mod 8) なので、Q ≡ ∓3 (mod 8) という条件に反する。

従って、Q の素因数の中には、≡ 3 or −3 (mod 8) のもの（夏・秋素数）が少なくとも1個、含まれている。そのような数―― Q の素因数の中に必ず1個はある夏 or 秋素数――を一つ選んで q として（q は Q の約数なので Q 以下）、Q = qr とでも書いておこう^*1。『し』に代入すると:
　　x² − 2 = pQ = pqr
従って x² − 2 は q で割り切れる（商は pr）。言い換えると:
　　x² − 2 ≡ 0 (mod q)　移項すると
　　x² ≡ 2 (mod q)　ここで q は Q 以下の夏 or 秋素数　　‥‥『た』

『さ』の場合と同様、『た』でも奇数の解 x を選択できる。

以下で説明するように、この『さ』と『た』から矛盾が生じる。

*1　ここで r = Q/q は、もし q = Q 自身が素数なら 1、さもなければ Q に含まれる残りの（q 以外の）素因数の積だが、r の値はどーでもいい。

【4】　まず『し』の x² − 2 = pQ だが、この Q って数、どのくらいの大きさ？　x = 1 とかだと『さ』は 1 ≡ 2 というばかげた式になってしまうので、『さ』を満たす奇数 x があるとするなら、その絶対値は 3 以上。従って『し』の左辺は正、右辺も正で Q も正。一方、mod p の世界のメンバーは、
　　0, 1, 2, 3, … p − 1
…で全種類なので（p で割った余りによる分類だからネ）、解があるとすれば、その中に解がある。その解を使うと、x² は最大でも (p − 1)² 以下^*2。ってことは、『し』の左辺は p² より小さい。それが『し』の値なんだから、Q は p より小さい正の数（もし Q が p 以上なら、『し』の右辺は p² 以上になっちゃって、つじつまが合わない）。

*2　実際には x² は (p − 2)² 以下: 解 x の値は奇数なので、x = p − 1（それは偶数）は不可能。とはいえ (p − 2)² 以下なら、もちろん (p − 1)² 以下。p² より小さいという結論に変わりない。

『た』の mod になっている夏 or 秋素数 q は、その Q 以下なんで、当然 p より小さい。

『さ』において、条件を満たす最小の p を選んだとすると、この時点でもう矛盾している（最小を選んだのに、もっと小さい素数が条件を満たしちゃうので）。

大きさを気にせず『さ』の p を適当に選んだとしても、要するに:
　　mod p で 2 が平方剰余になるような夏 or 秋素数 p が存在するなら…
　　　　「mod q でも 2 は平方剰余だぜ！」　　←『た』参照
　　　　「この q は p より小さいんだぜ！」
…という性質を持つ夏 or 秋素数 q が、存在する。「存在するなら、もっと小さい例も存在する」ってことは…
　　「2 が平方剰余」となるような夏 or 秋素数 p が存在
　　⇒ もっと小さい夏 or 秋素数が存在して同じ性質を持つ
　　⇒ もっともっと小さい夏 or 秋素数が存在して同じ性質を持つ
　　⇒ もっともっともっと小さい…
という無限降下が生じる。現実的に、『さ』を満たす素数 p を選ぶことができたとして、その p より小さい自然数は有限個しかないんだから、そんな無限降下は不可能！

『さ』の条件を満たす p を選ぶことは、現実には不可能だったのである。すなわち、夏または秋素数を法として 2 が平方剰余になることはない。これが証明したいことだった。□

【5】　上記で証明されたこと:

• 「8k±3型」の素数 p を法とすると、2 は平方非剰余。
• 奇数の素数 p を法として 2 が平方剰余になるなら、p は「8k±1型」。

第二補充法則（完全版）では、逆も成り立つ（今回は未証明）:

• 素数 p を法として 2 が平方非剰余なら p は「8k±3型」。
• 「8k±1型」の素数 p を法とすると、2 は平方剰余。

要するに、3 以上の素数 p について:
　　x² ≡ 2 (mod p) に解あり ⇔ p ≡ ±1 (mod 8)　春・冬
　　x² ≡ 2 (mod p) に解なし ⇔ p ≡ ±3 (mod 8)　夏・秋

【6】　で、それが何の役に立つの？　今回の成果の活用例として、8k+7型の素数（冬素数）が無限に存在することを証明する。春素数・秋素数の無限は証明済みなので、冬素数も「無限コレクション」に加えたい…

最初の8個の冬素数（8の倍数より1小さい素数）: 7, 23, 31, 47, 71, 79, 103, 127。果たしてこの系列は、無限に続くのか。仮に無限に続くとして、どうやってその無限性を証明できるのか。ワクワクするでしょ？ｗ

補助命題1　x² − 2 が奇数の素数 p で割り切れるなら、その p は春素数または冬素数。

証明　x² − 2 が奇数の素数 p で割り切れる場合、もし p が夏または秋素数だとすると、矛盾が生じる（上記『さ』『し』以下）。従って、そのような p があるとすれば、春または冬素数。□

補助命題2　8k+1型の素数（春素数）同士を2個以上掛け合わせた積は、8k+1型の奇数。

証明　a, b をどちらも8k+1型の素数とすると、a ≡ 1, b ≡ 1 (mod 8)。このとき積 ab ≡ 1⋅1 ≡ 1 (mod 8) は「8k+1型」の奇数。8k+1型の素数3個以上の積も同様。□

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

証明　8k+7型素数（冬素数）が S = {p₁, p₂, …, p_m} の m 個しか存在しないと仮定し、ユークリッドの手筋に従って、それらの積を
　　A = p₁p₂…p_m
とする。7 は8k+7型素数なので S は空集合ではない。A は奇数。

p₁, p₂ などはそれぞれ ≡ 7 (mod 8) つまり ≡ −1 (mod 8) なので、それらの積 A は、m が偶数か奇数かに応じて A ≡ ±1 (mod 8)。だから A² ≡ 1 (mod 8) であり、従って A² − 2 ≡ −1 (mod 8) は8k−1型の奇数。

①もし A² − 2 が素数なら、それは明らかに S のどの素数よりも大きい: S に含まれない冬素数。

②もし A² − 2 が合成数なら、その素因数は、春または冬素数に限られる（補助命題1）。もしも因数が全部春素数なら、補助命題2から積は「8k+1型」の奇数: 実際には A² − 2 は「8k−1型」なので、出てくる素因数は「春素数だけ」ではない――けれど「春素数または冬素数に限られている」。つまり、8A² − 1 の素因数には、冬素数が少なくとも1個、含まれる: その冬素数を q とする。今、S に含まれるどの素数 p を考えても、A は p の倍数なので、A² も p の倍数。p の倍数より 2 小さい A² − 2 は、p では（つまり S に含まれるどの素数でも）割り切れない。だから A² − 2 の約数である素数 q は、S に含まれない冬素数。

①でも②でも、S に含まれない冬素数が見つかる: 「冬素数は有限」という最初の仮定は不合理。□

〔例1〕　冬素数が {7, 23} だけと仮定。A = 7 × 23 = 161。これは8k+1型の奇数。
A² − 2 = 25919。これは8k−1型の奇数。この場合、この数は「新しい」冬素数。

〔例2〕　冬素数が {7, 23, 31, 47} だけと仮定。A = 234577。これは8k+1型の奇数。
8k−1型の奇数 A² − 2 = 55026368927 は 17 × 3236845231 と素因数分解される。
17 は春素数だが、3236845231 は冬素数。

この方法では A² − 2 の因数として奇数個の「新しい冬素数」が出てくる。

〔参考〕　Thomas Koshy: Elementary Number Theory with Applications (2007), Chap. 11, Review Exercises, 54 では上記の方法で定理3（冬素数の無限）が証明されている。一方、Kenneth Ireland & Michael Rosen (1982): A Classical Introduction to Modern Number Theory, Chapter 5, §1 では、A² − 2 の代わりに (4A)² − 2 = 2(8A² − 1) が使われている。後者の方法の長所として、8A² − 1 の部分が8k−1型であることが一目瞭然であり、さらに S が空集合でも構わない。（2022年10月10日）

2022-07-27　第二補充法則の簡単な証明・冬

「夏素数の無限」（【10】まで）は前回の続き、読み切り。第二補充の証明を終わらせないまま、春・夏・秋・冬素数の無限性を全部証明するのは、意外と史上初の最短「証明ゴルフ」かも…！？

【7】　今回も元ネタは Dirichlet（Vorlesungen §41 の続き: Gauß DA art. 113）。

問題　p が秋素数か冬素数のとき、x² ≡ −2 (mod p) を満たす x はない。言い換えると、8k+5型・8k+7型素数を法として −2 は平方非剰余。これを直接（補充法則・相互法則を使わず）証明したい。

〔例1〕　p が春素数 17 の場合: x² ≡ −2 (mod 17) に解がある。実際 x ≡ 7 とすると、x² ≡ 49 ≡ 15 (mod 17) だが、mod 17 では 17 の倍数の違いは区別されないので、15 ≡ 15 − 17 ≡ −2。つまり 7² ≡ −2 (mod 17)。「49 は 17 の倍数 51 より 2 小さい」と解釈してもいい。

〔例2〕　p が夏素数 11 の場合: x² ≡ −2 (mod 11) に解がある。実際 x ≡ 3 とすると、x² ≡ 9 ≡ −2 (mod 11)。

〔例3〕　一方、p が秋素数 5 の場合: x² ≡ −2 (mod 5) には解がない。x ≡ 0, ±1, ±2 の5種類を試すと、x² はそれぞれ 0, 1, 4 となって、−2 ≡ 3 (mod 5) と合同にならない。

〔例4〕　p が冬素数 7 の場合: x² ≡ −2 (mod 7) には解がない。x ≡ 0, ±1, ±2, ±3 の7種類を試すと、x² はそれぞれ 0, 1, 4, 9 (≡2) となって −2 ≡ 5 と合同にならない。

【8】　証明法は前回とほとんど同じ。復習も兼ねて…

x² ≡ −2 (mod p) が解を持つような、秋または冬素数 p が存在する…と仮定する（当然 p は奇数）。上の例3・例4から p = 5, p = 7 は条件を満たさない。条件を満たす p があるとすれば、もっと大きい。どのくらい大きいかは分からないが、もしそういう p があるなら、その中で最小のものがあるはず。そこで、p を…
　　x² ≡ −2　つまり
　　x² + 2 ≡ 0 (mod p)　ここで p は秋 or 冬素数　　‥‥『な』
…が解を持つような、最小の秋 or 冬素数としよう。0, 1, 2, 3, …, p−1 の中に解 x がある。そのうち r が解なら、−r ≡ p − r も解。なぜなら r² ≡ −2 が成り立つなら、当然 (−r)² = r² ≡ −2 も成り立つ…。前回同様、解 x があるとするなら、p より小さい正の奇数…と仮定できる（もし解 x が偶数だったら、もう一つの解 p − x を再選択して、それをあらためて x と置けば、それは奇数。x = 0 は『な』を満たさない）。

『な』によれば、x² + 2 は p で割り切れる。その商を Q とすると:
　　x² + 2 = pQ　　‥‥『に』

Q が p 以上になること（つまり『に』の右辺が p² 以上になること）が、あり得るだろうか？　もしあり得たとすると、そのときには、右辺に等しい『に』の左辺も p² 以上。けど『に』の左辺は、最大でも
　　(p − 1)² + 2 = p² − 2p + 3　　← x = p−1 の場合
…なので、それが p² 以上っつーことは:
　　p² ≤ p² − 2p + 3　両辺から p² を引くと
　　0 ≤ −2p + 3　移項して　2p ≤ 3
　　つまり　p ≤ 1.5

p は素数なので 1.5 以下ということは、あり得ない！　従って Q が p 以上になることはなく、Q は p より小さい。

【9】　『に』の左辺は、正の奇数（なぜなら奇数の平方プラス2 = 正の奇数プラス2 = 正の奇数）、右辺の p も正の奇数だから、Q も正の奇数。前回見たように（『す』『せ』）、奇数 x の平方は x² ≡ 1 (mod 8) を満たす。その両辺に 2 を足すと:
　　x² + 2 ≡ 3 (mod 8)
この左辺は『に』によって pQ と等しいので:
　　pQ ≡ 3 (mod 8)　　‥‥『ぬ』

仮定により p は秋 or 冬素数、つまり p ≡ 5 or 7 (mod 8)。このことと『ぬ』を両立させるためには、Q に厳しい条件が付く。奇数 Q は ≡ 1, 3, 5, or 7 (mod 8) のどれかだが、p ≡ 5 の場合、対応する pQ の値は、それぞれ:
　　5⋅1 ≡ 5, 5⋅3 ≡ 15 ≡ 7, 5⋅5 ≡ 25 ≡ 1, 5⋅7 ≡ 35 ≡ 3 (mod 8)
つまり Q ≡ 7 の場合だけ『ぬ』が成立。同様に、p ≡ 7 の場合、pQ の値は:
　　7⋅1 ≡ 7, 7⋅3 ≡ 21 ≡ 5, 7⋅5 ≡ 35 ≡ 3, 7⋅7 ≡ 49 ≡ 1 (mod 8)
つまり Q ≡ 5 の場合だけ『ぬ』が成立。

まとめると、『ぬ』が成り立つためには、少なくとも次の条件が必要:
　　Q ≡ 5 or 7 (mod 8)　　‥‥『ね』

さて、Q はそれ自身、奇数の素数であるか（1個の素因数）、または2個以上の素因数の積から成るが、もしも Q を構成する全部の素因数が春素数つまり ≡ 1 (mod 8) なら、それらの積は ≡ 1 (mod 8) なので『ね』の条件が満たされない。春素数に加えて夏素数（つまり ≡ 3 (mod 8) の形の素因数）が1個以上含まれているとしても、それらの積として新たに生じる可能性は ≡ 3 自身だけ。もっと掛け合わせてみても、
　　3 × 3 ≡ 9 ≡ 1 (mod 8), 3 × 3 × 3 ≡ 27 ≡ 3 (mod 8), …
のように、それ以外のものは作れず、依然『ね』の条件を満たせない。従って、『ね』が成り立つからには、Q の素因数の中に秋 or 冬素数（つまり ≡ 5 or 7 (mod 8) の素数）が少なくとも1個含まれている必要がある。この（少なくとも1個ある）秋 or 冬の素因数を q とすると、それは Q の因数なので、Q は q で割り切れる。Q/q = r つまり Q = qr とでも置いて、それを『に』に代入すると:
　　x² + 2 = pqr
この右辺は q で割り切れるので、それに等しい左辺も、もちろん q で割り切れる。言い換えると:
　　x² + 2 ≡ 0 (mod q)　ここで q は秋 or 冬素数　　‥‥『の』

『の』は『な』の仮定と矛盾している！　というのも、q は Q の約数なので Q 以下だが、その Q は p より小さいのだから、当然 q は p より小さい。けれど『な』では、この式を成り立たせるような最小の秋 or 冬素数を p として選んだはず。最小のはずの p よりもっと小さい秋 or 冬素数 q が、『な』と同じ形の『の』を成り立たせてしまうのでは、つじつまが合わない。

『な』が成り立つ例が1個でもある…と仮定すると矛盾が起きるのだから、『な』を満たす p は実は1個もない…と結論するしかない。そしてそれが、証明したいことだった。□

【10】　『な』は否定されたが、肯定的に見ると、次の事実が判明した。

補助命題3　x² + 2 の「奇数の素因数」は、春または夏素数に限られる。

証明　もしも x² + 2 が秋 or 冬素数の因数 p を持つなら『な』の形が成り立つが、それが無理な仮定であることは、証明済み。秋・冬が駄目なので、可能性があるとしたら春・夏。□

この補助命題によって、ついに「8k+○型素数の無限」シリーズが感動の完結（？）を迎える。すなわち…

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

証明　8k+3型素数（夏素数）が S = {p₁, p₂, …, p_m} の m 個しか存在しないと仮定し、ユークリッドの手筋に従って、それらの積を
　　A = p₁p₂…p_m
とする。A は奇数の積なので奇数。

A² + 2 は（奇数プラス2なので）奇数。補助命題3から、その素因数は春・夏素数に限られる。

A² = (p₁p₂…p_m)² = p₁²p₂²…p_m² は、「夏素数の平方」を掛け合わせたもの。夏素数は ≡ 3 (mod 8) なので、夏素数の平方は ≡ 9 ≡ 1 (mod 8) であり、それらの積はもちろん ≡ 1 (mod 8)。つまり:
　　A² ≡ 1 (mod 8)
両辺に 2 を足すと:
　　A² + 2 ≡ 3 (mod 8)

A² + 2 の素因数は、春・夏限定だった。もしも A² + 2 の素因数が全部春（つまり ≡ 1 (mod 8) の素数）だとしたら、それらの積も ≡ 1 (mod 8) となり（前回の補助命題2）、上記の事実 A² + 2 ≡ 3 (mod 8) に反する。だから A² + 2 の素因数の中には、少なくとも1個の夏素数 q が含まれている。

ところで S に含まれるどの素数 p から見ても、A は p の倍数なので、A² も p の倍数。従って、それに 2 を足した A² + 2 を p で割ると、2 余ってしまい、割り切れない。つまり集合 S のどの要素も A² + 2 を割り切ることができない。従って A² + 2 を割り切る q は、S の要素のどれとも違う「新しい」夏素数。夏素数が有限個しかないという最初の仮定は不合理。□

〔例1〕　夏素数は {3, 11} だけと仮定。A = 3 × 11 = 33 となる。A² + 2 = 1091 は新しい夏素数。

〔例2〕　夏素数は {3, 11, 19} だけと仮定。A = 3 × 11 = 627 となり、A² + 2 = 393131 = 131 × 3001。このうち 131 は新しい夏素数、3001 は春素数。

この方法では、A² + 2 の素因数として、新しい夏素数が奇数個、出てくる。

素数が無限にあることは、2000年以上前のユークリッドの時代から知られていた。それだけでなく、奇数の素数を 8 で割った余りによって春・夏・秋・冬の4グループに分けた場合にも、春素数・夏素数・秋素数・冬素数は、それぞれどれも無限個存在する。これは重大な事実といえよう！

【11】　前回は第二補充法則が「半分」だけだった。Gauß / Dirichlet 流では、第二補充法則を三つに分けて導入する。回りくどいようだが、含蓄があって、分かりやすい。まずオイラーの基準『き』を思い出そう。

p を 3 以上の素数とする。p の倍数ではない D について:
　　D^(p−1)/2 ≡ ±1 (mod p)
　　右辺の ±1 の符号によって D が平方剰余（プラス）か非剰余（マイナス）か判定される

p の倍数ではない2個の整数 a, b が与えられたとき、mod p において a は平方剰余か非剰余か？　b は平方剰余か非剰余か？　それぞれオイラーの基準から判定可能。例えば、
　　a^(p−1)/2 ≡ +1 (mod p)　⇒ 判定結果　a は平方剰余
　　b^(p−1)/2 ≡ −1 (mod p)　⇒ 判定結果　b は非剰余
となったとしよう。このとき、積 ab は果たして平方剰余だろうか、非剰余だろうか？

再びオイラーの基準によれば、
　　(ab)^(p−1)/2
を計算すればいいわけだが、次のように考えれば、カンタンだよ:
　　(ab)^(p−1)/2 = (a)^(p−1)/2 × (b)^(p−1)/2 ≡ (+1)(−1) = −1
だって a^(p−1)/2 が ≡ +1 ってことも、b^(p−1)/2 が ≡ −1 ってことも、既に分かってるんだもん…。

えーなーに、どーゆーこと？　ウンだからさぁ、例えば p = 13 とするじゃん（つまり mod 13）？　でもって、まぁ例えば a = 3 をオイラーの基準で判定すると、次のようになって、判定結果は平方剰余:
　　3^(13−1)/2 = 3⁶ = 729 ≡ +1 (mod 13)　　‥‥『は』
　　　13 × 56 = 13 × 50 + 13 × 6 = 650 + 78 = 728 なので
　　　728 は 13 の倍数。729 は 13 の倍数より 1 大きい。
一方 b = 2 は平方非剰余:
　　2^(13−1)/2 = 2⁶ = 64 ≡ −1 (mod 13)　　‥‥『ひ』
　　　64 は 13 の倍数（65）より 1 小さい。
このとき ab = 6 が平方剰余かどうか判定するのに、普通に…
　　6^(13−1)/2 = 6⁶ = 46656 ≡ −1 (mod 13)
…を計算してもいーんだけど、もっと単純に
　　6^(13−1)/2 = 6⁶ = 3⁶ × 2⁶ ≡ (+1)(−1) = −1
ってできるってこと。説明↓

☆　最後の式の2個目の等号の意味は:
　　6⁶ = (3⋅2)⁶
　　= (3⋅2)(3⋅2)(3⋅2)(3⋅2)(3⋅2)(3⋅2)　　← 6個掛け合わせる
　　= 3⋅3⋅3⋅3⋅3⋅3 × 2⋅2⋅2⋅2⋅2⋅2　　←交換法則。それぞれ6個
　　= 3⁶ × 2⁶

☆　それが ≡ (+1)(−1) になるのは、『は』と『ひ』で計算済みの 3⁶ ≡ +1 と 2⁶ ≡ −1 を再利用しただけ。

ポイントは「計算で楽ができる」というせこい話じゃなく、平方剰余・非剰余の判定を「分解して行える」ってこと。この考え方を整理すると:

第一に、a, b が両方とも平方剰余なら ab の判定結果は (+1)(+1) = +1 となり、ab も平方剰余。

x² ≡ a を満たす x と、y² ≡ b を満たす y があるなら、当然 xy は (xy)² = x²y² ≡ ab を満たすので、平方剰余と平方剰余の積が再び平方剰余になるのは、驚くには当たらない。整数の世界で言えば、平方数 4 = 2² と平方数 9 = 3² の積 36 = (2⋅3)² が再び平方数になることとパラレル。

第二に、a, b の片方だけが平方剰余、もう片方が非剰余なら、ab の判定結果は (+1)(−1) あるいは (−1)(+1) になり、いずれにしても −1 となって、ab は平方非剰余。

整数の世界で言えば、平方数 4 と非平方数 7 の積 28 が非平方数になることとパラレルで、感覚的には、まぁ当たり前のような…。

第三に、a, b が両方とも平方非剰余なら、ab の判定結果は (−1)(−1) = +1 となり、ab は平方剰余。

この点は、普通の整数の世界とは感覚が異なる。普通の整数で、例えば、非平方数 2 と非平方数 5 の積 10 は、平方数にはならない！　「非平方数 2 と 非平方数 18 の積が平方数 36」のような例もあるにはあるが、一般にはそうならない（普通の整数の世界では）。一方、素数を mod とする剰余の世界では、平方非剰余と平方非剰余の積が、必ず平方剰余。

第三の場合は、ちょっと意外な気も…。本当にそうなるのか、具体例として再び mod 13 で c = 5 を判定してみる:
　　5^(13−1)/2 = 5⁶ = 15625 ≡ −1 (mod 13)　　‥‥『ふ』
　　　13 × 12 = 13 × 10 + 13 × 2 = 130 + 26 = 156 なので
　　　13 × 1200 = 15600, 13 × 2 = 26,
　　　13 × 1202 = 15626。だから 15625 は 13 の倍数より 1 小さい。
つまり非剰余。『ひ』によれば b = 2 も非剰余だった。このとき、オイラーの基準の応用（上記第三の場合）によると、bc = 10 の判定結果は (−1)(−1) = +1 で、つまり 10 は平方剰余。言い換えると x² ≡ 10 (mod 13) に解があると判定される。果たして x = 6 とすれば 6² = 36 ≡ 10 (mod 13) となり x = 6 は一つの解。なるほど確かにそーなってるぞ…

【12】　以上の観察を踏まえ、今回は4分の1歩、微速前進…。

素早く第一補充法則の復習を: −1 という数は、4k+1型素数（バニラ素数）を法とすると平方剰余、4k+3型素数（チョコレート素数）を法とすると平方非剰余。

−1 はバニラだとOK（チョコだと駄目）。温度がマイナス1だから冷たいよ？

さて 5, 13, 29 のような8k+5型素数（秋素数）は、4k+1型素数の特別な場合^†。第一補充法則によると、そのような素数 p を法とすると −1 は平方剰余。他方、【7】の問題によると、8k+5型素数 p を法として、−2 は平方非剰余。【11】の議論で a = −1, b = −2 と置くと、ab = 2 の判定結果は (+1)(−1) = −1。すなわち、8k+5型素数を法とすると、2 は平方非剰余。

このことは、前回の「第二補充法則（半分）」で既に証明済みだが、その正しさが再確認された！

†　8k+5 = 4⋅2k+4+1 = 4(2k+1)+1 《2k+1 を K とすると》 = 4K+1

次に 7, 23, 31 のような8k+7型素数（冬素数）は、4k+3型素数の特別な場合^‡。第一補充法則によると、そのような素数 p を法とすると −1 は平方非剰余。他方、【7】の問題によると、8k+7型素数 p を法として、−2 は平方非剰余。【11】の議論で a = −1, b = −2 と置くと、ab = 2 の判定結果は、この場合 (−1)(−1) = +1。すなわち、8k+7型素数を法とすると、2 は平方剰余。

これが今回の新たな収穫！

‡　8k+7 = 4⋅2k+4+3 = 4(2k+1)+3 《2k+1 を K とすると》 = 4K+3

前回の成果と合併すると:

第二補充法則（75%完成バージョン）　8k+7型素数（冬素数）を法として 2 は平方剰余。一方（前回証明したように）、8k+3型素数・8k+5型素数を法として 2 は平方非剰余。

「春（8k+1型素数）はどーした、進行がのろいぞ！」というご批判もおありでしょうが、この悠々としたところが Gauß / Dirichlet 流。【10】だけオリジナル、あとは Dirichlet の受け売り。Dirichlet とのコラボで【10】の証明がやけにきれいにできて、何かきれい過ぎて逆に不安…。たぶん合ってるっぽいけど、間違ってたらごめんネ。

2022-07-29　第二補充法則の簡単な証明・春

前編、中編の続き。

【13】　x² ≡ 2 (mod p) は解を持つか？　p が夏・秋・冬素数の場合については、結論が出た: p が冬ならYes、夏・秋ならNo。残された問題は p が春素数、つまり8k+1型の場合だが…

素朴に考えると「平方剰余・非剰余は公平に半々じゃない？　夏・秋が駄目で、冬がOKなら、たぶん春もOKでは」。実際に mod 17 で試してみると:
　　1² = 1, 2² = 4, 3² = 9, 4² = 16 ≡ −1, 5² = 25 ≡ 8,
　　6² = 36 ≡ 2, 7² = 49 ≡ 15 ≡ −2
…となり 2 も −2 も平方剰余。上記の予想通りだが、こうなると「mod p で 2 なり −2 なりが平方剰余になるような春素数が存在すると仮定して、矛盾を導く」といった前編・中編同様のアプローチは、通用しない（その仮定は事実なので、矛盾は生じない）。

このケースについて、Gauß のDA第114節では、原始根を用いた証明が与えられている。Dirichlet はそれをアレンジして、原始根の概念を使わずに同じことを証明した。Dirichlet のこの証明法は、それ自体としては面白いのだが、入り口の部分が少し分かりにくい。以下では、まず Dirichlet 自身の議論を紹介し、次にそれを整理し直した改善版を紹介する。

【14】（ディリクレ版）　代数学によると x^k − y^k は x − y で割り切れる。特に y = 1 とすると、x^k − 1 は x − 1 で割り切れる。具体的には:
　　x^k − 1 = (x − 1)(x^k−1 + x^k−2 + … + x² + x + 1)　　‥‥『ま』

簡易的証明、一般的証明。面倒なら、証明なしにひとまず『ま』を認めてもいい。ここでは『ま』の正確な形は問題ではなく、次の事実だけを使う: x = 1 は f(x) = x^k − 1 の零点なので、f(x) は x − 1 で割り切れ、f(x) = (x − 1) g(x) の形になる（g は x の k−1 次式）。

3 以上の任意の素数 p と、p の倍数以外の任意の自然数 y について、フェルマーの小定理から次が成り立つ:
　　y^p−1 ≡ 1 (mod p)　　‥‥『み』
『み』を y についての p−1 次方程式と見るなら、それは p−1 個の解 y ≡ 1, 2, 3, …, p−1 を持つ。

合同な解は同一と見なし、不合同な解の個数を問題とする。y が p の倍数の場合、つまり y ≡ 0 (mod p) の場合には、『み』の左辺は 0^p−1 ≡ 0 になってしまうので、y ≡ 0 は解ではない。

しばらくの間、素数 p が8k+1型の場合に話を限る。p が 8k+1 なのだから p−1 = 8k となり『み』は:
　　y^8k ≡ 1 (mod p)　移項すると
　　(y⁸)^k − 1 ≡ 0　　‥‥『む』
小定理によって、この『む』が p−1 = 8k 個の解を持つ。
　　x = y⁸　　‥‥『め』
と置くと、『む』は:
　　x^k − 1 ≡ 0
公式『ま』を使って上の左辺を書き換えると:
　　(x − 1)(x^k−1 + x^k−2 + … + x² + x + 1) ≡ 0
『め』によって変数を元に戻すと:
　　(y⁸ − 1)[y^8(k−1) + y^8(k−2) + … + y⁸⁽²⁾ + y⁸ + 1] ≡ 0
これが成り立つのは…
　　y⁸ − 1 ≡ 0　の場合　または
　　y^8(k−1) + y^8(k−2) + … + y⁸⁽²⁾ + y⁸ + 1 ≡ 0　の場合
…であり^*4、可能性として、解の最大個数は、前者が 8 個、後者が 8(k−1) = 8k−8 個、合計 8k 個（○次方程式の解は最大で○個なので）。ところが、解が合計 8k 個あることは既に分かっているのだから、前者も後者も最大限度・目いっぱいの解を持つしかない。同様に考えると:
　　y⁸ − 1 ≡ 0　つまり　(y⁴)² − 1 ≡ (y⁴ + 1)(y⁴ − 1) ≡ 0
に関連して、y⁴ + 1 ≡ 0 も y⁴ − 1 ≡ 0 も、それぞれ4個の解を持つ。

*4　抽象代数的に言うと「整域なので零因子がない」。簡単に言えば、積 AB が ≡ 0 なら A または B が ≡ 0 でしょ、常識で考えて？

y⁴ + 1 ≡ 0 (mod p) が解を持つ…というこの事実が、証明の鍵を握る。しかしながら、この事実は次のようにすれば、もっと簡単に示される。

【14】（改善版）　面倒くさい『ま』は必要ない。フェルマーの小定理から『み』『む』が出るが、便宜上、文字を y から z に変えて、『む』の代わりに z^8k − 1 ≡ 0 (mod p) と書くことにすると:
　　(z^4k)² − 1 ≡ 0　つまり　(z^4k + 1)(z^4k − 1) ≡ 0
が合計 8k 個の解を持つのだから、z^4k + 1 ≡ 0 と z^4k − 1 ≡ 0 は、それぞれ 4k 個ずつの解を持つ。このうち前者に注目すると:
　　z^4k + 1 ≡ 0　つまり　(z^k)⁴ + 1 ≡ 0
が（4k 個の）解を持つのだから、y ≡ z^k と置けば、直ちに「y⁴ + 1 ≡ 0 は解を持つ」と結論される。

〔注意〕　改善版は、z^(p−1)/2 = z^4k ≡ −1 が解を持つことを指摘した上で、その任意の一つの解 z について、単に y ≡ z^k と置いただけ。Dirichlet 版よりずいぶん簡潔だが、「どこからこの発想が出てくるのか」というモチベーションが不透明かもしれない。実は、この y は mod p における −1 の4乗根に当たる。ガウス版と比較すれば、全てを透明に見通せるだろう。

【15】　いずれにしても y⁴ + 1 ≡ 0 (mod p) が解を持つのだから、それと同じ意味の次の式を満たす y が、存在する:
　　(y² + 1)² − 2y² ≡ 0　移項すると
　　(y² + 1)² ≡ 2y² (mod p)　　‥‥『も』

『も』の右辺の 2y² という数は、mod p において平方剰余だろうか？　言い換えると
　　r² ≡ 2y² (mod p)
を満たす r が存在するか？　答えはもちろんYesで、『も』自身が r = y² + 1 という解を与えてくれる。

では y² という数は、mod p において平方剰余だろうか？　言い換えると
　　s² ≡ y² (mod p)
を満たす s が存在するか？　答えはもちろんYesで、単に s = y とすれば、それが解。

オイラーの基準を使って a = 2 が平方剰余かどうか判定した結果を w とすると、w = +1 か w = −1 か、どちらかになるわけだが、前回の【11】の考察から逆に考えると…。上記の通り、事実として b = y² が平方剰余、ab = 2y² も平方剰余だから、a についての判定、b についての判定、ab についての判定の関係は、
　　(w)(+1) = +1
となる。だから w = +1。

別の言い方をすると…。もしも a が非剰余だとすると、「a は非剰余」「b は剰余」「ab は剰余」となってしまい、理屈に合わない（非剰余と剰余の積は非剰余のはず）。一方、a が平方剰余なら、剰余と剰余の積は再び剰余なのだから、「a は剰余」「b は剰余」「ab も剰余」となって、つじつまが合う。

従って、法が8k+1型の素数 p なら 2 は平方剰余、と結論される。

【15】　前編・中編の成果とまとめると:

第二補充法則（完全版）　8k+1型素数・8k+7型素数（春・冬素数）を法として 2 は平方剰余。8k+3型素数・8k+5型素数（夏・秋素数）を法として 2 は平方非剰余。

8k+7型は8k−1型でもあり（7, 23 など）、8k+5型は8k−3型でもある（5, 13 など）。p を 3 以上の素数に限定した上で、「2 が mod p で平方剰余」ということを L(2, p) = 1 と書き、「2 が mod p で平方非剰余」ということを L(2, p) = −1 と書くなら:
　　L(2, p) = 1 ⇔ p = 8k±1　　‥‥『や』
　　L(2, p) = −1 ⇔ p = 8k±3　　‥‥『ゆ』

〔意味〕　r² ≡ 2 (mod p) を満たす r があるか・ないか？　p が 8 の倍数と 1 違うだけ（7, 17, 23 など）なら「ある」、それ以外なら「ない」。

『や』『ゆ』は、しばしば次の謎めいた形式で、一つにまとめて表現される。
　　L(2, p) = (−1)^(p2−1)/8　　‥‥『よ』

この式の右辺は、(−1) を (p²−1)/8 乗しろ…と言っている。例えば p = 5 だとすると、(5²−1)/8 乗しろ ＝ (25−1)/8 乗しろ ＝ 24/8 乗しろ ＝ 要するに「3乗しろ」と。言われた通りにすると、この場合、(−1)³ = −1 となって、8k−3型素数 p = 5 についての『ゆ』の判定 L(2, 5) = −1 と一致。

謎めいた式『よ』がどうやって導出されるかはさておき^*5、「それで合ってる」こと――確認済みの『や』＆『ゆ』と意味が一致すること――を確かめておく。『や』の p = 8k±1 の場合、
　　p² = (8k ± 1)² = 64k² ± 16k + 1　そこから 1 を引くと
　　p² − 1 = 64k² ± 16k = 8[8k² ± 2k] = 8[2(4k² ± k)]
なので、p² − 1 は「8 × 偶数」に当たり、8 で割れば「偶数」になる。要するに、p = 8k±1 なら『よ』は (−1) を偶数乗しろということで、結果は +1、『や』と一致。一方、『ゆ』の p = 8k±3 の場合、
　　p² = (8k ± 3)² = 64k² ± 48k + 9　そこから 1 を引くと
　　p² − 1 = 64k² ± 48k + 8 = 8[8k² ± 6k + 1] = 8[2(4k² ± 3k) + 1]
なので、p² − 1 は「8 × 奇数」に当たり、8 で割れば「奇数」。要するに、p = 8k±3 なら『よ』は (−1) を奇数乗しろということで、結果は −1、『ゆ』と一致。

*5　ガウスの補題（次回以降、取り組む）と関係ある。

【16】　最後に −2 が平方剰余か非剰余かについて。春・夏・秋・冬素数は、順にバニラ・チョコ・バニラ・チョコなので、それぞれ…
　　L(−1, p) = +1, −1, +1, −1　　← −1 はバニラ（春・秋）が平方剰余【第一補充法則】
　　L(2, p) = +1, −1, −1, +1　　← 2 は両端（春・冬）が平方剰余【第二補充法則】
…となり、各ケースについて上と下を掛け算すると、こうなる:
　　L(−2, p) = +1, +1, −1, −1　　← −2 は下2個（秋・冬）が駄目
つまり、春・夏素数を法とすると −2 は平方剰余、秋・冬素数を法とすると −2 は非剰余（この後半については、【7】で問題として直接確かめた）。

春素数を法として −2 が平方剰余。この事実については、別ルートで確かめることもできる: 『も』と同様にして y⁴ + 1 ≡ 0 を (y² − 1)² + 2y² ≡ 0 と書けば (y² − 1)² ≡ −2y² となるから、【15】と全く同じ議論から、法が8k+1型の素数なら −2 も平方剰余と結論される。

【17】　これで第二補充法則が完全に導入された！　教科書の方法と比べて、ホントに10倍簡単だったでしょ（笑）？　理解を深めるため、春素数 p = 17 について、今回の証明が具体的にどういうことなのか確かめてみよう。『み』について y¹⁶ ≡ 1 (mod 17) が16個の解を持つことは、明らかだろう（8乗までの具体的計算）。鍵となる観察は y¹⁶ − 1 が y⁸ − 1 で割り切れることだった:
　　y¹⁶ − 1 = (y⁸ − 1)(y⁸ + 1) = (y⁴ + 1)(y⁴ − 1)(y⁸ + 1) ≡ 0 (mod 17)
…が16個の解を持ち、必然的に y⁴ + 1 ≡ 0 が（4個の）解を持つ。つまり −1 が mod 17 において4個の4乗根を持つ。具体的計算の表と見比べると、その4乗根とは y ≡ 9, 8, 2, 15 つまり y ≡ ±2, ±8。

〔検算〕　(±2)⁴ = 16 ≡ −1 は明白。一方、68 は 17 の倍数（4倍）、従って 64 = 68 − 4 ≡ −4 (mod 17)。これを利用すると、(±8)⁴ = 64² ≡ (−4)² = 16 ≡ −1。

『も』の (y² + 1)² ≡ 2y² が（同じ4個の）解を持つ。ポイントは「解がある」という事実そのもので、解の値は問題ではないが、確認のため一番簡単な y = 2 を実際に選んでみる: 2y² = 8 が平方剰余（y² + 1 = 5 の平方が 8 と合同）、y² = 4 はもちろん平方剰余なので、2 も平方剰余――その心は、オイラーの基準との関係において: (2⋅4)⁸ = 2⁸⋅4⁸ ≡ +1 が分かっていて、しかも 4⁸ ≡ +1 も分かっているときに、2⁸ が ≡ +1 or −1 のどちらかになるという前提で符号を選ぶとすると、必然的に「プラス」が選択され「マイナス」はあり得ない。言い換えると w = +1 or −1 のうち (w)(+1) = (+1) を満たすのは、どっち？　答えは明らかだろう。

別の例として、春素数 p = 41 を考える。x = y⁸ と置いて公式『ま』を使うと:
　　y⁴⁰ − 1 = x⁵ − 1 = (x − 1)(x⁴ + x³ + x² + x + 1)
　　= (y⁸ − 1)(y³² + y²⁴ + y¹⁶ + y⁸ + 1)
　　= (y⁴ + 1)(y⁴ − 1)(y³² + y²⁴ + y¹⁶ + y⁸ + 1) ≡ 0 (mod 41)

小定理によってこの解が40個あるので、y⁴ + 1 ≡ 0 と y⁴ − 1 ≡ 0 がそれぞれ4個の解を持ち、残りの32次式 ≡ 0 が32個の解を持つ。y⁴ + 1 ≡ 0 の一つの解は y = 3。実際、3⁴ = 81 は 41 の倍数 82 より 1 小さい。『も』の (y² + 1)² ≡ 2y² も同じ解を持つ: y = 3 とすると 2y² = 18 が平方剰余、y² = 9 も平方剰余。オイラーの基準に当てはめれば 9²⁰ ≡ +1 そして (2⋅9)²⁰ = 2²⁰⋅9²⁰ ≡ +1 となるはず。従って 2²⁰ ≡ +1 となり、2 も平方剰余と判定される。

「いまいち納得がいかない」「前編・中編の背理法による証明が分かりにくい」「どうでもいいけど長ったらしい」…といったご批判もあるでしょうが、後からガウスの補題経由などでも第二補充法則を証明し（相互法則【10】）、いろいろな角度から考えてみたい（上記の例題では、【14】の改善版ではなくディリクレ版をそのまま使っているので、確かに少しややこしいけれど、これはこれで含蓄がある）。ガウス自身も、このように3つに分けて研究を進めたのである（前編・中編・後編は、それぞれ Gauß DA art. 112, 113, 114 に当たる）。「天才ガウスにもすぐには思い付けなかったトリッキーなショートカット」をいきなり理解させようとする現代の教科書は、不親切を通り越して無謀だろう。

2022-08-03　ガウスの補題　Gauß の第三証明 Dirichlet 版・完全解説 1/3

平方剰余の相互法則の証明（ガウスの第三証明）の簡単化された形は、多くの教科書に載っている: 典型的には、座標平面に斜線を引いて、一定領域に含まれる格子点を数える幾何学的証明。確かに「簡単」だが、「天下り的で、やってることの真意が分からない」というのが本音だろう。このメモでは、しゃらくさいショートカットをせず、Gauß が切り開いた源流を、伝道者 Dirichlet のガイドに従って、ゆっくり歩いてみたい。

200年前の説明は、現代の教科書に比べ10倍くらい遠回りのようにも思える。けれど、現代的な「手っ取り証明」を100回読んでも理解できない真意が、1回で隅々まで理解できるので、実質10倍以上速い。

第三証明は、「予備定理」とも呼ばれる補題の部分と、証明本体の二つに分かれる。今回は補題の部分を…

予備知識として必要なのは、主にオイラーの基準だけ（「ウィルソンの定理から第一補充法則」の【1】～【6】参照）。ウィルソンの定理・フェルマーの小定理・第一補充法則・第二補充法則の知識は、相互法則の証明を理解したいだけなら、必要ない（相互法則の使用例を理解するためには、補充法則が必要）。

【1】　p を奇素数（3以上の素数）、q を p の倍数以外の整数とする。オイラーの基準によれば、q が mod p の平方剰余か非剰余かは、q^(p−1)/2 ≡ ±1 (mod p) の符号によって、判定可能だった。以下では、別の判定法を導入する。

例題　p = 13, q = 10 とする。x² ≡ q (mod p) を満たす解 x は存在するか、つまり
　　x² ≡ 10 (mod 13)
に解があるか？　このYes/Noの判定が、平方剰余・非剰余の判定。

今、1 以上で p/2 = 6.5 未満の整数…
　　《ア》　1, 2, 3, 4, 5, 6
…をそれぞれ q 倍する:
　　《イ》　10, 20, 30, 40, 50, 60
それぞれ p = 13 で割ると、余りは:
　　《ウ》　10, 7, 4, 1, 11, 8

《ウ》の中で p/2 より小さいものをチビ余りと呼ぶことにする:
　　《エ》　4, 1
《ウ》の中で p/2 より大きいものをデカ余りと呼ぶことにする:
　　《オ》　10, 7, 11, 8

実は、デカ余りが偶数個なら q は平方剰余、奇数個なら平方非剰余。上の例で言えば、デカ余りが 4 個（偶数個）あるので、 10 は mod 13 で平方剰余。一般に、デカ余りが合計 n 個あるとして、
　　(−1)ⁿ = ±1
…の右辺の符号がプラスかマイナスかで、平方剰余・非剰余を判定できる。この性質は、ガウスの補題（Gauss’s lemma）と呼ばれる。オイラーの（判定）基準と似てるので、ガウスの（判定）基準と呼んだ方が分かりやすいかもしれない。

例題の一つの解は x ≡ 6。実際 6² ≡ 36 ≡ 10 (mod 13)。これは「36 も 10 も、13 で割った余りは同じ」という意味だった。同じことだが「36 と 10 の差は 13 の倍数」という意味。2乗するのだから符号はどっちでもよく x ≡ −6 ≡ 7 も解: 7² ≡ 49 ≡ 10 (mod 13)。けれど目的は、具体的な解 x を求めることではない: 「解があるかないか」を問題にしている。

【2】　《ア》の数が、どれも互いに不合同なことは明らかだろう――例えば 2 を p で割った余りは 2 自身、3 を p で割った余りは 3 自身で、両者が一致するわけがない。《ア》から相異なるどの2数を選んでも、同じことが言える。

互いに不合同な《ア》をそれぞれ q 倍した《イ》も互いに不合同: これは「今月の1日、2日、3日は曜日が違う」（当たり前）、だから「2日、4日、6日も互いに曜日が違う」「3日、6日、9日も互いに曜日が違う」…というのと、全く同じ理屈。

ここで「q が p の倍数でない」という前提条件が利いている。もしも q が p の倍数なら q, 2q, 3q, … は全部 p の倍数なので、それらを p で割った余りは、どれも 0 であり、不合同ではない。具体例として、曜日（mod 7）において「今月の7日、14日、21日は全部曜日が違う！」という主張は、明らかに間違っている。

さらに、《ウ》は mod p において《イ》と同じ集合なので（順に 10 ≡ 10, 20 ≡ 7, 30 ≡ 4, etc.）、《ウ》の各数も互いに不合同。従って、《エ》と《オ》を合わせた各数も互いに不合同。

デカ余りは、でかくて扱いにくいので、小さくなってもらうことにしよう（ガウスのアイデアの鍵）。小さくする方法は2通りあるが、この二股ではパイオニアに敬意を払い、まずは Gauß / Dirichlet と同じ道を選択する: 一つ一つのデカ余り d を p − d で置き換える。例えばデカ余り 10 を 13 − 10 = 3 で置き換える。《オ》の 10, 7, 11, 8 は、こうなる:
　　《カ》　3, 6, 2, 5

〔注〕　この置き換えは、やぶから棒・独断的で「なぜそう置き換えるのか？」という疑問が生じる。以下で見るように結果的にはこれでうまくいくし、大したことではないけれど、この件については【6】で再検討する。

デカ余り d は p で割った余りのうち p/2 よりでかい数なので、それを p から引けば p/2 より小さくなる: d がでかければでかいほど、それを p から引いた残りは小さくなる。とはいえ、p で割った余りは最大でも d = p−1 なので、p − d は最小でも p − (p−1) = 1。上の例で言えば、p = 13 で割った余り d は 12 以下なので、p − d は 1 以上。さて、注目すべきこととして、チビ余り《エ》の 4, 1 と、デカ余りを置き換えた上記《カ》を合わせると、1 以上 p/2 未満の整数が過不足なく1回ずつ出現している（1, 2, 3, 4, 5, 6）。

これは偶然ではない。この何げない性質こそが、天才ガウスの鋭い観察なのだ！

一般に、チビ余り（合計 m 個あるとする）
　　《キ》　c₁, c₂, c₃, … , c_m
とデカ余り（合計 n 個あるとする）
　　《ク》　d₁, d₂, d₃, … , d_n
を合わせたものについて、どの2個を選んでも不合同であることは、上述の通り。《ク》を小さくした
　　《ケ》　p − d₁, p − d₂, p − d₃, … , p − d_n
についても、mod p では、順に
　　《コ》　−d₁, −d₂, −d₃, … , −d_n
と合同なので（p で割った余りで分類してるんだから、p を足し算しても（商が1増えるだけで）余りつまり分類結果は変わらない）、《ク》の各数が不合同であるからには、《ケ》ないし《コ》の各数も不合同（もしも《コ》の数について −d₂ ≡ −d₃ のような事態が発生するとすれば、両辺を −1 倍して d₂ ≡ d₃ となるが、その可能性は《ク》において否定されている）。

従って（《キ》の内部にも《ケ》の内部にも互いに合同な数はないので）、《キ》と《ケ》にまたがって合同な数がないことを示せば、《キ》《ケ》の各数は全部不合同と結論される。仮に《キ》の数のどれか c と《ケ》の数のどれか p − d が合同になったとしよう（それが無理な仮定であることを確かめる）:
　　c ≡ p − d　移項して　c + d ≡ p
p ≡ 0 (mod p) なので、上の式は要するにこういう意味:
　　《サ》　c + d ≡ 0 (mod p)
ところで c は、1 以上 p/2 未満のどれかの数（u とする）を q 倍して p で割った余りだった:
　　《シ》　c ≡ uq (mod p)
同様に d も、1 以上 p/2 未満のどれかの数（v とする）を q 倍して p で割った余り:
　　《ス》　d ≡ vq (mod p)
でもって《シ》《ス》を《サ》に代入すると:
　　uq + vq ≡ 0　つまり　(u + v)q ≡ 0 (mod p)
これは (u + v)q が p で割り切れるという意味だが、q は p の倍数ではないので p では割り切れない。「秘技」によって u + v が p で割り切れるはず。けれど、実際にはそれは無理―― u も v も 1 以上 p/2 未満なので、u + v が 0 以下になる可能性も p 以上になる可能性もなく、従って u + v が p の倍数にはなる可能性はない。結局《サ》は無理。結論として、《キ》と《ケ》を合わせた数の中に、合同な数が重複して出現することはない。

ちなみに c, d は、それぞれ chibi, deka の意味。格好つけて外国語起源の変数名ばかり使わず、分かりやすく…

【3】　「p/2 未満」という表現を何度か使ったが、p は奇素数なので 2 では割り切れない: 無理やり割れば 0.5 の端数が生じる。p = 13 なら p/2 = 6.5 のように。だから、より精密に表現すると、「p/2 未満の整数」とは「p/2 − 0.5 以下の整数」。あるいは…
　　p/2 − 0.5 = p/2 − 1/2 = (p−1)/2
…なので (p−1)/2 以下の整数。p = 13 なら 12/2 = 6 以下。今後この (p−1)/2 という値を繰り返し使うので、簡潔に H と略すことにする:
　　定義　H = (p − 1)/2
H は考えている素数 p の半分（Hanbun）に当たる（端数切り捨て）。p = 13 なら H = 6 で、p = 23 なら H = 11 のように。

さて、出発点となる 1 以上 p/2 未満の整数（つまり 1, 2, 3, …, H）について、そのうち任意の一つを u とすると、u はもちろん p の倍数ではなく、仮定によって q も p の倍数ではない。従って uq は決して p で割り切れず、余りとして 0 が発生することはない: デカ余りはもちろんのこと、チビ余りも 1 以上。

1, 2, 3, …, H の一つ一つに対して「チビ余り」または「デカ余りを小さくしたもの」が一つずつ存在するのだから、「チビ余り」と「デカ余りを小さくしたもの」の合計個数は、H 個。「チビ余り」も「デカ余りを小さくしたもの」も、値は 1 以上 p/2 未満（つまり 1, 2, 3, …, H のどれか）。合計 H 個あって、重複がないのだから（【2】参照）、結局、「チビ余り」と「デカ余りを小さくしたもの」を合わせた中には「値1」が 1 個、「値2」が 1 個、「値3」が 1 個、…、「値 H」が 1 個、ある。要するに、順序の違いを無視して、次の数が1個ずつある:
　　1, 2, 3, …, H
最初の例題で、チビ余り《エ》の 1, 4 とデカ余りを小さくした《カ》の 3, 6, 2, 5 を合わせると、全体として 1, 2, 3, 4, 5, 6 となったが、それは、この現象の例だった。

要点: 「チビ余り」と「デカ余りを小さくしたもの」の全体は、1, 2, 3, …, H を並び替えたものにすぎない。

【4】　ガウスの補題の証明。
　　《タ》　1, 2, 3, …, H
をそれぞれ q 倍して、
　　《チ》　q, 2q, 3q, …, Hq
…を考える。今、《チ》の H 個の数を一つ一つ p で割って、余り（amari）をそれぞれ
　　《ツ》　a₁, a₂, a₃, … , a_H
とすると、q ≡ a₁, 2q ≡ a₂, … (mod p) となり、《チ》の各数はそれぞれ《ツ》の各数と合同。以下、合同式は全て mod p で考え、しばしば mod p という表記を省く。《ツ》をチビ余り・デカ余りに分類して並び替えると:
　　《テ》　c₁, c₂, c₃, … , c_m, d₁, d₂, d₃, … , d_n
もちろん m + n = H である。《テ》は《ツ》を並び替えただけなので、《テ》の各数は、引き続き、全体としては《チ》の各数と合同。他方、《テ》について、デカ余りの部分を次のように小さくした場合、その結果は、全体として《タ》の数を並び替えただけ（【3】参照）:
　　《ト》　c₁, c₂, c₃, … , c_m, p − d₁, p − d₂, p − d₃, … , p − d_n

《テ》と《チ》は全体として合同なので、《テ》の数全部の積と《チ》の数全部の積も合同:
　　(c₁c₂c₃…c_m)(d₁d₂d₃…d_n) ≡ (q)(2q)(3q)…(Hq)
この右辺には、因子 q が H 個あって、それらの係数は 1, 2, 3, …, H なので、こう整理できる:
　　《ナ》　(c₁c₂c₃…c_m)(d₁d₂d₃…d_n) ≡ (1⋅2⋅3…H)q^H

《ト》は《タ》を並び替えただけなので、《ト》の数全部の積と《タ》の数全部の積は等しい。等しいのだから、もちろん合同:
　　《ニ》　(c₁c₂c₃…c_m)[(p − d₁)(p − d₂)(p − d₃)…(p − d_n)] ≡ 1⋅2⋅3…H
《ニ》左辺 [] 内について p − d₁ ≡ −d₁, p − d₂ ≡ −d₂, … (mod p) という事実を使って、丸かっこの中身を全部簡単化すると:
　　《ヌ》　(c₁c₂c₃…c_m)[(−d₁)(−d₂)(−d₃)…(−d_n)] ≡ 1⋅2⋅3…H
《ヌ》左辺の [] 内には −1 という因子が n 個あるので、それらを (−1)ⁿ にまとめて、くくり出す:
　　《ネ》　(−1)ⁿ(c₁c₂c₃…c_m)(d₁d₂d₃…d_n) ≡ 1⋅2⋅3…H
左辺の (−1)ⁿ の後ろの部分に《ナ》から代入して:
　　(−1)ⁿ(1⋅2⋅3…H)q^H ≡ 1⋅2⋅3…H
両辺を (1⋅2⋅3…H) で割って:
　　《ノ》　(−1)ⁿq^H ≡ 1

《ノ》左辺のうち、(−1)ⁿ の部分はガウスの判定基準であり、+1 or −1 の値を持つ。

《ノ》左辺のうち、q^H つまり q^(p−1)/2 の部分はオイラーの判定基準であり、≡ +1 or −1 となる。

《ノ》によれば、この二つの値の積が ≡ 1 になるのだから、一方が +1 なら他方が +1 になり、一方が −1 なら他方が −1 になる。言い換えれば、ガウスの基準とオイラーの基準のどちらを使っても、同じ判定結果になる。ガウスの補題が証明された！

〔付記〕　《ノ》の解釈が分かりにくければ、次のように考えてもいい。(−1)ⁿ は n が偶数か奇数かに応じて +1 or −1 になるが、どっちにしても、自分に自分を掛ければ 1 になる:
　　(−1)ⁿ(−1)ⁿ = (+1)(+1) or (−1)(−1) = 1
つーことは《ノ》の両辺を (−1)ⁿ 倍すると、
　　(−1)ⁿ(−1)ⁿq^H ≡ (−1)ⁿ　←ここで (−1)ⁿ(−1)ⁿ = 1 なんで
　　q^H ≡ (−1)ⁿ
になるが、この左辺はオイラーの判定基準、右辺はガウスの判定基準。上の式から、二つの基準は一致。

ガウスの補題　p を奇素数、q を p で割り切れない数、H = (p−1)/2 とする。
　　q, 2q, 3q, … , Hq
を p で割った余りのうち p/2 より大きいものの合計個数を n とすると、L(q, p) = (−1)ⁿ。ここで L(q, p) は、q が mod p で平方剰余か非剰余かを表す（平方剰余なら 1 に等しく、非剰余なら −1 に等しい）。

【5】　具体例。第二補充・前編では「p = 17 や p = 23 なら 2 は平方剰余だが、p = 11 なら 2 は非剰余」という例を観察した。最初に、オイラーの基準によって、この事実を確認する。

p = 17 のとき: 17 × 15 = 17(10 + 5) = 170 + 85 = 255 は 17 の倍数。従って 2^(17−1)/2 = 2⁸ = 256 ≡ 1 (mod 17)。Yes判定。

p = 23 のとき: 23 × 89 = 23(90 − 1) = 2070 − 23 = 2047 は 23 の倍数。従って 2^(23−1)/2 = 2¹¹ = 2048 ≡ 1 (mod 23)。Yes判定。

p = 11 のとき: 33 は 11 の倍数。従って 2^(11−1)/2 = 2⁵ = 32 ≡ −1 (mod 11)。No判定。

☆　今度はガウスの基準を使って、同じ対象を判定してみると…

p = 17 のとき: H = 8 以下の正の整数を 2 倍すると:
　　2, 4, 6, 8, 10, 12, 14, 16
これを 17 で割った余りは、上記の数自身。デカ余り、つまり p/2 = 8.5 以上の余りは 10, 12, 14, 16 の 4 個なので n = 4。(−1)⁴ = 1。Yes判定。

p = 23 のとき: H = 11 以下の正の整数を 2 倍すると:
　　2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22
これを 23 で割った余りは、上記の数自身。デカ余り、つまり p/2 = 11.5 以上の余りは 12, 14, 16, 18, 20, 22 の 6 個なので n = 6。Yes判定。

p = 11 のとき: H = 5 以下の正の整数を 2 倍すると:
　　2, 4, 6, 8, 10
これを 11 で割った余りは、上記の数自身。デカ余り、つまり p/2 = 5.5 以上の余りは 6, 8, 10 の 3 個なので n = 3。(−1)³ = −1。No判定。

オイラーによる判定結果と全部一致した！

さて mod 11 で 3 は平方剰余だろうか？
　　3, 6, 9, 12, 15
これを 11 で割った余りは:
　　3, 6, 9, 1, 4
デカ余りが 6, 9 の 2 個なのでYes判定。実際 5² = 25 ≡ 3 (mod 11)。では 4 は平方剰余か？
　　4, 8, 12, 16, 20
これを 11 で割った余りは:
　　4, 8, 1, 5, 9
デカ余りが 8, 9 の 2 個なのでYes判定（4 は平方数なので、判定するまでもなく 2² ≡ 4 であることは分かり切ってるが）。では 5 は？
　　5, 10, 15, 20, 25
11 で割った余りは:
　　5, 10, 4, 9, 3　　デカ余りの個数 n = 2。Yes判定

同様に続けると、こうなる。ここで L(q, 11) は q が mod 11 で平方剰余なら +1、非剰余なら −1 とする。

6, 12, 18, 24, 30
6,  1,  7,  2,  8  n=3, L(6, 11) = −1

7, 14, 21, 28, 35
7,  3, 10,  6,  3  n=3, L(7, 11) = −1

8, 16, 24, 32, 40
8,  5,  2, 10,  7  n=3, L(8, 11) = −1

9, 18, 27, 36, 45
9,  7,  5,  3,  1  n=2, L(9, 11) = +1

10, 20, 30, 40, 50
10,  9,  8,  7,  6  n=5, L(10, 11) = −1

結局、mod 11 では、1, 3, 4, 5, 9 が平方剰余、2, 6, 7, 8, 10 が非剰余（1 は平方剰余: x² ≡ 1 を満たす x は必ず存在する。つまり x ≡ ±1）。0 を別にすると、平方剰余も非剰余も 5 個ずつ存在する。

平方剰余と非剰余が半々になる理由。q = 1², 2², 3², …, H² の H 種類の q に対して x² ≡ q (mod p) は解を持つ。だから少なくとも H 種類の平方剰余があるが、実はそれで全部。なぜなら (p − 1)² ≡ (−1)² ≡ 1², (p − 2)² ≡ (−2)² ≡ 2², …, (p − H)² ≡ (−H)² ≡ H² は、上記（既にカウント済み）の平方剰余と合同だし、0 を別にすれば、mod p における x² は、以上で全種類。結局、0 を除く p−1 種類の数のうち、半分の H 個だけが平方剰余。

原始根を使って説明することも可能。g を mod p の原始根とすると、1 から p−1 までの p−1 = 2H 個の数のそれぞれは、g^e のどれかと合同（e は 2H 以下の正の整数）。この 2H 種類の数のうち、e が偶数の場合が平方剰余（mod p の世界において、平方根 (g^e)^1/2 を持つ）、e が奇数の場合が非剰余。2H 以下の正の整数の中には、偶数・奇数が H 個ずつあるので、平方剰余・非剰余も H 個ずつ。

【6】　（参考）　デカ余り d を p − d に置き換える処理は、若干不自然とも思える。小さくすることで、関連する数を H 以下の正の整数に絞り、H! = 1⋅2⋅3…H に帰着させるのは妙案だが、d の置き換え先は、p − d よりも、符号が逆の d − p の方が透明だろう（d と合同のままなので、見通しが良い）。これが【2】で注記した「二股」のもう一方の道。こっちの経路も調べておこう。《キ》《ク》までは同じで、《ケ》の代わりに
　　《ゲ》　d₁ − p, d₂ − p, d₃ − p, … , d_n − p
を使う。《エ》のチビ余り 4, 1 と《オ》のデカ余り 10, 7, 11, 8 で言うと、《カ》の 3, 6, 2, 5 の代わりに −3, −6, −2, −5 を使い、全体としては
　　1, −2, −3, 4, −5, −6
になる。《キ》と《ゲ》を合わせたものは、絶対値が 1, 2, 3, …, H の H 個の数で、各数の符号は、チビ余り由来ならプラス、デカ余り由来ならマイナス（デカ余りは p/2 より大きく p 未満なので、そこから p を引けば、絶対値 p/2 未満の負の数になる）。《キ》内部、《ゲ》内部に合同な数が重複して現れないのはもちろんだが、《キ》と《ゲ》の間には、絶対値が同じで符号だけ反対の数はない。実際、チビのどれか c と《ゲ》の数のどれか d − p が「符号だけ反対」になったとすると
　　c + (d − p) = 0　つまり　c + d = p
　　両辺を p で割った余りについて　c + d ≡ 0 (mod p)
となるはずだが、《サ》以下で見たようにそれは不可能。

《タ》～《テ》が同じで《ト》の代わりに、次を使う:
　　《ド》　c₁, c₂, c₃, … , c_m, d₁ − p, d₂ − p, d₃ − p, … , d_n − p
このとき《チ》の数全部の積と《ド》の数全部の積が（ダイレクトに！）合同になる。前者は《ナ》で見たように (H!)q^H。後者について、《ド》は絶対値においては 1 から H までの各数、そのうちマイナスが付く数が n 個あるのだから (−1)ⁿ(H!)。従って:
　　(H!)q^H ≡ (−1)ⁿ(H!)
両辺を H! で割れば、直ちにガウスの補題を得る。おおっ！

これが高木 §14 の「Gauss の予備定理」の証明法であり、簡潔。式の左辺・右辺について Dirichlet とは逆の側に (−1)ⁿ が現れるため、《ノ》の両辺を (−1)ⁿ 倍するような手間も省ける。高木はチビ・デカ分類自体も省き、最初から絶対値最小の剰余を考えている。

証明という点では高木の方法はエレガントだが、実際の計算の観点からは、多くの場合、「絶対的最小剰余が負のものの個数」を数えるより、単に「普通に割り算して余りが p/2 より大きいものの個数」を数える方が自然だろう。しかも 1⋅2⋅3…H の因子の「不定の位置に不定の個数のマイナスが付く」という状況を式で表現しようとすると、若干技巧的になってしまう。Gauß / Dirichlet の方法は、1⋅2⋅3…H という積（符号は全部プラス）に話が固定され、具体的で分かりやすい。Gauß は、第三証明（1808）のときには【2】以下の方法で《ノ》を導き、第五証明（1818）のときは、同様に《ニ》まで進めてから両辺に (−1)ⁿ を掛け算して、p − d を d − p に変更している。Hardy & Wright, §6.11 は、高木と同様、絶対的最小剰余を使っている。現代の教科書では、それが標準だろう。一方 Apostol, Introduction to Analytic Number Theory (1976), §9.4 では Gauß / Dirichlet と同じく「デカ余り」を p から引き算し、1 から H の各整数が過不足なく出現するという事実をうまく活用している。

文献
[1] Dirichlet, Vorlesungen, §43
[2] Carl Friedrich Gauss' Untersuchungen über höhere Arithmetik, 457ページ以下
https://gdz.sub.uni-goettingen.de/download/pdf/PPN373456743/PPN373456743.pdf

下に続く。

2022-08-07　平方剰余の相互法則　Gauß の第三証明 Dirichlet 版 2/3

前回の続き。Vorlesungen の §44（99～102ページ）の内容を扱う。

【7】　本題に入る前に…。1 + 2 + 3 + … + 9 + 10 = 55 という足し算をご存じの方は多いだろう。こーゆー場合、両端から2個ずつペアにすると…
　　(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)
…どのペアも和が 11 で、ペアが5組あるので 11 × 5 = 55 と計算される。一般に 1 から H まで足すなら:
　　1 + 2 + 3 + … + H = (H + 1)(H/2)
ここで H + 1 は各ペアの和、H/2 は「ペアが全部で何組あるか」に当たる。

たとえ H が奇数で、真ん中に「ペアにならない項」が残ってしまっても、上の式はそのまま成り立つ。例えば:
　　1 + 2 + 3 + … + 9 + 10 + 11 = (11 + 1)(11/2) = (12 × 11) / 2 = 6 × 11 = 66
10 まで足すと 55 なので、11 を追加すれば 66 で合ってる。ペアからあふれる項があってもOKな理由は…。真ん中に取り残される項（この例では「6」）は、次のように、その左隣・右隣の平均に当たり、「ペアの和を2で割ったもの」に等しいので、「0.5組」相当の大きさを持つ:

A   B   C   D   E       E   D   C   B   A
1   2   3   4   5   6   7   8   9   10  11

ペアA = 1 + 11 = 12
ペアB = 2 + 10 = 12
ペアC = 3 + 9 = 12
ペアD = 4 + 8 = 12
ペアE = 5 + 7 = 12
「半ペア」 = 6 = (5 + 7)/2

従って、和が12のペアが「5.5組」ある…と考えれば計算が合う。上記 (11 + 1)(11/2) の通り。H と H + 1 のどちらかは偶数なので、それらの積は偶数。だから
　　1 + 2 + 3 + … + H = (H + 1)(H/2)
は、2分の1が絡むようでも、(H + 1)H が偶数なので割り切れて、ちゃんと整数になる。以下では、この公式を使う。

【8】　本題。例えば、素数 p = 13 について H = (13−1)/2 = 6 となる（前回【3】の定義参照）。今 q = 7 が mod p の平方剰余かどうか知りたいとする。ガウスの補題を使おう。余りの列は:
　　1q = 7　に対して　7÷13　商 0　余り 7　デカ余り:　d₁ = 7
　　2q = 14　に対して　14÷13　商 1　余り 1　チビ余り:　c₁ = 1
　　3q = 21　に対して　21÷13　商 1　余り 8　デカ余り:　d₂ = 8
　　4q = 28　に対して　28÷13　商 2　余り 2　チビ余り:　c₂ = 2
　　5q = 35　に対して　35÷13　商 2　余り 9　デカ余り:　d₃ = 9
　　6q (= Hq) = 42　に対して　42÷13　商 3　余り 3　チビ余り:　c₃ = 3
p/2 = 6.5 より大きければ（あるいは、同じことだが、H = 6 より大きければ）デカ余り。デカ余りが奇数個なので、判定結果はNo。

ここで、商は 1q, 2q, 3q, …, Hq のそれぞれを p で割って、小数点以下の端数を切り捨てたもの。例えば
　　5q = 35　に対して　35÷13　商 2
というのは、35/13 = 2 + 9/13 (=2.6923…) の端数を切り捨てたものに他ならない。

35÷13 が商 2 余り 9 というのは
　　35 = 13 × 2 + 9　つまり
　　《あ》　5q = 13 × 2 + 9
という意味を持つ。

一般に、奇数の素数 p が与えられたとき、それに対応して H = (p−1)/2 が定まる。さらに p の倍数ではない任意の q が与えられて、こうなったとしよう（商 shō を s で表す）:
　　1q　に対して　1q÷p　商 s₁　余り a₁
　　2q　に対して　2q÷p　商 s₂　余り a₂
　　3q　に対して　3q÷p　商 s₃　余り a₃
　　4q　に対して　4q÷p　商 s₄　余り a₄
　　………
　　Hq　に対して　Hq÷p　商 s_H　余り a_H
《あ》のように書くなら:
　　《い》　1q = ps₁ + a₁
　　《う》　2q = ps₂ + a₂
　　《え》　3q = ps₃ + a₃
　　………
　　《か》　Hq = ps_H + a_H

これら H 個の余り a₁, a₂, …, a_H が、前回のように
　　m 個のチビ余り　c₁, c₂, c₃, …, c_m
　　n 個のデカ余り　d₁, d₂, d₃, …, d_n
に分類されたとする。全部のチビ余りを足し合わせたものを大文字の C で表すことにする:
　　C = c₁ + c₂ + … + c_m
同様に、全部のデカ余りを足し合わせたものを大文字の D で表すことにする:
　　D = d₁ + d₂ + … + d_n
《い》から《か》までの全部の余りの和 a₁ + a₂ + … + a_H は、もちろん C + D に等しい。ついでに H 個の商の和を大文字の S で表すことにしよう:
　　S = s₁ + s₂ + … + s_H

今、《い》から《か》までの全部の左辺の和を考える（【7】の和の公式を利用）:
　　1q + 2q + 3q + … + Hq = (1 + 2 + 3 + … + H)q
　　= [(H + 1)(H/2)]q　　←【左】

さらに、《い》から《か》までの全部の右辺の和を考える（余りの和が C + D に等しいことを利用）:
　　(ps₁ + a₁) + (ps₂ + a₂) + … + (ps_H + a_H)
　　= ps₁ + ps₂ + … + ps_H + a₁ + a₂ + … + a_H
　　= p(s₁ + s₂ + … + s_H) + C + D
　　= pS + C + D　　←【右】

【左】と【右】は、《い》《う》《え》…ような「左辺と右辺が等しい」という等式の左辺同士の和・右辺同士の和の関係なので、もちろん等しい（等しいもの同士を足し合わせたものは等しいので）:
　　《き》　[(H + 1)(H/2)]q = pS + C + D

一方、デカ余りを（p から引く方法で）小さくしたもの（前回の【2】）と、チビ余りを合わせると:
　　《く》　c₁, c₂, …, c_m, p − d₁, p − d₂, …, p − d_n
この余りたちは、全体として
　　《け》　1, 2, 3, …, H
を並び替えたものになるのだった（前回の【3】）。《く》は順序の違いを無視すれば《け》と同じなので、《く》の全部の数を足し合わせたもの…
　　c₁ + c₂ + … + c_m + pn − (d₁ + d₂ + … + d_n)
　　= C + pn − D
…は、《け》の全部の数を足し合わせたもの
　　1 + 2 + … + H = (H + 1)(H/2)
に等しい:
　　《こ》　(H + 1)(H/2) = C + pn − D

等式《き》の両辺から同じものを引いた結果は、もちろん依然として等式となる。具体的に、《き》の左辺から《こ》の左辺を引き、《き》の右辺から《こ》の右辺を引くと…
　　[H(H + 1)/2]q − [(H + 1)H/2] = pS + C + D − (C + pn − D)
　　[H(H + 1)/2](q − 1) = pS + C + D − C − pn + D　つまり
　　《さ》　[(H + 1)(H/2)](q − 1) = p(S − n) + 2D

何やらゴチャゴチャした式だが、ここで問題なのは「デカ余りの個数 n が偶数か・奇数か」だけ（それによって q が平方剰余か非剰余かが決まる）。「偶数か奇数か？」以外の情報は必要ないので、《さ》を mod 2 で考えることにする。すると、偶数（つまり 2 の倍数）の項 2D は ≡ 0 (mod 2) なので消えちゃうし、p は奇数の素数なので、シンプルに ≡ 1 (mod 2) となる。すなわち…
　　[(H + 1)(H/2)](q − 1) ≡ S − n (mod 2)　　←《さ》を mod 2 で考えた。移項すると…
　　《し》　n ≡ S − [(H + 1)(H/2)](q − 1) (mod 2)

【9】　ここで、もし「q は奇数」という条件を追加するなら、q − 1 は偶数（つまり 2 の倍数）なので、《し》の右辺第2項も ≡ 0 (mod 2) となって消滅し、《し》は
　　《す》　n ≡ S (mod 2)
となる。q が奇数の場合、デカ余りの個数が偶数か奇数かという区別は、商の和が偶数か奇数かと一致する！

〔例〕　【8】冒頭の p = 13, q = 7 の場合、デカ余りが奇数個だった。商の和 0 + 1 + 1 + 2 + 2 + 3 = 9 は確かに奇数で、デカ余りの個数と「偶・奇」が一致する。

かくして、ガウスの補題との関係では、「デカ余りの個数」の偶・奇の代わりに「商の和」の偶・奇を考えてもいい。p = 13, q = 7 の例で言えば、
　　S = (7/13 の端数を切り捨てた整数) + (2⋅7/13 の端数を切り捨てた整数)
　　　　+ (3⋅7/13 の端数を切り捨てた整数) + … + (6⋅7/13 の端数を切り捨てた整数)
は、別に難しい計算でもない。p, q が不特定のとき「端数を切り捨てる」という部分をどうやって扱うのか…というのが問題だけど、これをすっきり整理できれば、大きな収穫が得られるかもしれない。

【10】　（参考）　その探検を始める前に、ちょっと寄り道: 「q は奇数」という条件を付ける前の《し》も、研究しておく価値がある（つまり q が偶数でもOK）: q = 2 が平方剰余か非剰余かは、第二補充法則に従うのだが（そしてわれわれは、ガウス、ディリクレと共に、既に第二補充法則を直接証明したのだが）、《し》に q = 2 を入れると、右辺は簡単な形になる:
　　《せ》　n ≡ S − [(H + 1)(H/2)]
しかも q = 2 の場合、一番大きい《か》の商でも
　　Hq÷p の端数を切り捨てた整数　つまり
　　H⋅2/p の端数を切り捨てた整数
であり、H の定義は (p − 1)/2 なのだから、これは
　　[(p − 1)/2]⋅2/p の端数を切り捨てた整数
　　つまり　(p − 1)/p の端数を切り捨てた整数
に当たる。(p − 1)/p は 2/3 とか 6/7 とか 12/13 のようなもので、明らかに 1 未満の正の数。なので、端数を切り捨てた整数は 0。他方、《い》に当たる最小の商は
　　1q÷p = 2/p の端数を切り捨てた整数
であり、これも 0。要するに、商は最小も最大も 0、つまり全部 0 なので、商の和は S = 0。このとき《せ》は:
　　《そ》　n ≡ −[(H + 1)(H/2)] (mod 2)

「n が奇数か偶数か？」が問題の核心だった。「正の奇数・負の奇数」の区別や「正の偶数・負の偶数」の区別は必要ない（つまり符号はどーでもいい）。だから邪魔くさい右辺の頭のマイナスも、消しちゃお。そして H の定義を思い出すと…
　　H + 1 = (p − 1)/2 + 1 = (p − 1)/2 + 2/2 = (p + 1)/2
　　一方　H/2 = [(p − 1)/2]/2 = (p − 1)/4
《そ》右辺について（頭のマイナスを消して）上の2式を使うと:
　　n ≡ (H + 1)(H/2) = [(p + 1)/2][(p − 1)/4] = (p + 1)(p − 1)/8
　　つまり n ≡ (p² − 1)/8 (mod 2)　　← (p+1)(p−1) を展開すると p²−1

結局、3 以上の素数 p が与えられたとき、もし (p² − 1)/8 が偶数なら 2 は mod p において平方剰余、(p² − 1)/8 が奇数なら 2 は非剰余。これは、第二補充・後編の『よ』で紹介した謎の式の指数に他ならない。ガウスの補題経由で、再び第二補充法則が証明された！　（下に続く）

2022-08-09　平方剰余の相互法則（続き）　Gauß の第三証明 Dirichlet 版 3/3

前回の続き。寄り道から本道に戻って、相互法則の証明を完成させよう。

【11】　引き続き p を 3 以上の素数とする。p の倍数以外の数 q が mod p において平方剰余か？を L(q, p) で表すことにする: L(q, p) の意味は q が平方剰余なら = 1、非剰余なら = −1 とする。

第一に、オイラーの基準によれば L(q, p) ≡ q^H (mod p)。ここで H = (p − 1)/2。

第二に、ガウスの補題によれば L(q, p) = (−1)ⁿ。ここで n は【1】のデカ余りの個数。

第三に、ガウスの補題からの発展として、q が奇数という条件なら、L(q, p) = (−1)^S とも書ける（【9】参照）。ここで S は、チビ余り・デカ余りを求めるときに発生する商の和:
　　S = s₁ + s₂ + s₃ + … + s_H
この場合、商というのは【8】で見たように:
　　1q/p の（小数点以下の）端数を切り捨てたものが s₁
　　2q/p の端数を切り捨てたものが s₂
　　3q/p の端数を切り捨てたものが s₃
　　………
q が負のとき、負の分数 1q/p, 2q/p, 3q/p, … の「端数を切り捨てる」という意味は紛らわしい。以下の議論では必要もないので、シンプルに q は正の奇数としておこう！

便宜上、これからしばらくの間（【11】～【16】）、0 以上の数 A の（小数点以下の）端数を切り捨てた整数を [A] で表すことにする。

〔例〕　[2.5] = 2, [1/3] = 0, [9/13] = 0, [40/11] = 3, [7] = 7

この記法を使うと、上記の商の和 S は:
　　《た》　S = [1q/p] + [2q/p] + [3q/p] + … + [Hq/p]

〔例〕　p = 13, q = 9 とすると（H = (13−1)/2 = 6 なので）:
　　S = [1⋅9/13] + [2⋅9/13] + [3⋅9/13] + [4⋅9/13] + [5⋅9/13] + [6⋅9/13]
　　 = [9/13] + [18/13] + [27/13] + [36/13] + [45/13] + [54/13]
　　 = 0 + 1 + 2 + 2 + 3 + 4 = 12

ここで第2項の 1 は、18/13 = 1.38… の端数を切り捨てたものに当たる。実際には、小数点以下の計算は必要ない: 正の数の範囲で「18 から 13 の 1 倍は引けるが、13 の 2 倍 26 は引けない」つまり「18 から 13 は 1 回までしか引けない」ので商（の整数部分）は 1。この考え方だと、1.38… を計算して 0.38… を切り捨てる手間が省ける。同様に、第3項の 2 は「27 から 13 は 2 回引ける」、第4項の 2 は「36 から 13 は 2 回引ける」、第5項の 3 は「45 から 13 は 3 回引ける」、第6項の 4 は「54 から 13 は 4 回引ける」という意味。第1項の 0 は「9 から 13 は 1 回も引けない」。
和 S = 12 なので、結局 L(9, 11) = (−1)^S = (−1)¹² = 1 となり 9 は mod 11 において平方剰余。…これは説明のための例で、9 = 3² が平方数（従って平方剰余）ってことは、初めから分かり切っている。

【12】　q が（単に正の奇数というだけでなく）奇数の素数の場合、L(q, p) と L(p, q) は一定の関係を持つ。つまり mod p で q が平方剰余か非剰余か？と、mod q で p が平方剰余か非剰余か？という二つの事柄を比較した場合、前者と後者は単純に「常に一致する」わけでも「常に逆になる」わけでもないが、一定の法則に従う。この法則が「平方剰余の相互法則」。ガウスはこれを「根本法則」と呼び、6種類もの証明を発表した！

L(q, p) = (−1)^S が《た》の S によって表されるのだから、ひっくり返した L(p, q) は、次の和 T によって表される:
　　《ち》　T = [1p/q] + [2p/q] + [3p/q] + … + [Ip/q]
　　　　そして　L(p, q) = (−1)^T
ここで I = (q − 1)/2 は、H = (p − 1)/2 に対応する「q バージョン」。つまり素数 q の半分（端数切り捨て）:
　　定義　I = (q − 1)/2　　←【3】の H の定義と同様

今までずっと p が奇数の素数のときの q (mod p) を考えていたが、q も奇数の素数だとすると、話を逆にして p (mod q) を考えることもできるわけである！

逆にすると何が起きるのか？

《た》の S と《ち》の T には、一体どういう関係があるのか？

探検を始めよう。

値が 3 以上の相異なる素数が任意に 2 個与えられたとき、大きい方を p、小さい方を q と呼ぶことにしよう（q < p）。このように大小を定めておくと、《た》左辺の隣り合う2項は、値が等しいか、または右側が 1 大きい。例えば 2q/p と 3q/p を比べると――あるいは、より一般的に、第x項の [] 内にある xq/p と、次の項の [] 内にある (x+1)q/p を比べると――、後者の方が q/p だけ大きいが、q < p なので、この分数は 1 未満。だから 2 以上大きくなることは、あり得ない。他方、端数の部分が例えば 0.9 くらいなら、そこからの増加が 1 未満（例えば 0.2 くらい）でも、結果的に整数部分が 1 大きくなることはある。

〔例〕　p = 19, q = 7 とすると、第1項 [1⋅7/19] = 0 と第2項 [2⋅7/19] = [14/19] = 0 は等しいが、第3項 [3⋅7/19] = [21/19] = 1 はそれより 1 大きい。

《た》左辺の第1項 [1q/p] = [q/p] が = 0 であることは言うまでもない（q < p なのだから 1 未満の数 q/p の小数部分を切り捨てている）。《た》左辺の最終項について、[] 内の…
　　《つ》　Hq/p = (p − 1)/2 × q/p = (pq − q) / (2p)
…は (pq) / (2p) = q/2 と比べると（分子に −q があるので q / (2p) だけ）小さい。では (q − 1)/2 よりは大きいだろうか、小さいだろうか？　確かめるため《つ》から (q − 1)/2 を引いてみる:
　　Hq/p − (q − 1)/2 = (pq − q) / (2p) − (q − 1)/2　←《つ》より
　　通分すると　= (pq − q) / (2p) − (pq − p) / (2p) = (−q + p) / (2p)　要するに
　　《て》　Hq/p − (q − 1)/2 = (p − q) / (2p)
《て》右辺の分数について、q < p だから分子 p − q は p 未満の正の数、従ってこの分数は p / (2p) = 0.5 未満の正の数。結局《つ》は (q − 1)/2 より少し大きいが、差は 0.5 未満。今、《て》の左辺第2項を右辺に移項すると:
　　Hq/p = (q − 1)/2 + (p − q) / (2p)
ここで q は奇数（の素数）だから q − 1 は偶数、(q − 1)/2 は整数。結局、《つ》の値は、整数部分が (q − 1)/2 で、それに 0.5 未満の端数が付く。端数切り捨ての [] 記号を使うと:
　　[Hq/p] = (q − 1)/2
《ち》の所で定義した I を使い、簡潔に書くと:
　　[Hq/p] = I

【13】　結局《た》の S = [1q/p] + [2q/p] + [3q/p] + … + [Hq/p] は、0 から始まって I で終わる整数…
　　0, 1, 2, 3, …, I
…を足し合わせたもの。でも《た》の和は、もちろん H 項ある。p は q よりでかいので、H = (p − 1)/2 は I = (q − 1)/2 よりでかい。そうすると、一般論として、和 S は、シンプルな
　　0 + 1 + 2 + 3 + … + I
と比べると、もっと項数が多く、もう少し複雑なパターンになる。

〔例〕　p = 19, q = 7 の場合、H = (19−1)/2 = 9, I = (7−1)/2 = 3 で:
　　S = [7/19] + [14/19] + [21/19] + [28/19] + [35/19] + [42/19] + [49/19] + [56/19] + [63/19]
　　 = 0 + 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3　　←和の項として「0」が2回、「1」と「2」が3回ずつ反復、「3」が1回
ちなみに上の和 S = 12 は偶数なので、7 は mod 19 の平方剰余。式で書けば L(7, 19) = (−1)¹² = 1。実際 r = 8 が r² ≡ 7 (mod 19) を満たす。

このパターンをどう把握するか？　つまり 0 から I までの数を合計 H 個、足し算する中で、何が何回リピートされるのか？　これこそが、平方剰余の相互法則についてのガウスの第三証明の技術的核心である！

いよいよ物語は佳境へ…

【14】　アイゼンシュタインは、この問題をエレガントな幾何学的議論に帰着させたが、その土台となったガウス、ディリクレの発想は、算数のような実直なものだった。われわれは、源流となったディリクレのルートを行く（この道を歩いてみてこそ、アイゼンシュタインの工夫の意味も分かるだろう）。「何が何回リピートされるのか？」を直接数えようとせず、「どこで値が 1 増えるのか？」と考えてみよう。上の例では、第2項 [14/19] と第3項 [21/19] において値が「0」から「1」に増えている。さらに第5項 [35/19] と第6項 [42/19] において値が「1」から「2」に増えている。そうすると、第5項以前に限って値が 1 以下、第2項以前に限って値が 0 なので、値が 1 の項はそれらの間にあり、つまり 5 − 2 = 3 項と分かる！

そんなふうに、「直前の項より値が 1 増える項」は第何項か？を知りたい。「第x項の値と比べて、その次の項の値（y とする）は 1 大きい」として、項の番号 x が求まるか試してみよう。つまり:
　　[xq/p] = y − 1, [(x+1)q/p] = y
　　↑意味　第x項の値はまだ y − 1 だが、その次の項の値は y
要するに:
　　xq/p は整数 y よりちょっとだけ小さいよ。
　　(x+1)q/p は整数 y よりちょっとだけ大きいよ。
　　★ 第x項（その値は [xq/p] である）は、値が y 未満の最後の項　←重要な観察！

〔注意〕　xq/p または (x+1)q/p が割り切れて整数 y とちょうど等しくなるためには、分子が分母 p の倍数になる必要がある。分子が p の倍数になるためには x, q, x+1 のどれかが p の倍数になる必要がある（p は素数なので）。ところが、この q は素数なので、p の倍数ということはあり得ない。さらに、第x項の xq/p にせよ、第(x+1)項の (x+1)q/p にせよ、項の番号 x ないし x+1 は、1 から H の範囲なので（そして H は p の半分未満なので）、x や (x+1) が p の倍数になることもあり得ない。だから、整数 y との大小関係は、上記のように「ちょっと小さい・ちょっと大きい」と表現される――等しい可能性はないので「以下」や「以上」ではない。

式で書くと:
　　xq/p < y < (x+1)q/p
この不等式全体を p/q 倍して、両端の分母を払うと:
　　x < yp/q < x+1　← p/q は正なので不等号の向きは変わらない

この最後の不等式によると: yp/q という数は、整数 x と整数 x+1 の間にある。つまり yp/q の端数を切り捨てた整数が、問題の項の番号 x である:
　　《と》　x = [yp/q]

これで x と y の関係が分かった！　しかも★によって: 第x項――《と》によれば、それは第 [yp/q] 項である――が、値 y 未満の最後の項…と判明した。

〔解説〕　商の和 S = s₁ + s₂ + … + s_H を構成する項として、同じ一つの値（それを y としよう）の項が何回反復するか？が問題だった（【13】の例参照）。その重大な手掛かりとして、値が y に増える直前の項を s_x とすると、《と》によって、その項の番号 x を決定できる。

《と》は、整数 y を入力として、値が y 未満になる最後の項の番号 x を求める式になっている。といっても、和 S を構成する各項の値は 0 以上 I 以下なので（【13】参照）、その範囲外の y を《と》に入れると、無意味な計算になるだろう。「有効範囲の確認」ということをひとまず脇に置いて、とにかく有効範囲内の計算をしてるとするなら、任意の y（例えば 3）について《と》が成立。任意の数でいいのだから y を y−1（例えば 2）に置き換えても構わない。実際に《と》の y を y−1 に置き換え、再び★の観察を使うと: 第 [(y−1)p/q] 項が、値 y−1 未満の最後の項。

それらの間の [py/q] − [(y−1)p/q] 個の項が、値 y−1 を持つ！

〔例〕　【13】では p = 19, q = 7 としたところ、S の第3項～第5項の三つが値「1」になった。上の観察に当てはめると、これは値 y−1 = 1 のケース、つまり y = 2 のケース。《と》によると:
　　x = [2p/q] = [2⋅19/7] = [38/7] = 5
★の予言通り、第5項が値 y = 2 未満の最後の項になっている。同様に y = 1 とすると:
　　x = [1p/q] = [1⋅19/7] = [19/7] = 2
つまり、第2項が値 y = 1 未満の最後の項（言い換えると第3項は値「1」を持つ）。よって、値「1」を持つ項の総数は
　　[2p/q] − [1p/q] = 5 − 2 = 3
全てのつじつまは合っている！

【15】　《と》を使えば、何が何項あるのか式で表せるんだけど、注意点として、この計算には有効範囲がある。和 S を構成する各項の値は 0 から I までのどれかの整数なので、項の値がその範囲外になっちゃ駄目だろうし、S は、第1項から第 H 項までの H 個の項の和なので、項の番号 x がこの範囲外になっても駄目だろう。どこからどこまで何を足せばいいのか、和の開始部分・終了部分を検討しよう…。

まず和の開始部分、つまり値「0」の項だが、《と》に y = 0 をぶち込むと x = 0 となって計算上「値 0 未満の最後の項は第0項」つまり「第0項の値は −1」となる。けれど、この和は第1項 s₁ から始まるので、第0項なんて、そもそも存在しない。値「0」を持つ最初の項は第1項…と再解釈するなら、結論は正しそうだが、どっちにしても値「0」の項なんてもんは和に影響しないんだから、最初から無視して、値「1」の項から考え始めるのが得策だろう。「値 1 未満の最後の項」の番号は、《と》によると:
　　x = [1p/q]
同様に、「値 2 未満の最後の項」の番号は:
　　x = [2p/q]
従って [2p/q] − [1p/q] 個の項が値「1」を持つ。

次に和の終了部分、つまり値 I の項だが、《と》に y = I をぶち込むと、「値 I 未満の最後の項」の番号が分かる:
　　《な》　x = [Ip/q]
最後の項の値がちょうど I に等しいこと（従って値 I 未満の項が存在すること）は保証されているので（【13】参照）、《な》は有効範囲内。その次の項から、値 I になるわけだが、一体、値 I の状態は第何項まで続くのか？　それを調べるため《と》に y = I + 1 を代入したい誘惑に駆られるかもしれないが、そいつはまずいぜ！　再び p = 19, q = 7, I = 3 を例にすると、もしも y = I + 1 = 4 を《と》に入れると:
　　x = [4p/q] = [4⋅19/7] = [76/7] = 10
となって、計算上「値 4 未満の最後の項は第10項」つまり「第10項までは値 3」となるけど、p = 19 なら H = 9 なので、S の和には「第9項」までしかない。存在しない「第10項」なんてもんをカウントしたら、項の数が合わなくなる。ここはもっと単純に考えて…。S の和は第 H 項で終わるんだから、もちろん第 H 項（つまり最終項）が値 I を持つ最後の項。従って《な》と組み合わせると H − [Ip/q] 個の項が値 I を持つ。

【16】　まとめると: 和 S の内訳は（値「0」の項を無視して）次の通り。

• 値「1」の項が　[2p/q] − [1p/q] 個　→　小計 = 1 × ([2p/q] − [1p/q])
• 値「2」の項が　[3p/q] − [2p/q] 個　→　小計 = 2 × ([3p/q] − [2p/q])
• 値「3」の項が　[4p/q] − [3p/q] 個　→　小計 = 3 × ([4p/q] − [3p/q])
• ………
• 値「I−1」の項が　[pI/q] − [p(I−1)/q] 個　→　小計 = (I−1) × ([pI/q] − [p(I−1)/q])
• 値「I」の項が　[pI/q] − H 個　→　小計 = I × (H − [pI/q])

ここで「小計」というのは…。例えば、値「2」の項が A 個あるとしたら、それらの項の和はもちろん 2 × A だよね。そういうふうに、値「2」の項だけを考えた場合の「項の値の和」が「小計」。値「2」以外でも同様。

下から2番目の「値 I−1 の項」の計算は、値 y−1 を持つ項の数（【14】参照）の y を I に置き換えたものに当たる。

一番下の「値 I の項」の計算は、【15】で調べた「和の終了部分」に対応している。

この小計たちを全部縦に足し合わせれば、S の値になるわけだが、分配法則を使うと、最初の小計の一部として (−1)[1p/q] という負の数が出てくる。最初の小計の残りの部分は (1)[2p/q] という正の数だが、2番目の小計から (−2)[2p/q] が出てくるので、その二つを合わせるとマイナス側が勝って、負の数 (−1)[2p/q] が残る。同様に、2番目の小計から (2)[3p/q] が出るものの、3番目の小計から出てくる (−3)[3p/q] と合わせると、再び負の数 (−1)[3p/q] が残る。同様に進めると、(−1)[4p/q], (−1)[5p/q], (−1)[6/q], … の形の負の数が次々と残り、(−1)[Ip/q] に至るのだが、最後の小計から出てくる正の数 I × H = HI だけは、このパターンを免れ、無傷で残る。要するに:
　　S = (−1)[1p/q] + (−1)[2p/q] + (−1)[3p/q] + … + (−1)[Ip/q] + HI
HI 以外の項から −1 をくくり出すと:
　　《に》　S = −([1p/q] + [2p/q] + [3p/q] + … + [Ip/q]) + HI

ずいぶん前の【12】で登場した伏線《ち》…
　　T = [1p/q] + [2p/q] + [3p/q] + … + [Ip/q]
…が、ここで魔法のように回収され、《に》は次の意味を持つ:
　　S = −T + HI　移項すると
　　《ぬ》　S + T = HI

S は、L(q, p) = (−1)^S の形で q が mod p の平方剰余か？を支配し、T は、L(p, q) = (−1)^T の形で p が mod q の平方剰余か？を支配するのだった。すると L(p, q) と L(q, p) の積は、《ぬ》を使うと:
　　L(p, q) L(q, p) = (−1)^T(−1)^S = (−1)^S+T = (−1)^HI
　　ここで　HI = (p−1)/2 × (q−1)/2 = (p−1)(q−1)/4　　← H と I の定義より
　　だから　L(p, q) L(q, p) = (−1)^HI = (−1)^{(p−1)(q−1)/4}

【17】　すなわち、次が証明された。

平方剰余の相互法則　p, q を 3 以上の相異なる素数とするとき:
　　《ね》　L(p, q) L(q, p) = (−1)^{(p−1)(q−1)/4}

法則の具体的意味を説明する前に、まず p, q の大小関係をクリアにしておきたい。証明内では p の方が大きいと仮定した。これは、このルートでの証明のために必要な仮定だった。けれど、実際に《ね》を使う場合、p, q の大小関係を気にする必要はない。なぜなら《ね》は p と q について、完全に対称的。従って q の方が大きい場合でも、単に p と q の変数名を入れ替えれば、上記の証明がそのまま有効。実質上 p > q と p < q の両方のケースについて証明が済んでいる。

さて p も q も奇数（の素数）なので、p−1 と q−1 はそれぞれ偶数。p−1 = 2u, q−1 = 2v とでも置くと、(p−1)(q−1) = 4uv は 4 の倍数なので、法則の指数の分数 (p−1)(q−1)/4 = (4uv)/4 = uv は必ず割り切れて、整数になる。例えば p = 19, q = 7 なら (19−1)(7−1)/4 = (18)(6)/4 = 27。あるいは 19−1 = 2u と置くと u = 9 で、7−1 = 2v と置くと v = 3 なので、uv = 9 × 3 = 27 が指数。指数が奇数ということは、上の法則によれば
　　《の》　L(19, 7) L(7, 19) = (−1)²⁷ = −1
となるが、L(19, 7) も L(7, 19) も、平方剰余か非剰余かに応じて 1 or −1 の値を持つのだった。では「それらの積が −1」という《の》の意味は…。もしも L(19, 7) と L(7, 19) が両方とも 1 になるか、または両方とも −1 になれば、それらの積は 1 になるはず。他方、L(19, 7) と L(7, 19) の片方だけが 1 で、もう片方が −1 になるとすれば、それらの積は −1 になる。…《の》の積 −1 は、後者が真実であること――すなわち L(19, 7) と L(7, 19) は一致しないこと――を意味する。

「一致する・しない」の真意は以下で次第に明らかになるが、《ね》の値は 1 or −1 なのだから、L(p, q) と L(q, p) の値は、もし両方 1 か両方 −1 なら「一致する」、さもなければ「一致しない」。

一般論として、L(p, q) と L(q, p) は一致するのか、しないのか。上記の通り、指数 uv が偶数であれば一致するし、奇数であれば一致しない。言い換えれば u と v の少なくとも一方が偶数なら一致し、u と v が両方とも奇数なら一致しない。

もし p と q の中に「4k+1型」の素数（愛称: バニラ素数）が一つでも含まれていれば…。例えば p = 4k+1 だとすれば、p−1 = 2u は (4k+1)−1 = 4k に等しいので u = 2k は偶数となり、「一致」の条件が満たされる。q が「4k+1型」の場合も同様。

他方、もし p と q が両方とも「4k+1型」でない場合――すなわち p, q が両方とも「4k+3型」の素数（愛称: チョコレート素数）の場合――、「一致」の条件は満たされない。実際、p = 4k+3 だとすれば、p−1 = 2u は (4k+3)−1 = 4k+2 に等しいので u = 2k+1 は奇数。同様に q もチョコレート素数なら v も奇数になって uv は奇数。この場合 (−1)^uv つまり《ね》の値は −1 となり、L(p, q) と L(q, p) は一致しない。

奇数を 4 で割れば 1 余るか 3 余るかのどちらかなので（余りが 0 or 2 なら、それは偶数！）、3 以上の素数（つまり奇数の素数）は、必ずバニラとチョコレートのどちらかに分類される（偶数の素数 2 は、どちらでもないが、ここでは奇数を考えている）。

要するに、p と q が両方バニラ素数であるか、または一方がバニラ素数、他方がチョコレート素数であれば（つまりバニラ素数が一つでも含まれていれば）、L(p, q) を計算する代わりに、ひっくり返した L(q, p) を計算してもいい（両者は一致する）。p と q が両方チョコレート素数の場合にも、L(p, q) の計算をひっくり返した L(q, p) の計算に帰着させることができるが、この場合、前者と後者は一致しない――つまり符号が反対になる:
　　p, q が両方ともチョコレートなら L(p, q) = −L(q, p)　　←符号が変わる
　　p, q の少なくとも一方がバニラなら L(p, q) = L(q, p)　　←符号が変わらない

これが、相互法則の実質的な意味。

〔例〕　7 と 19 は両方ともチョコレート素数なので、L(7, 19) と L(19, 7) は《の》で見た通り符号が逆。これは、どちらか一方だけが平方剰余で、他方は非剰余ということ。まず 7 は mod 19 の平方剰余か。すなわち r² ≡ 7 (mod 19) を満たす r が存在するか。r = 8 のとき r² = 64 は 19 の倍数 57 より 7 大きいのだから、答えはYes。すると、ひっくり返した問い「19 は mod 7 の平方剰余か？」は、確かめるまでもなく、逆の答えNoとなる。…確認として r² ≡ 19 (mod 7) を満たす r は存在しない: 19 ≡ 5 (mod 7) なので、r² ≡ 5 (mod 7) を考えても同じことだが、r = ±1, ±2, ±3 のどれを試しても、r² はそれぞれ 1, 4, 9 ≡ 2 (mod 7) なので ≡ 5 にはならない。［実は 19 ≡ 5 ≡ −2 (mod 7)。第二補充法則との関連において、「法の素数が春・夏のときに限って −2 が平方剰余」ってことを証明してあるので（第二補充・後編【16】）、「mod が冬素数 7 の場合には −2 は非剰余」と直接判定できる。］

【18】　けれど、そもそも L(p, q) をひっくり返して L(q, p) に帰着させることに、どんな意味があるのだろうか？　こんなことが何の役に立つの？

本質を言うなら、平方剰余の相互法則は「より深い数論的性質」の現れだろう。では、その「より深い数論的性質」とやらは、一体何の役に立つのか？

これについては、二つの観点から眺める必要がある。

第一に、ちょっと哲学的な話になるが、数論の「価値」を決めるのは「当事者の感覚」だろう…。
　　r² ≡ p (mod q) を満たす r が存在するか？
　　r² ≡ q (mod p) を満たす r が存在するか？
…この二つの問いの答えは、常に一致するわけでもなく、常に一致しないわけでもない。相異なる奇素数 p, q の選び方によって、一致するかしないかが決まる。メタ的な観点として、根本的な問題は「あなたは、このことに不思議さや魅力・好奇心を感じるか？」――それは好みの問題で、数論をすてきと思えるなら、すてきなことが一つ増えるんだから結構なことだし、すてきと思えないとしても別に不幸せになるような問題でもないだろう。

つまり「それ自体が美しい。何の役に立つかなんて関係ない！」という観点があり得る。

第二に、数論内部の実用的観点からすると、平方剰余の相互法則は、ややこしい問題を簡単な問題に変換する働きを持つ。Dirichlet が §45 で取り上げ、高木が §13 でそのまま引用している例題は:
　　L(365, 1847)　すなわち r² ≡ 365 (mod 1847) は解を持つか？
ここで 1847 は素数であり、365 は 5 × 73 と素因数分解される。平方剰余の判定は「分解して考える」ことができるのだった（第二補充・中編【11】）:
　　《は》　L(365, 1847) = L(5, 1847) L(73, 1847)

まず《は》右辺の L(5, 1847) つまり r² ≡ 5 (mod 1847) の解の有無だが、それを調べるために、約900種類の r の可能性を一つずつ試すのは、あまり優雅ではない。ところが 5 はバニラ素数なので、
　　L(5, 1847) = L(1847, 5)
…と、そのままひっくり返すことができる。これで問題は r² ≡ 1847 (mod 5) の解の有無に帰着され、1847 ≡ 2 (mod 5) なので、要するに r² ≡ 2 (mod 5) の解の有無に帰着され、第二補充法則（5 は「8k+5型」…秋素数）によって、直ちにNo判定される:
　　《ひ》　L(5, 1847) = −1
これが「ひっくり返せることの、ありがたみ」。

《は》のもう一つの因子だが、73 もバニラ素数なので、そのままひっくり返すことができる:
　　L(73, 1847) = L(1847, 73) = L(22, 73)
2個目の等号の根拠は 1847 ≡ 22 (mod 73)。実際 73 × 50 = 3650 は分かってるのだから、その両辺を半分にすれば 73 × 25 = 1825。でまぁ 1847 から 73 の倍数 1825 を引いても、73 で割った余りは変わらない、ってなわけで、1847 ≡ 22 (mod 73) ってことに。こいつを分解して判定:
　　L(22, 73) = L(2, 73) L(11, 73)
このうち L(2, 73) = 1 は第二補充法則から分かるので（73 = 8×9+1 は「8k+1型」…春素数）、判定から除外し、L(11, 73) だけ考えればいい。73 もバニラ素数なので、またひっくり返しちゃお:
　　L(11, 73) = L(73, 11) = L(7, 11)　　←両方チョコ。これをひっくり返すと符号が変わる
　　 = −L(11, 7) = −L(4, 7)　　← ４は平方数（2² ≡ 4）なので L(4, 7) = 1
　　 = −(1) = −1
　　2番目の等号の根拠は 73 ≡ 7 (mod 11)。4番目の等号の根拠は 11 ≡ 4 (mod 7)。
これが L(73, 1847) の判定結果なので、《ひ》と合わせると、《は》の判定結果は:
　　L(5, 1847) L(73, 1847) = (−1)(−1) = 1
すなわち、r² ≡ 365 (mod 1847) は解を持つ^*6…と結論される。

*6　具体的には、r = 496 とすると r² = 246016 を 1847 で割った余りが 365 になる。

「具体的な解は必要はないが、解の有無を知りたい」という局面において、このような計算はそれなりに役に立つ。とりあえず「自由にひっくり返せるってのは、場合によっては便利そう…」という感触がつかめるだろう。

以上がガウスの第三証明・ディリクレ版。現代の教科書の証明と比べると、いかにも古風。幾何学的証明を使った方がスマート。だが、あえてこの道を歩いてみることで、見えてくるものもある。

平方剰余の相互法則は、ヤコビの記号などを通じて、数論上のさまざまな問題（例えば楕円曲線）を扱う基本ツールとなり、広い意味で言えば、現代の日常生活の基盤となるインターネットの「セキュアな通信」などにも関わってくる。けれど「応用が利くから価値がある」といった損得勘定のような見方をせず、純粋に「数の世界の奥深さ」を楽しみたい。

[ 参考文献一覧 ]

いつか　あふれそうなときめき
両手に抱き　戻ってくるの　ここへ

2022-08-19　知られざるアイゼンシュタイン　Eisensteinによる相互法則の証明

Gauß は「平方剰余（じょうよ）の相互法則」の重要性を感じ、生前、6種類もの証明を公表した。人類初の証明に当たる第一・第二証明は、1801年、名高い『算術の研究』¹で発表されたが、Gauß 自身は「複雑過ぎる・不自然」と不満を抱いていたようだ。

1807年、Gauß は簡潔な第三証明を完成（1808年発表）。現代の証明は、大抵これをベースとしつつ、Eisenstein による簡単化²（1844年）を一部併用している。

われわれは、Dirichlet が整数論講義（1863年）において整理し直した形に沿って、Gauß の第三証明を紹介した――そこでは Eisenstein の「簡単化」は使われていない。年代的に Dirichlet は Eisenstein の工夫を知っていたはずだが、「トリッキーでかえって分かりにくい」と判断したのかもしれない。

しかし Dirichlet 版の実直な証明の後で、Eisenstein の証明法を研究してみるのも面白いだろう。

「格子点を数える幾何学的証明」の部分だけがずば抜けて有名だが、Eisenstein はむしろ別の部分で、いろいろ工夫を凝らしている。当時の私信の中で「あいにくオイラー先生の時代には、この式がまだ知られていなかったわけです」（意訳³）と、愉快そうに書いているところを見ると「会心の証明！」という満足感があったようだ。Eisenstein 自身も相互法則を重要視、計5種の証明を発表している。Gauß の「第三証明」をアレンジしたバージョンは、Eisenstein の「第三証明」でもある。

¹ Disquisitiones Arithmeticae （詳細）

² Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste
https://www.digizeitschriften.de/download/pdf/243919689_0028/log27.pdf
下記の39ページ以下に英訳がある:
https://archive.org/details/collmathpapers03caylrich

³ Wie glücklich würde sich der gute Euler geschätzt haben, diese paar Zeilen vor etwa 70 Jahren zu besitzen.（良きオイラーは、わが身を何と幸運と考えたことでしょう、これらの式を70年ほど前に知っていたら）
https://archive.org/details/abhandlungenzurg07leip （174ページ）
手紙の内容は快活だが、Eisenstein は経済的には困窮していた。健康状態も優れず、29歳で師匠 Gauß より先に亡くなってしまった。なぜか1850年ごろには「夭逝の天才数学者」が多い（Abel、Galois、Eisenstein）。

【19】　アイゼンシュタインの着想を紹介するため、【1】と同じ例題、つまり奇数の素数 p = 13 と q = 10 を取り上げる。ガウスの補題（【1】参照）では、1 から H = (p − 1)/2 までの整数、つまり x = 1, 2, 3, 4, 5, 6 に対して xq を p で割った余りを出発点とした。アイゼンシュタインは、代わりに 1 から p − 1 までの偶数 x = 2, 4, 6, 8, 10, 12 に対して、xq を p で割った余りを考える。【1】の《ア》《イ》《ウ》に対応するものは:
　　鉄ア　x = 2, 4, 6, 8, 10, 12
　　鉄イ　xq = 20, 40, 60, 80, 100, 120
　　鉄ウ　a = 7, 1, 8, 2, 9, 3
ここで例えば x = 2 なら xq = 20 となり（q = 10 なので）、それを p = 13 で割ると余り a = 7 を得る。同様に x = 4 なら xq = 40, a = 1、等々。

ガウスは、p/2 との大小の比較によって、余り a たちを「デカ余り」「チビ余り」に分け、デカ余り a を p − a に置き換える処理を行った。一方、アイゼンシュタインは、鉄ウの余りたちを「偶数か奇数か」で分類し、偶数の余りについてはそのままにして、奇数の余り a については −a で置き換える。置き換え後の「符号（fugō）付きの数」を f で表すことにしよう:
　　鉄エ　f = −7, −1, 8, 2, −9, −3　　←鉄ウの奇数にマイナスを付けただけ
ガウスの処理もそうだが、このアイゼンシュタインの処理（奇数にはマイナスを付ける）も、やぶから棒で独断的に思える。けれど、マイナスの付いた数に p を足して、合同な正の剰余に戻してやると（その結果を g としよう）…
　　鉄オ　g = 6, 12, 8, 2, 4, 10
ここで例えば f = −7 については g = −7 + p = 6 としている: −7 ≡ 6 (mod p) に注意する。f = −1 ⇒ g = 12 なども同様。f が偶数なら g はそのままだし、f が（負の）奇数なら、そこに奇数 p を足すのだから、いずれにしても g の数は必ず偶数。

結局、鉄ウの余り a たちのうち、奇数のものを p − a に置き換えている。ガウスの補題と同様の処理だ（【2】参照）。置き換えの結果、鉄オは、全体として鉄アと同じ数（2, 4, 6, 8, 10, 12）を並び替えただけ。元祖ガウス・バージョンの《タ》《ト》と同じ関係。ガウスが 1 から (p − 1)/2 までの H 個の整数を使ったのに対して、アイゼンシュタインは 2 から p − 1 までの H 個の偶数を使う。f の各数と、それらを変形した g の各数は、もちろん mod p では合同。

【20】　一般に p を奇素数、q を p の倍数以外の整数とする。

(1)　余り a が偶数なら、それがそのまま g となる。この場合、a は必ず 2 以上 p 未満の偶数。

xq が p で割り切れて、余りが a = 0 になる可能性はない。というのも、p は素数なので、xq が p で割り切れるためには x または q が p で割り切れる必要がある。ところが x は p 未満の正の偶数なので p で割り切れないし、q も p と互いに素なので p で割り切れない。

(2)　余り a が奇数なら p − a が g となる。この場合、p は奇数なので p − a は「奇数マイナス奇数」で偶数（しかも a は p で割った余りなので p より小さく、従って p − a もまた、p 未満の正の偶数）。

…どちらにしても、g の数は、どれも p 未満の正の偶数。それだけでなく、g の数の中には、2 以上 p − 1 以下の H 個の偶数が過不足なく 1 回ずつ現れる（だからこそ、「g は x を並び替えただけ」という結論に）。その理由は次の通り（f たちの各数と g たちの各数はそれぞれ合同なので、一方に重複がなければ他方にも重複がなく、過不足が起きない――そこで f たちの中に重複がないことを示す）。

今 xq = 2q, 4q, 6q, …, (p − 1)q を p で割った余りをそれぞれ a₁, a₂, a₃, … a_H として、こう書くことにする:
　　2q ≡ a₁ (mod p)　→　a₁ が偶数なら f₁ = a₁、奇数なら f₁ = −a₁
　　4q ≡ a₂ (mod p)　→　a₂ が偶数なら f₂ = a₂、奇数なら f₂ = −a₂
　　6q ≡ a₃ (mod p)　→　a₃ が偶数なら f₃ = a₃、奇数なら f₃ = −a₃
　　………
　　(p − 1)q ≡ a_H (mod p)　→　a_H が偶数なら f_H = a_H、奇数なら f_H = −a_H

これら H 個の a たちの中に、合同な数が重複して含まれることはない: 例えばもしも a₂ ≡ a₃ になったとすると、それは 4q ≡ 6q (mod p) を意味するが、q は p と互いに素なので両辺を q で割ることができて 4 ≡ 6 (mod p) …これは、ばかげている。より一般的に、どこかに「重複」があって uq ≡ vq (mod p) になったとすると、u ≡ v (mod p) だが、この u と v は偶数なので、それらの差（再び偶数）が奇数 p で割り切れるわけがなく、従って u ≡ v (mod p) は不可能。合同になる可能性がないので、ましてや等しくことはない。

すると、「a たちの中に等しい偶数の値が重複出現して、その結果、相異なる f が同じ値を持つ」心配はないし、「a たちの中に等しい奇数の値が重複出現して、相異なる f が同じ負の奇数の値を持つ」心配もない。重複が起きるとすれば、考えられるのは、ある f と別の f が「絶対値が同じで符号だけ逆」というパターンだけ。実際には、それもあり得ない。もしも相異なる2個の f ――それを f_i と f_j とする――が符号だけ逆だとすれば、a_i ≡ −a_j (mod p) となり、移項すると:
　　a_i + a_j ≡ 0 (mod p)　つまり　a_i + a_j は p の倍数
けれど a_i も a_j も「2 以上 p − 1 以下の偶数」なので、両者の和は「4 以上 2p − 2 以下」。この範囲にある p の倍数は p 自身だけなので、上の条件は
　　a_i + a_j = p
を意味する。この左辺は偶数の和で偶数、右辺は仮定により奇数（の素数）――偶数と奇数なので、等号が成り立つわけない！

【21】　結局、x の数も g の数も、順序の違いを無視すれば 2, 4, 6, …, p − 1 を過不足なく 1 個ずつ含んでいる。さらに、g の各数は f の各数と合同。よって、ガウス／ディリクレ版と同様、x の各数の積と f の各数の積は合同:
　　鉄キ　2⋅4⋅6…(p−1) ≡ f₁f₂f₂…f_H (mod p)
一方、2q ≡ a₁, 4q ≡ a₂, … なので、それらの左辺同士・右辺同士の積を考えると:
　　2q⋅4q⋅6q…(p−1)q ≡ a₁a₂a₃…a_H　つまり
　　鉄ク　2⋅4⋅6…(p−1) q^H ≡ a₁a₂a₃…a_H (mod p)

ここで a たちの一つ一つとそれに対応する各 f の関係は、もし a が偶数なら f = a で、奇数なら f = −a だった。アイゼンシュタインは、これを
　　f = (−1)^aa　　← (−1)^a が符号部分（a の正負）を表す
のように表現した。例えば a が偶数 4 なら、符号部分は (−1)⁴ = +1 なので f = a となる。また例えば a が奇数 3 なら、符号部分は (−1)³ = −1 なので f = −a となる。この考え方を使うと…
添え字がゴチャゴチャして、ちょっと読みにくいかもしれないが…
　　f₁ = (−1)^a₁a₁, f₂ = (−1)^a₂a₂, …
となって、鉄キの右辺は:
　　(−1)^a₁a₁ × (−1)^a₂a₂ × (−1)^a₃a₃ × … × (−1)^a_Ha_H
　　= (−1)^a₁(−1)^a₂(−1)^a₃…(−1)^a_H (a₁a₂a₃…a_H)
　　= (−1)^{a₁+a₂+a₃+…+a_H} (a₁a₂a₃…a_H)
簡潔に A = a₁ + a₂ + a₃ + … + a_H と置くと、上の値はこうなる:
　　(−1)^A (a₁a₂a₃…a_H)
従って、鉄キは:
　　2⋅4⋅6…(p−1) ≡ (−1)^A (a₁a₂a₃…a_H)
これを鉄クの左辺に代入すると:
　　鉄ケ　(−1)^A (a₁a₂a₃…a_H) q^H ≡ a₁a₂a₃…a_H (mod p)

a₁, a₂ などは、素数 p 未満（の偶数）なので、p と互いに素。だから、鉄ケの両辺を a₁a₂a₃…a_H で割ることが許される。それを実行すると:
　　鉄コ　(−1)^A q^H ≡ 1 (mod p)

ここで (−1)^A は、もちろん A が偶数なら = 1、奇数なら = −1。

一方、オイラーの基準によると q^H = q^(p−1)/2 は、q が mod p の平方剰余なら ≡ 1、非剰余なら ≡ −1。

鉄コによれば、(−1)^A と q^H の積は ≡ 1 なので、これら二つの値は、一方が ≡ 1 なら他方も ≡ 1、一方が ≡ −1 なら他方も ≡ −1 でなければならない。q が mod p の平方剰余か非剰余かに応じて L(q, p) を 1 ないし −1 とすると、オイラーの基準によれば L(q, p) ≡ q^H (mod p) だが、上記の観察によれば、この q^H の代わりに (−1)^A を使っても、同じ判定結果が得られる:

Eisenstein の補題　L(q, p) = (−1)^A
ここで A は 2q, 4q, 6q, …, (p−1)q をそれぞれ p で割った余りの和。

〔例1〕　L(10, 13) について【19】の鉄ウから A = 7 + 1 + 8 + 2 + 9 + 3 = 30 なので (−1)³⁰ = 1、つまり 10 は mod 13 の平方剰余（ガウスの補題【1】の例題参照）。

参考: (−1)^A = (−1)^{a₁+a₂+a₃+…+a_H} = (−1)^a₁(−1)^a₂(−1)^a₃…(−1)^a_H が = −1 になるのは、a たちの中に「値が奇数のもの」――そのとき (−1)^a = −1 となる――が「奇数個」含まれているときに限られる。偶数の a は、(−1)^a = 1 を生じるだけなので、掛け算の結果に影響しない。奇数の a が存在する場合でも、それが合計「偶数個」なら (−1)^A は (−1)^a = −1 の偶数個の積なので、= 1 となる。要するに、上の補題において、A の代わりに「A の和を構成する各項の中で、値が奇数であるもの」の個数を使っても、同じ結果が得られる。

〔例2〕　例1の A の6項の和では、奇数の項は4個: (−1)⁴ = 1 とすれば、例1の結果と一致。

【22】　以上が「アイゼンシュタインの第三証明」の導入部。それなりに面白い発想を含み、ガウスの補題も必要としないものの、特に鮮烈な印象を与えるわけでもない。むしろディリクレのやり方の方が、実直で分かりやすいとも思える。「アイゼンシュタインの第三証明」が一部だけ有名で、全体としてはあまり知られていないのも、無理からぬことだろう。

一方、この先で使われる幾何学的議論は見事なもので、現代でも多くの教科書で、アイゼンシュタインのアイデアが利用されている。

だがアイゼンシュタインの工夫は、それだけではない。原論文に含まれる巧妙な発想も、併せて紹介したい。（下に続く）

2022-08-20　アイゼンシュタインのトリック　Eisensteinによる相互法則の証明 2/2

mod p において q が平方剰余なら L(q, p) = 1、非剰余なら L(q, p) = −1 と書くことにする（p は奇素数、q は p の倍数以外）。

Eisenstein の補題（前回参照）によれば:
　　鉄サ　L(q, p) = (−1)^A
ここで A = a₁ + a₂ + a₃ + … + a_H は 2q, 4q, 6q, …, (p−1)q をそれぞれ p で割った余りの和。

a の添え字（例: a₃ の 3）は、対応する q の係数（例: 6q の 6）の半分。一番大きい添え字は (p−1) の半分: H = (p−1)/2。

【23】　「余り」の和 A の性質を調べるため、関連する「商」を考えてみよう。例えば…
　　q = 7, p = 13　⇒　2q ÷ p = 14 ÷ 13　⇒　商 1、余り 1　⇒　a₁ = 1
　　q = 7, p = 13　⇒　4q ÷ p = 28 ÷ 13　⇒　商 2、余り 2　⇒　a₂ = 2
　　q = 7, p = 13　⇒　6q ÷ p = 42 ÷ 13　⇒　商 3、余り 3　⇒　a₃ = 3
…のとき、最初の商 1 は 14/13 = 1.07… の整数部分（小数点以下の端数を切り捨てたもの）。同様に、2番目の商は 28/13 の整数部分、3番目の商は 42/13 の整数部分。Gauß はこのような端数切り捨てを [14/13] や [28/13] のように表現したが、Eisenstein は、同じ意味で E(14/13), E(28/13) などの記号を使った。E(y) とは y 以下の最大の整数というわけ。

上の割り算は、掛け算の形ではこう書ける:
　　2 × 7 = 13 × 1 + 1　つまり　2q = p E(2q/p) + a₁
　　4 × 7 = 13 × 2 + 2　つまり　4q = p E(4q/p) + a₂
　　6 × 7 = 13 × 3 + 3　つまり　6q = p E(6q/p) + a₃
　　………
　　12 × 7 = 13 × 6 + 6　つまり　(p−1)q = p E((p−1)q/p) + a_H

「つまり」の後ろの各行右側の部分は、p や q などの値と無関係に、一般的に成り立つ。これら右側の部分を縦に足し合わせると:
　　左辺の和は　2q + 4q + 6q + … + (p−1)q = [2 + 4 + 6 + … + (p−1)]q
　　同様に右辺の和は　p[E(2q/p) + E(4q/p) + E(6q/p) + … + E((p−1)q/p)] + (a₁ + a₂ + a₃ + … + a_H)
今 E(2q/p) + E(4q/p) + E(6q/p) + … + E((p−1)q/p) を M として、A = a₁ + a₂ + a₃ + … + a_H という関係を使うと、上記「右辺の和」を
　　pM + A
と簡潔に書ける。それが「左辺の和」と等しいのだから:
　　鉄シ　[2 + 4 + 6 + … + (p−1)]q = pM + A

鉄サとの関係において、重要なのは A の値: しかも A の具体的な値そのものというより A が偶数か奇数かによって、L(q, p) が 1 か −1 かが決まる。ところが、鉄シの左辺は（角かっこ内が偶数の和なので）偶数。つまり右辺の pM と A の和は偶数。従って pM が奇数なら A も奇数、pM が偶数なら A も偶数。一方が奇数、他方が偶数ということは、あり得ない。p は奇数（の素数）なので、pM の「偶・奇」は、p と無関係に M の「偶・奇」によって決まる。要するに、A の偶奇は M の偶奇と一致。

式で書けば、mod 2 において p ≡ 1 となり、鉄シは 0 ≡ 1M + A つまり −A ≡ M (mod 2)、従って―― mod 2 では 1 ≡ −1 なので―― A ≡ M (mod 2)。これは A と M の「偶・奇」が一致するという意味を持つ。

結局、鉄サにおいては、指数 A の代わりに指数 M を使っても同じ結果になる:
　　鉄ス　L(q, p) = (−1)^M
ここで M = E(2q/p) + E(4q/p) + E(6q/p) + … + E((p−1)q/p) は、2q, 4q, 6q などを p で割った商（端数切り捨て）の和。

ガウス／ディリクレ版の S と同様の「商の和」だが（《に》参照）、割と簡単にこの結論が得られた。

上記の q は p の倍数以外の任意の整数だが（p は 3 以上の素数）、ここからは q も 3 以上の素数である場合に話を限る（ただし p ≠ q）。

【24】　Eisenstein による幾何学的議論は次の通り。

座標平面の原点を O、横座標 p の点を P、縦座標 q の点を Q、座標 (p, q) の点を K として、長方形 OPKQ を考えよう。一般に、横座標・縦座標がどちらも整数である点は、格子点と呼ばれる。格子点は碁盤の目のように整然と並んでいるが、ここでは説明の便宜上、境界（長方形の辺や座標軸）の上の点を無視し、完全に長方形の内側にある点だけを「格子点」と呼ぶことにする。

この用語を使うと、上記の和 M を構成している各項は、横座標が偶数（2, 4, 6, …）の格子点のうち、対角線 OK（画像の赤い対角線）より下にあるものの個数に他ならない。というのも、赤い線 OK は傾きが q/p で、横座標が x のとき赤い線の縦座標は (q/p)x = xq/p。例えば x = 6 のとき、赤い線の高さ（縦座標）は、商の和 M の第3項 E(6q/p) の E() 内の数に等しい。E() は端数を切り捨てる意味だった: この場合、切り捨てられる端数とは、「x = 6 に対する赤い線の縦座標」と「その点の真下にある格子点 B」の間の（1 未満の）ずれに当たる。

赤い直線 y = (7/13)x の x = 6 (= H) における y 座標は 42/13 = 3.23… だが、その下には (6, 1), (6, 2), (6, 3) の3個の格子点がある（図の H の列の●）。この「3個」という整数は、もちろん 3.23… の端数を切り捨てたもの。

同様に x = 2, 4, 6, …, p−1 について考えると、M というのは「横座標が偶数の格子点のうち、対角線より下にあるもの（図の●）」の総数に他ならない。上記の具体例では、傾き 7/13 が 0.5 に近い数なので、横座標が 2 増えるごとに●が 1 個ずつ増える単純な関係になっているが、一般の場合、傾き q/p はもっと複雑な分数なので、格子点の分布はそれほど単純ではない。しかし、p と q は素数なので、x 自体が p の倍数にならない限り、(q/p)x が割り切れて整数になることはない。ここでは x は p − 1 以下の正の整数なので、(q/p)x が整数になることはなく、だから赤い対角線それ自体が格子点を含むことはない（格子点のすぐ近くをかすめることはある）。

【25】　x = 1 の列から、x = p − 1 の列まで、各列は q − 1 個の格子点を含む: q は 3 以上の素数（だから奇数）なので、この q − 1 という数は偶数。そうすると、各列において「赤い対角線より上にある格子点」の個数と、「赤い対角線より下にある格子点」の個数の和は、偶数。これは「赤い線より上にある個数・下にある個数」がどちらも偶数個か、またはどちらも奇数個であることを意味する（一方が偶数個、他方が奇数個だと、和が偶数にならない）！

〔例〕　図で x = 8 のとき、赤い線より下に4個の●、上に2個の○がある（どちらも偶数個）。x = 10 のとき、赤い線より下に5個の●、上に1個の○がある（どちらも奇数個）。x = 12 のとき、赤い線より下に6個の●、上に0個の○がある（どちらも偶数個）――もちろん「0個」も偶数個の一種。

鉄スの M で重要なのは「偶数か奇数か」だけで、それさえ分かれば、具体的な値はどうでもいい。だから「商の和」の計算では、足し算される偶数を別の偶数で置き換えても構わないし、足し算される奇数を別の奇数で置き換えても構わない。例えば、図において x = 8 のとき、対角線 OK の下にある 4 個の●の代わりに、OK より上にある 2 個の○を考えてもいいし、x = 10 のとき、OK の下にある 5 個の●の代わりに、OK より上にある 1 個の○を考えてもいい。

しかも、対角線 OK によって長方形を △OKP と △OKQ に分割した場合、これら2個の直角三角形は、図形として合同: 例えば x = 10 のとき OK より上にある格子点 U は、合同な三角形において x = 3 のとき OK の下にある格子点 u に対応する。同様に、x = 8 の格子点 V, W は、合同な三角形において x = 5 の格子点 v, w に対応。

このことから、次の巧妙なアイデアが生じる:
　　横座標が偶数の場所について、対角線 OK より下にある格子点を数える代わりに、
　　横座標が H = (p − 1)/2 以下の自然数の場所について、OK より下にある格子点を数えても、
　　「合計個数が偶数か奇数か？」は同じになる。

最初の数え方は x = 2 から p − 1 までの広い範囲において、横座標が偶数の場所だけを考え、OK より下の格子点をカウント。2番目の数え方も OK より下の格子点をカウントするのだが、今度は x = 1 から (p − 1)/2 までの約半分の範囲だけを考え、「横座標が偶数の場所だけ」という飛び飛びの数え方をやめて、横座標が奇数でも偶数でも普通にカウントする。…これら2通りの数え方では、カウントされる合計個数は異なる。けれど「個数が偶数か奇数か？」は一致するので、(−1) の累乗の指数として使うのなら、どちらでも同じ結果になる（最終的には偶数乗か奇数乗か？だけが問題なので）。

このように（結果の偶・奇を保ったまま）変形した和は、結局、ガウス／ディリクレの証明法における「商の和」 S と全く同じもの:
　　S = E(1q/p) + E(2q/p) + E(3q/p) + … + E(Hq/p)　　（《た》参照）

少々トリッキーな式変形だが、意味が分かると「なるほど、うまいことを考えたな」と…。結論はガウス／ディリクレの「商の和」と同じでも、それを導く方法が面白い。

【26】　かくして Eisenstein の補題 L(q, p) = (−1)^A ――すなわち鉄サ――について、右辺は、2q/p, 4q/p, …, (p−1)q/p の商の和 M を使った (−1)^M と一致（鉄ス）。それはさらに q/p, 2q/p, …, Hq/p の商の和 S ‌を使って表現される:
　　鉄セ　L(q, p) = (−1)^S　　（《た》と同じ）

この S は、幾何学的には、x = 1 から H = (p − 1)/2 までの範囲において OK の下にある格子点の個数に等しい！　ガウス／ディリクレ版の S の計算（実直だが面倒くさい）の、明快な可視化となっている。

さて、p と q の役割を入れ替え、今度は L(q, p) ではなく L(p, q) を求めてみよう。通常と逆に「縦を x-軸、横を y-軸」と思えば、鉄スと全く同様:
　　L(p, q) = (−1)^N
　　ここで N = E(2p/q) + E(4p/q) + … + E((q−1)p/q)
このとき、【25】と同様の巧妙な式変形により、この指数 N を（偶・奇を保ったまま）次の指数 T に置き換えられる:
　　鉄ソ　L(p, q) = (−1)^T
　　ここで T = E(p/q) + E(2p/q) + … + E(Ip/q)　そして　I = (q − 1)/2

〔注〕　I は文字の「アイ」。数字の 1 じゃない。p と q の役割を入れ替えるということは、赤い線を x = (q/p)y ではなく y = (p/q)x と解釈すること…と考えてもいい（前者の両辺を p/q 倍すれば後者になる）。

鉄ソは、ガウス／ディリクレ版の《ち》に当たる。

幾何学的には、S は横座標 1 から H までの「OK の下の格子点の総数」。T は、OQ を「横軸」と見た場合の「横」座標 1 から I までの「OK の下の格子点の総数」――あるいは、OQ を普通に「横軸」と見た場合、「縦」座標 1 から I までの「OK の左の格子点の総数」。上の図で言えば、★☆の総数に当たる。

図から明らかなように、S と T の和とは、「横に H 個、縦に I 個、並んでいる格子点の総数」で、合計 HI 個（そのうち赤い線 OK より下にある格子点の数が S、上にある格子点の数が T）。すなわち S + T = HI。これはガウス／ディリクレ版【16】の《ぬ》だが、形式的な式変形ではなく「そうなって当たり前！」ということが一目で分かる。H = (p − 1)/2, I = (q − 1)/2 という定義を思い出すと:
　　L(q, p) = (−1)^S　　←鉄セ
　　L(p, q) = (−1)^T　　←鉄ソ
　　L(p, q) L(q, p) = (−1)^T (−1)^S = (−1)^S+T = (−1)^HI = (−1)^{(p−1)(q−1)/4}

平方剰余の相互法則（【17】の《ね》）が再び証明された！

【27】　アイゼンシュタインの第三証明は、本質的にはガウスの第三証明のアレンジにすぎない。けれど、計算の幾何学的解釈により、ガウス版より式の意味が分かりやすい。特に S + T = HI の可視化（【26】）は秀逸。

アイゼンシュタインの工夫は、それだけではない。ガウスの 1, 2, 3, …, (p−1)/2 の代わりに、偶数 2, 4, 6, …, p−1 を出発点とすることにより、ガウスの補題を経由せずに手際よく鉄スを導き、【24】のアイデアにより、鉄スが、偶・奇に関して鉄セと同じであることを示す。ちょっとトリッキーだが、面白い。ディリクレの証明と違い q < p という制限も不要。

半面、天下り的にアイゼンシュタイン版の証明を示されても、モチベーション的疑問が残るかもしれない。S + T = HI などは確かに「簡単な計算」だが、「そもそもなぜそういうことを考えるのか」という根本が、必ずしも明らかではない――「結果的にこれで相互法則を証明できるのだから、それでいいでしょう」という説明では、だまされたような気持ちにもなる。

ガウス／ディリクレがやったように「端数を切り捨てた商を一つ一つ足していく」という実直な操作を体験してみた後でこそ、アイゼンシュタインの工夫の真意、その素晴らしさを実感できるのかもしれない。

2022-09-06　アイゼンシュタインの証明の現代化　目で見る相互法則

ガウスの第三証明（ディリクレ版）、それを簡単化したアイゼンシュタインの幾何学的証明については、いずれも既に200年前のオリジナル版を紹介したが、現代的にはそれがどう整理されるか。

【28】　p = 11, q = 7 を例にすると、H = (p−1)/2 = 5, I = (q−1)/2 = 3。横 5 個、縦 3 個の長方形状に並んだ格子点（図の ● と ○）が、合計 5 × 3 = 15 個…という当たり前のことに、問題は帰着されるのだった。

赤線の下の ● と赤線の上の ○ が対称ではないことに注目（後者の方が1個多い）！

このうち赤線 y = (7/11)x の下にある格子点 ● の個数を考えると、y が縦座標なので:
　　x = 1 のとき y = (7/11) × 1 = 7/11　→ 0 以上 1 未満　→　端数を切り捨てると 0 個
　　x = 2 のとき y = (7/11) × 2 = 14/11　→ 1 以上 2 未満　→　端数を切り捨てると 1 個
　　x = 3 のとき y = (7/11) × 3 = 21/11　→ 1 以上 2 未満　→　端数を切り捨てると 1 個
　　x = 4 のとき y = (7/11) × 4 = 28/11　→ 2 以上 3 未満　→　端数を切り捨てると 2 個
　　x = 5 のとき y = (7/11) × 5 = 35/11　→ 3 以上 4 未満　→　端数を切り捨てると 3 個
　　だから計 0 + 1 + 1 + 2 + 3 = 7 個

赤線 y = (7/11)x は、両辺を 11/7 倍すれば x = (11/7)y と同じ。だから赤線の上（赤線の左）にある格子点 ○ の個数を考えると、x が横座標なので:
　　y = 1 のとき x = (11/7) × 1 = 11/7　→ 1 以上 2 未満　→　端数を切り捨てると 1 個
　　y = 2 のとき x = (11/7) × 2 = 22/7　→ 2 以上 3 未満　→　端数を切り捨てると 2 個
　　y = 3 のとき x = (11/7) × 3 = 33/7　→ 4 以上 5 未満　→　端数を切り捨てると 4 個
　　だから計 1 + 2 + 4 = 8 個

7 個と 8 個 の和は 15 個。

【29】　より一般的に p, q を 3 以上の相異なる素数として、H = (p−1)/2 と I = (q−1)/2 の積が、赤線の下の格子点と、赤線の上の格子点の合計数に等しいことは、一目瞭然だろう。端数切り捨てを E() で表すと、赤線の下の格子点の数は:
　　S = E(1q/p) + E(2q/p) + E(3q/p) + … + E(Hq/p)
赤線の上の格子点の数は:
　　T = E(1p/q) + E(2p/q) + E(3p/q) + … + E(Ip/q)
そして、上記のように、格子点の数の総数は:
　　S + T = HI = [(p−1)/2][(q−1)/2] = (p−1)(q−1)/4　　‥‥①

ところが、ガウスの補題からの発展として（【11】【12】）――この部分は、あまり見通しが良くないのだが――
　　L(q, p) = (−1)^S, L(p, q) = (−1)^T　　‥‥②
となる。アイゼンシュタインのトリックによっても（【26】）、同じ結論が得られた（依然トリッキーだが、比較的簡潔）。

②と①を組み合わせると、次のように、直ちに平方剰余の相互法則が得られる:
　　L(p, q) L(q, p) = (−1)^T × (−1)^S = (−1)^S+T = (−1)^HI = (−1)^{(p−1)(q−1)/4}

結局、「赤線の上と下にある格子点の合計数＝横 H 個、縦 I 個の長方形状に並んでる＝HI 個」ということと、性質②から、第三証明が得られる。アイゼンシュタインのトリッキーな証明も、これでずいぶん自然な形になる。相互法則そのものについては、もはや疑いの余地はなく、後は「証明をどれだけ見通しよく、すっきりさせられるか」という気分の問題、そして厳密性の問題だろう。

第一に、①について、「作図から一目瞭然」というのは、心理的な納得のためには非常に良いことだが…。「見れば分かる」というのは直観的な話で、必ずしも論理的ではない。作図に頼らない最初の証明の方が、実直だろう。

第二に、②の導出については、ガウスの方法もアイゼンシュタインの方法も多少天下り的。論理的な不備はないものの、依然として「すっきり透明」とは言い難い。もう一歩、踏み込んで考える余地もありそうだ。

全体として言えば、われわれは第三証明について、ずいぶん理解を深めることができた。ガウス／ディリクレの源流から、アイゼンシュタインの幾何学的工夫を経て、現代的に整理された形へ…。今どきの教科書を読んでもピンとこないニュアンスや歴史的背景が実感できたのは、大きな収穫だった。

2022-08-25　第二補充法則の散歩道　数論のスローライフ

素数 p について、x² ≡ 2 (mod p) に解があれば、2 は平方剰余と呼ばれ、解がなければ 2 は平方非剰余（略して非剰余）と呼ばれる。例えば p = 17 の場合、x² ≡ 2 (mod 17) には解があるので（x = 6。そのとき x² = 36 ≡ 2 (mod 17) となる）、mod 17 において 2 は平方剰余。

3 以上の素数 p は、8 で割ると、余りが奇数 1, 3, 5, 7 のどれかになる（もしも余りが偶数なら p は「8の倍数、プラス、余りの偶数」イコール「偶数」なので、2 で割り切れてしまい、「3 以上の素数」という条件に当てはまらない）。第二補充法則は、p が「8 で割って余りが 1 か 7 の素数」なら（そしてそのときに限って）、2 が mod p において平方剰余になる…という内容。シンプルだけど奥が深い。上の例では、p = 17 が「8 で割って余りが 1 か 7」なので、2 が平方剰余となった！

第二補充法則については、既に場合分けして直接的に証明したし、ガウスの補題経由（【10】）でも一挙に証明した。忙しい（？）現代人としては「もう済んだ話。次の話題に行きましょう」という気持ちもあるかもしれない。でも、第二補充法則の周辺には、小粒でも面白い話題がいろいろある。のんびり散策を楽しむのも悪くあるまい。

現代はネットやら何やらが発達して「便利になった・効率的になった」はずなのに、なぜ現代人は「忙しい」のだろう。何か変だ。薄っぺらな「インスタントな喜び」を急いで追求しても、そこに深い満足感などあろうはずもなく、ますます満たされない気持ちになるのかもしれない…。

今回は、Gauß DA 第114節の議論を紹介する。その内容は、p が「8 で割って 1 余る素数」なら、2 も −2 も平方剰余…というもの。

われわれは天才ガウスが考えた通りの道をたどる――はっきりと目には見えなくても、そこから何かが得られるだろう。200年前の議論なので、現代から見れば、多少整理・改善できる点もあるかもしれない。花びらのような印 を付けて、別の観点についても記しておく。

1.　p を8k+1型の素数、g を mod p における一つの原始根としよう。原始根は「p−1 乗して初めて ≡ 1 (mod p) になる数」: 1乗、2乗、3乗、…、p−2 乗では ≡ 1 にならない。この場合 p = 8k+1 なので p−1 = 8k。つまり 8k 乗して初めて ≡ 1 になる:
　　g^8k ≡ 1 (mod p)
今 g^4k を w とすると、上の式によれば g^8k = (g^4k)² = w² なので、w は2乗すると ≡ 1 になる数、つまり w ≡ 1 or −1。けれど、もしも w ≡ 1 つまり g^4k ≡ 1 なら「g は 8k 乗して初めて ≡ 1 になる」という原始根の性質に反し、不合理（4k 乗の段階で既に ≡ 1 になってしまう）。だから、他方の選択肢 w ≡ −1 が正しい:
　　g^4k = w ≡ −1　つまり　g^4k ≡ −1 (mod p)　　‥‥①

Gauß のちょっとした「妙手」は、①の両辺に 2g^2k を足す…というもの:
　　g^4k + 2g^2k ≡ −1 + 2g^2k　右辺の −1 を移項すると
　　g^4k + 2g^2k + 1 ≡ 2g^2k　つまり
　　(g^2k)² + 2⋅(g^2k)⋅1 + 1² ≡ 2⋅(g^2k)　　‥‥②
　　従って　(g^2k + 1)² ≡ 2⋅(g^k)² (mod p)　　‥‥③

〔解説〕　g^2k を一つの数 A だと思うと、②の左辺は A² + 2⋅A⋅1 + 1² なので、
　　(A + B)² = A² + 2AB + B²
という公式を適用できる（B = 1）。

③右辺の 2⋅(g^k)² は mod p において平方剰余: x² ≡ この右辺 (mod p) は解を持つ――見たまんま、③左辺の x = g^2k + 1 が一つの解。

③右辺のうち (g^k)² の部分も、もちろん平方剰余: x² ≡ (g^k)² は解を持つ――これまた見たまんま x = g^k が一つの解。

ここで思い出そう（【11】）。平方剰余と平方剰余の積は、再び平方剰余。一方、平方剰余と非剰余の積は、非剰余。すると、③の右辺について…
　　「2」　と　(g^k)²（←平方剰余）の積が　③の右辺（←平方剰余）
…なのだから、必然的に「2」も平方剰余になる！

結論として、8k+1型の素数 p を mod とするとき、2 は平方剰余。

実は、これらの議論では「原始根」の概念は必要ない。フェルマーの小定理から z^p−1 ≡ 1 (mod p) は p−1 種類の解 z ≡ 1, 2, 3, …, p−1 を持つ。p = 8k+1 つまり p = 8k なら、
　　z^8k ≡ 1　つまり　z^8k − 1 = (z^4k + 1)(z^4k − 1) ≡ 0
は 8k 個の解を持ち、従って、z^4k + 1 ≡ 0 と z^4k − 1 ≡ 0 は、それぞれ 4k 個ずつの解を持つ。z^4k + 1 ≡ 0 の解の一つを z ≡ g とすると、g^4k + 1 ≡ 0 つまり g^4k ≡ −1。後は①以降と同じ。ここで重要なのは、z^4k − 1 ≡ 0 が（従って z^4k ≡ −1 が）解を持つ…という事実であり、その解が原始根であるかどうかは、議論の本質とは関係ない（g が原始根というのは、必要以上に強い条件）。Dirichlet も、原始根を使わずに同じ結論を導いている（上述の方法より若干複雑だが、ほぼ同内容）。

2.　この判定は、「第二補充法則の簡単な証明・春」（Dirichlet の整数論講義 §41 に基づく）の【15】と同じ。③は、【15】の『も』
　　(y² + 1)² ≡ 2y² (mod p)
と同じ（y が上記 g^k に当たる）。Dirichlet は代数的な恒等式から同じ結論を導いているが、その鍵となるのは、
　　p が8k+1型の素数（愛称: 春素数）なら　y⁴ + 1 ≡ 0 (mod p)　が（4個の）解を持つ
ということだった（【14】参照）。この式の + 1 を右辺に移項すると:
　　p が春素数なら　y⁴ ≡ −1 (mod p)　が解を持つ…
　　…つまり　−1 の4乗根（4乗すると ≡ −1 になる数）が存在。

①によれば g^4k = (g^k)⁴ ≡ −1 なのだから、4乗すると ≡ −1 になる数 y ――つまり−1 の4乗根 y ――とは g^k に他ならない（g は任意に選んだ原始根）。このことを【17】の p = 17 の例で確認してみる。17 = 8 × 2 + 1 なので、この場合 k = 2（「素数 17 は8k+1型」と言うとき、具体的には k = 2 になっている）。17 の原始根は
　　g = ±3, ±5, ±6, ±7
の8個あるが（【2】の表参照）、−1 の4乗根 g^k は、この場合 g² に当たる――2乗されるので g の ± の違いはどうでもいい:
　　g² = 9, 25, 36, 49 ≡ 9, 8, 2, 15 (mod 17)

y⁴ ≡ −1 つまり y⁴ + 1 ≡ 0 の解が、4種類、見つかった。素数を mod とする世界は整域なので、4次方程式の解は4個以下。つまり以上で全種類。

mod が 8k+1 のとき、原始根 g は「4k 乗すると ≡ −1 になる」という性質を持つので（①参照）、y ≡ g^k を4乗すると ≡ −1 になるのは当たり前だろう:
　　原始根 g　　←　4k 乗すると ≡ −1　　言い換えれば (p−1)/2 乗すると ≡ −1
　　−1 の4乗根 y ≡ g^k　　←　4 乗すると ≡ −1

〔参考〕　より一般的に p を 3 以上の任意の素数とするとき、もし g が mod p の原始根なら、g を (p−1)/2 乗すると ≡ −1 になる（上記はそのうち p = 8k+1, (p−1)/2 = 4k の場合）。この命題の逆は成り立たない。つまり「g が原始根」なら g^(p−1)/2 ≡ −1 (mod p) と断言できるが、g^(p−1)/2 ≡ −1 (mod p) が成り立つからといって、それだけでは「g が原始根」とは言い切れない（説明）。

前述のように「g が原始根」というのは、この場合、過剰な条件である。z^4k + 1 ≡ 0 の解の一つを z ≡ g とするなら、その g は（原始根であろうがなかろうが）「4k 乗すると ≡ −1 になる」という性質を持ち、g^k は「4 乗すると ≡ −1 になる」という性質を持つ――われわれの目的のためにはそれで十分であり、この証明だけに限って言えば、ガウスは必要十分の線を見切らず、必要以上に強い制約を課している。けれど、もっと広い範囲で言えば、原始根や指数の理論は非常に重要・便利なものであり、ガウスがそれを使って考えているのは自然なことだろう。

3.　①の g^4k ≡ −1 の両辺に 2g^2k を足す代わりに、両辺から 2g^2k を引き算しても、同様の議論が成り立つ:
　　g^4k − 2g^2k ≡ −1 − 2g^2k
　　g^4k − 2g^2k + 1 ≡ −2g^2k　　ここで (g^2k) を一つの数と見ると…
　　(g^2k)² − 2⋅1⋅(g^2k) + 1² ≡ −2⋅(g^2k)
　　(g^2k − 1)² ≡ −2⋅(g^k)² (mod p)　　‥‥④
④の左辺は平方の形、右辺の第2因子も平方の形なので、これが成り立つからには −2 も平方剰余！

結局、mod p の p が奇素数の場合、p が8k+1型（春素数）のときには、2 も −2 も平方剰余。この性質を持つ奇素数 p は、春素数に限られる。だって、証明済みの第二補充法則によれば、2 が平方剰余になるのは p = 8k±1 の場合（春・冬）だけだし、さらに「簡単な証明・春」の【16】で確かめたように、−2 が平方剰余になるのは p = 8k+1 or 8k+3 の場合（春・夏）だけ。どっちもオーケーなのは、春素数の場合だけ♪

「だから何？」「それが何の役に立つの？」と忙しい現代人（笑）は思うかもしれないけど…。何の役にも立たない数の不思議だからこそ、優雅ですてきなんじゃない…。ロマンチックより、パセリチックより、メロンチックに、へんちくりんな魔法いっぱい覚えたいよ！

4.　mod 8k+1 における「原始根」「−1 の4乗根」「±2 が平方剰余であること」の関係をより深く理解するため、具体例として p = 41 の場合を検討してみよう（【17】参照）。

まず mod 41 の世界の原始根だが…。40乗して初めて ≡ 1 になる数 g を探したい。g = 2 は条件を満たすか？　2¹⁰ = 1024 は 25 × 41 (= 25 × 40 + 1) = 1025 より 1 小さい。これは 2¹⁰ ≡ −1 (mod 41) を意味し、その両辺を平方すると 2²⁰ ≡ 1 なので、条件を満たさない（20乗でもう ≡ 1 になってしまう）。ついでに言うと、2² = 4 は半分の10乗で ≡ 1 になってしまい（4¹⁰ = (2²)¹⁰ = 2²⁰ ≡ 1）、ますます条件を満たさない。

では g = 3 ならどうか？　3⁴ = 81 は 41 の倍数 82 より 1 小さいので、3⁴ ≡ −1 従って 3⁸ ≡ 1 (mod 41)。これまた40乗より、はるか手前でもう ≡ 1 になってしまう。

今度は g = 5 を考えてみると…。細かい計算は省くが、5²⁰ ≡ 1 (mod 41) となって、これも位数が40より小さい。存在することは分かってるといっても、なかなか見つからないもんだな、原始根ってのは（笑）。とはいえ、要するに g = 1 から 40 までの中で位数が 40 のもの（40乗して初めて ≡ 1 mod 41 になる数）を見つければいいのだから、やれば機械的にでき、結論としては次の16種が原始根となる:
　　g ≡ 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 (mod 41)

これらの各数は g²⁰ ≡ −1 を満たし（指数の 20 は (p−1)/2 だが、p = 8k+1 なので、4k に当たる）、従って、指数を4分の1にした y ≡ g⁵ は y⁴ ≡ −1 を満たす（−1 の4乗根。g の指数 5 は k に当たる）。それぞれの g に対して実際に計算すると、順に:
　　y ≡ g^k ≡ 27, 38, 3, 3, 38, 14, 27, 27, 14, 14, 27, 3, 38, 38, 3, 14
重複している数を省いて、整理すると:
　　y ≡ g^k ≡ 3, 14, 27, 38 ≡ ±3, ±14　　‥‥⑤
数の個数が減ってたった4個になってしまったが、整域の4次方程式 y⁴ ≡ −1 の解は最大4個なので、この個数は妥当！

〔検算〕　(±3)⁴ = 81 ≡ −1 (mod 41) は確かに −1 の4乗根。もう一方の ±14 についても、(±14)⁴ = 38416 ≡ −1 なのだが、これはちょっと計算が面倒。そこで4乗する代わりに、2回2乗すると…。(±14)² = 196 = 41 × 5 − 9 ≡ −9、そして (−9)² = 81 = 41 × 2 − 1 ≡ −1。

「観察」　⑤の数について、3 × 14 = 42 ≡ 1 (mod 41) という関係にご注目。mod 41 においては 3 と 14 は互いに逆数（積が 1）なのだ！　つまり 3⁻¹ ≡ 14 であり、14⁻¹ ≡ 3 である。⑤の数の中から、例えば g^k ≡ 3 を選ぶと、3⁻¹ つまり (g^k)⁻¹ ≡ g^−k は ≡ 14 となる。

もちろん (−3) × (−14) = 42 ≡ 1 でもあるから、同様に (−3)⁻¹ ≡ −14 なども成り立つ。

上記の例では、必要以上に強い条件「g は原始根」の弊害が生じている。この場合、苦労して原始根を探す必要はなく、もっと緩く「4k 乗すると ≡ −1 になる任意の数」を g として構わない。例えば g = 3 は mod 41 の原始根ではないが、3²⁰ ≡ −1 (mod 41) なので g = 3 を選択しても、同じ結果が得られる。

5.　③によれば:
　　(g^2k + 1)² ≡ 2⋅(g^k)² (mod p)
両辺を (g^k)² で割ると:
　　(g^2k + 1)² / (g^k)² ≡ 2
左辺の「分子の2乗」と「分母の2乗」を「分数全体の2乗」にまとめると:
　　[(g^2k + 1) / (g^k)]² ≡ 2
従って、上記左辺の角かっこ内、つまり下記の数の2乗が ≡ 2 になる:
　　(g^2k + 1) / (g^k)　つまり　(g^2k + 1)(g^−k)　　‥‥⑥

〔補足〕　g は p−1 乗（つまり 8k 乗）して初めて ≡ 1 になる数なので、2k 乗した時点では ≢ 1 であり、p と互いに素。従って、上記の「両辺を (g^k)² で割る」という計算をしても、mod は変化しない。⑥の「つまり」では、g^k で割る代わりに、逆数の g^−k を掛け算した（意味に違いはない）。

⑥において、例えば g^k ≡ 3 (mod 41) を選び、4. の「観察」を使うと:
　　g^2k + 1 = (g^k)² + 1 ≡ 3² + 1 = 10
　　g^−k ≡ 14　それらの積は…
　　(g^2k + 1)(g^−k) ≡ 10 × 14 = 140 ≡ 17 (mod 41)

2 が平方剰余ということだけでなく、具体的に「17 を平方すると ≡ 2 になる」ことが判明した！

〔検算〕　17² = 289 = 7 × 41 + 2 ≡ 2 (mod 41)

平方される数については、もちろん符号はプラスでもマイナスでも結果に影響はなく、(−17)² ≡ 2 つまり 24² ≡ 2 (mod 41) も成り立つ。x² ≡ 2 は2次方程式なので、解は最大2個。従って x ≡ ±17 (mod 41) 以外の種類の解はない。

同様に④の (g^2k − 1)² ≡ −2⋅(g^k)² (mod p) を変形すると、下記の数の2乗が ≡ −2 になる:
　　(g^2k − 1) / (g^k)　つまり　(g^2k − 1)(g^−k)　　‥‥⑦

再び g^k ≡ 3 で試すと、g^2k − 1 = 8 だから⑦の値は 8 × 14 ＝ 112 ≡ 30 ≡ −11 (mod 41)。実際 (−11)² = 121 は 41 の倍数より 2 小さいので、≡ −2 (mod 41)。もちろん −11 だけでなく +11 も解となる（それ以外の種類の解はない）。

6.　−1 の4乗根である y ≡ g^k には、4種の選択肢がある。mod 41 の例では y ≡ ±3 or ±14 だが、マイナスの符号を選択した場合には…
　　►　「観察」から分かるように、逆数 y⁻¹ ≡ g^−k の符号もマイナスになるが、
　　►　⑥や⑦の値の g^2k の部分は、偶数乗なので、g の符号がプラスでもマイナスでも結果は同じ
…なので、全体としては、⑥ないし⑦の計算結果において、値は同じで符号だけ逆になる（mod p において）。

例えば g^k ≡ 3 に対応して⑥の値 17 が得られるのだから、g^k ≡ −3 に対応して⑥の値 −17 が得られる。同様に g^k ≡ 14 を選んだ場合と g^k ≡ −14 を選んだ場合とでは、⑥の値の符号だけが逆になる。

一方、y ≡ 3 と y ≡ 14 のように符号だけの違いではない2種類の選択は、結果にどう影響するのだろうか？　試しに y ≡ g^k の値として実際に⑥に 14 を入れてみると…。何のことはない、最初と同じ結果になる:
　　g^2k + 1 ≡ 33, g^−k ≡ 3　それらの積は　(g^2k + 1)(g^−k) ≡ 99 ≡ 17 (mod 41)
2次方程式の解は最大2種類なので、新しい解が見つからないこと自体は（抽象的な事実としては）当然だが、入力の y が違うのに、具体的にどういう仕組みで「どちらでも同じ結果」になるのだろうか？

以下⑥について、この点を検討する（⑦についても全く同様）。

4. の「観察」を思い出そう。2種類の値 y ≡ 3 or 14 は mod 41 において、互いに逆数になっているのだった。これら2種類（符号の違いだけではない）の y を a と b とすると、a⁻¹ ≡ b, b⁻¹ ≡ a となる。ところが、⑥によると「平方すると ≡ 2 になる数」は…
　　(g^2k + 1)(g^−k)　つまり　(y² + 1)(y⁻¹) = y²y⁻¹ + y⁻¹
　　要するに　y + y⁻¹　　‥‥⑧
…なのだから、この最後の式に y ≡ a を入れれば結果は a + a⁻¹ ≡ a + b になるし、y ≡ b を入れれば結果は b + b⁻¹ ≡ b + a になる。同じ値になるのは、当たり前☆

一般に、8k+1型の素数 p を法とすると −1 の4乗根は4種類あって ±a, ±b の形を持つ（詳細は次回に）。複号 ± の部分は、大した問題ではない: ある数 y を4乗したものと (−y) を4乗したものは等しいので、一方が ≡ −1 なら、他方もそうなる。問題は「単なる符号の違いだけではない a と b の存在」…。今 g を一つの原始根として a ≡ g^k としよう。両辺を4乗した a⁴ ≡ g^4k が ≡ −1 (mod p) であることは既に分かっているので、a は−1 の4乗根の一つ。a⁴ ≡ g^4k ≡ −1 をさらに2乗すると、g^8k ≡ 1 （この結論はフェルマーの小定理からも明らか）。これらのことから、次が成り立つ:
　　g^24k = (g^8k)³ ≡ (1)³ ≡ 1
　　従って　g^28k = (g^24k)(g^4k) ≡ (1)(−1) ≡ −1
だから g^7k を4乗しても ≡ −1 になる:
　　(g^7k)⁴ = g^28k ≡ −1
つまり g^7k も −1 の4乗根の一つだが（この数を b ≡ g^7k としよう）、原始根の性質上、b は a ≡ g^k とは種類が異なる（原始根の1乗、2乗、3乗、…、p−1 乗は、どれも不合同）。注目すべきこととして、
　　ab = (g^k)(g^7k) = g^8k ≡ 1
が成り立つ: a と b は互いに逆数。さらに b/a ≡ g^7k/g^k ≡ g^6k は g^4k ≡ −1 と不合同。つまり b/a ≢ −1。その両辺を a 倍すると b ≢ −a。

結論として、上記のように定めた a と b は −1 の「別の種類の」4乗根で（符号が違うだけの関係ではない）、しかも互いに逆数。このことから、mod 41 の例と同様、mod が8k+1型のどんな素数であろうと、⑧の値は、y = a を入れても y = b を入れても同じ a + b になる！

〔補足〕　−a と −b も互いに逆数（なぜなら積 ≡ ab ≡ 1）: 従って y = −a または y = −b も y + y⁻¹ ≡ (−a) + (−b) を満たし、この和は、上記で求めた「2の平方根」 a+b の符号を逆にしたもの −(a+b) と合同になる（もちろん平方すれば、どちらも ≡ 2 になる）。結局、±a, ±b のどれを⑧の y としても構わない: つまり、4種類ある4乗根のどれを a としても構わない（その選択に対応して b ≡ a⁻¹ は決まる）。上記の議論は、下記で a = g^k とした場合に当たる。

mod が8k+1型の素数のとき、「4k 乗すると ≡ −1 になる任意の数」（原始根とは限らない）を g とすると、そこから −1 の4乗根を全種類、構成できる: g^k, g^3k, g^5k, g^7k。最初の数 g^k の4乗が = g^4k ≡ −1 になるのは明白。2番目の数については (g^3k)⁴ = g^12k = g^8kg^4k ≡ g^4k（なぜなら小定理により g^8k ≡ 1）、3番目の数についても (g^5k)⁴ = g^20k = (g^8k)²g^4k ≡ g^4k、4番目の数についても (g^7k)⁴ = g^28k = (g^8k)³g^4k ≡ g^4k。これら4種類はどれも不合同（下記 8. 参照）。ちなみに g^k ≡ a, g^2k ≡ j と置くと、これら4種類の解は順に a, aj, aj², aj³ と合同、つまり順に a, aj, −a, −aj と合同。1個目と4個目、2個目と3個目が互いに逆数。実際、a² ≡ g^2k ≡ j そして j² ≡ g^4k ≡ −1 なので、(a)(−aj) と (aj)(−a) はどちらも ≡ −(a²)j ≡ −(j)j ≡ −(−1) ≡ 1。

7.　興味深いこととして、上記の現象は、複素数の世界における −1 の4乗根の振る舞いと似ている。

〔注〕　この節の内容は、ガウスのDAとは直接関係ない。

複素数の世界で −1 の平方根は、もちろん ±i の2種類。そのまた平方根（−1 から見ると4乗根）は ±√i と ±√−i の合計4種類だが、複素平面上で言えば、「偏角 ±45° と ±135°（実軸の向きと虚軸の向きのちょうど中間に当たる斜めの向き）で絶対値 1 の点」に当たる:
　　i の平方根（主値）　α = (√2 + i√2)/2 = (1 + i)/√2
　　i のもう一つの平方根　−α = (−√2 − i√2)/2 = −(1 + i)/√2
　　−i の平方根（主値）　β = (√2 − i√2)/2 = (1 − i)/√2
　　−i のもう一つの平方根　−β = (−√2 + i√2)/2 = −(1 − i)/√2

〔補足〕　それぞれの式で、1個目の等号の後ろの分数が普通の書き方。2個目の等号の後ろは、分子・分母を √2 で割った形（以下の話では、こっちの形の方が便利）。上記の4個（どうやって求めるの？）が −1 の4乗根であることは、簡単に直接確認できる。例えば…
α² = (√2 + i√2)²/2² = (2 + 2⋅√2⋅i√2 + 2i²)/4 = (2 + 4i − 2)/4 = i
従って　α⁴ = (α²)² = i² = −1
β² = (√2 − i√2)²/2² = (2 − 2⋅√2⋅i√2 + 2i²)/4 = (2 − 4i − 2)/4 = −i
従って　β⁴ = (β²)² = (−i)² = −1

さて、⑧によれば、p = 8k+1 のとき、mod p での 2 の平方根は:
　　(y² + 1)y⁻¹

実験として、mod p という前提をあえて無視、上の式の y に「複素数の世界での −1 の4乗根」を入れてみよう:
　　y = α ⇒ (y² + 1)y⁻¹ = (1 + i) √2/(1 + i) = √2
　　y = β ⇒ (y² + 1)y⁻¹ = (1 − i) √2/(1 − i) = √2

これはびっくり！　複素数の世界でも、⑧は 2 の平方根（平方すると 2 になる数）を表している。しかも y に α, β のどっちを代入しても、結果は同じ。上述の mod 8k+1 の場合と同様の結果になる背景として、α, β もまた、互いに逆数:
　　αβ = (1 + i)/√2 × (1 − i)/√2 = (1² − i²)/2 = 2/2 = 1
　　（計算するまでもなく、偏角が ±45° でどちらも絶対値 1）
同様に −α, −β も互いに逆数。

mod 8k+1 の世界でも、複素数の世界でも、2 の平方根が同じ形 y + y⁻¹ で表現できるのは、面白い。ここで y は、それぞれの世界における −1 の4乗根。その具体的な値は、複素数の世界では上記 ±α, ±β だが、結果の符号に影響するのは α, β の符号であり、α, β のどちらを使うかは結果に影響しない。一方、mod 41 の例では −1 の4乗根は ±3, ±14 だったが、この場合も、結果の符号に影響するのは入力の符号の選択であり、3 と 14 のどちらを使うかは結果に影響しないのだった。

どうやら複素数の世界での −1 の原始4乗根と、mod 8k+1 の世界での −1 の4乗根の間には、構造的な類似性がありそうだ…。

それはさておき、今回は「8k+1型の素数が mod のとき ±2 の両方が平方剰余となる」ということについて、かなり掘り下げて考えることができた。このメモはDAの第114節をベースにしているが、ガウスは次の115節でも同じ問題を別の角度から考察している。（続く）

（付記）

i の平方根（−1 の4乗根）　本筋と関係ないが参考までに…。2個の複素数 u, v を極座標で表した場合、積 uv の絶対値は u の絶対値と v の絶対値の積になり、uv の偏角は u の偏角と v の偏角の和になる。i は絶対値 1、偏角 90° なので、その平方根は「2乗すると、そうなる数」――2乗するというのは「等しい数 u = v の積 uv を求めること」なので、u = v の絶対値が 1、偏角が 45° なら、今の規則から、uv の絶対値は 1、偏角は 90° となって、要するに「2乗すると i になる」。…従って、問題は、複素平面（横軸が実部、縦軸が虚部を表す）において、原点からの距離が 1 で（＝単位円の円周上にあって）、偏角が 45° の点の座標を求めることに帰着される。つまり求めたい値は、
　　実部が cos 45°　虚部が sin 45°　（説明）
ということに…。ただし i には、もう一つの平方根があって、偏角が −135°（あるいは同じことだが 225°）でもいい: (−135°) + (−135°) = −270° は 90° と同じ向きなので…。この偏角に対する値は、単に最初の値の符号を逆にしただけ: u² が i なら (−u)² = (−1)²u² = u² も同じ値なので、i の平方根は u でも −u でもいいわけである。i の二つの平方根も、同様の考え方で求められる。（戻る）

(p−1)/2 乗が ≡ −1 になる場合について　p を 3 以上の素数、b を p の倍数以外の整数とするとき、フェルマーの小定理から b^p−1 ≡ 1 (mod p)。この p−1 は偶数なので、その半分の値 (p−1)/2 は整数。その整数を H = (p−1)/2 とすると p−1 = 2H となり、b^p−1 ≡ 1 の代わりに b^2H ≡ 1 と書くこともできる。b^H ≡ w とすると:
　　b^2H = (b^H)² ≡ 1　だから　w² ≡ 1 (mod p)
w ≡ 1 と w ≡ −1 は、明らかにこの2次方程式 w² ≡ 1 の解。mod p の世界は整域なので、2次方程式の解は2種類以下: つまり解は w ≡ 1 or −1 だけで、他の選択肢はない。変数を元に戻すと:
　　b^H ≡ 1 or −1　つまり　b^(p−1)/2 ≡ 1 or −1 (mod p)

要するに、p の倍数以外の任意の整数 b は、(p−1)/2 乗されると ≡ 1 or −1 のどっちかになる。どっちになるかが「オイラーの判定基準」（【6】）だが、それはそれとして、もし b が原始根なら (p−1)/2 乗が ≡ 1 ということはあり得ない（原始根というのは p−1 乗して初めて ≡ 1 になる数だから）: b が原始根なら、その (p−1)/2 乗は ≡ −1（これは、冒頭の①の議論の一般化に当たる）。

他方、原始根でなくても (p−1)/2 乗が ≡ −1 になることがある。例えば p = 7 の場合、mod 7 において 6² = 36 ≡ 1 なので、6 は原始根ではないが、6³ = 216 = 7 × 31 − 1 ≡ −1 なので、6 の (p−1)/2 乗は ≡ −1 になる。この現象は、考えている数 b の位数が (p−1)/3 や (p−1)/5 などのとき（一般に (p−1) 割る奇数が割り切れて、それが b の位数のとき）、起きる。mod 7 での 6 は、6¹ ≢ 1 だが 6² ≡ 1 なので、位数は 2 つまり (p−1)/3。この場合、6⁴ = (6²)² ≡ (1)² = 1 であり、同様に 6⁶ = (6²)³ ≡ 1 なので 6² と 6⁴ と 6⁶ が ≡ 1 になる。6^e ≡ 1 となる指数 e = 2, 4, 6 の周期が 2 なので、(p−1)/2 乗――つまり 3 乗――のときは ≡ 1 にならない（6³ ≢ 1）。上述のように、b の (p−1)/2 乗は ≡ 1 or −1 (mod p) の二者択一だから、≡ 1 にならないのなら ≡ −1 になる（6³ ≡ −1）。結論として、mod p において…
　　b は原始根　⇒　b^(p−1)/2 ≡ −1
…は常に成り立つが、
　　b は原始根　⇐　b^(p−1)/2 ≡ −1
…とは限らない。

要するに、b^(p−1)/2 ≡ −1 というのは「b は原始根」より弱い条件。本文の「mod が8k+1型素数のとき ±2 は平方剰余」という命題の証明のためには、この弱い条件で十分であり、「b は原始根」という条件は、必要以上に強い。（戻る）

2022-09-01　第二補充法則の散歩道・2　四乗剰余の冒険

ガウスDA、第115節。前回紹介した114節の別証明なのだが、この内容がなかなか渋い。高木の講義も Hardy & Wright も確かに名著だが、Gauß はやはり別格というか、オーラが違う（？）ようだ。

8.　一般に p を4n+1型の素数とするとき、1 以上 p 未満の 4n 種類の数…
　　1, 2, 3, 4, …, p−1 (=4n)
…の中で n 種類の数だけが ≡ r⁴ (mod p) の形を持つ（つまり「4乗数」、正確に言えば四乗剰余。言い換えれば「4乗根を持つ数」）。それ以外の 3n 種類の数は、そうならない。具体例と証明は…

〔例1〕　p = 13 とする。mod 13 において:
　　1⁴ = 1 ≡ 1
　　2⁴ = 16 ≡ 3
　　3⁴ = 81 ≡ 3　（←13×6=78は13の倍数）
　　4⁴ = 16² ≡ 3² = 9
　　5⁴ = 25² ≡ (−1)² = 1
　　6⁴ = 36² ≡ (−3)² = 9
この先の 7 ≡ −6, 8 ≡ −5, 9 ≡ −4 などを4乗した結果は、それぞれ 6, 5, 4 などの4乗と同じなので、新しい「4乗数」は生じない。結局、1～12の12個の数のうち、1, 3, 9 の3個だけが ≡ r⁴ (mod 13) の形を持つ。

〔注意〕　0 も含めるなら 0⁴ ≡ 0 なので、0 も「4乗数」であり、自分自身の4乗根に当たるが、ここでは r ≡ 0 を除外し r ≢ 0 とする。

証明　第一補充法則から、4n+1型の素数 p を法として −1 は平方剰余、つまり j² ≡ −1 (mod p) を満たす j が存在。

〔注意〕　複素数の世界では −1 の平方根の一つは i で表される。ここではそれをまねて、mod p での −1 の平方根を j で表すことにしよう。j⁴ = (j²)² ≡ (−1)² = 1 となる。

mod p において、ある数 A が ≡ r⁴ の形を持つなら、もちろん (−r)⁴ も ≡ A。さらに (rj)⁴ = r⁴j⁴ = r⁴ も ≡ A だし (−rj)⁴ もまたしかり。だから、ある一つの数 A に対して、4次方程式 x⁴ ≡ A は、もし解を持つなら、4種類の解 ±r, ±rj を持つ。4次方程式の解は4個以下なので、5個目の解はない。他方、ある一つの r に対して r⁴ は一定の決まった数なので、もし A ≡ r⁴ なら、「A と不合同の B に対して B ≡ r⁴ も成り立つ」ということはあり得ない。ある数が4乗根を持つなら、ちょうど4個の4乗根を持ち、別の種類の数も4乗根を持つなら、最初の4個とは別の種類の4乗根をちょうど4個持つ。

〔補足〕　4種の4乗根 ±r, ±rj は、どれも互いに不合同。まず r ≡ −r つまり 2r ≡ 0 つまり r ≡ 0 はあり得ない（r ≡ 0 は除外されている）。次に rj ≡ −rj も、両辺を j で割ると r ≡ −r なので、同じく不可能。残された可能性は、符号のどれかの組み合わせで ±r ≡ ±rj が成り立つことだけだが、この式の両辺を平方すると r² ≡ −r² となり、つまり 2r² ≡ 0 つまり r² ≡ 0 となる。r ≢ 0 なので、これも不可能。

言い換えると、1種類の4乗数 A ≡ r⁴ ごとに、それを作る4乗根 r は4種類ある: 4乗根の個数に比べると、4乗数の個数は4分の1しかない。ところが、mod p つまり mod 4n+1 において、1から 4n までの 4n 個の数の一つ一つは、どれも「その数を4乗した数」の4乗根に当たる。4乗数の個数は、4乗根の個数の4分の1なのだから、この場合、4乗数はちょうど n 個存在。□

9.　p を 3 以上の素数とする。ある数 u に関して、uv ≡ 1 (mod p) を満たす v を u の逆数と呼び u⁻¹ (mod p) で表す。例えば mod 7 において u = 2, v = 4 とすると uv = 8 ≡ 1 なので、u = 2 の逆数は u⁻¹ ≡ 4 (mod 7)。同様に v = 4 の逆数は v⁻¹ ≡ 2 (mod 7)。 1 の逆数は 1 自身、−1 の逆数は −1 自身。

命題1　A が mod p の四乗剰余なら（つまり「ある数 r の4乗」として A ≡ r⁴ (mod p) のように書けるなら）、A の逆数も mod p の四乗剰余。

証明　A⁻¹ ≡ (r⁴)⁻¹ ≡ (r⁻¹)⁴ なので、A⁻¹ は r⁻¹ の4乗に当たる。□

〔例2〕　例1において、mod 13 の四乗剰余は 1, 3, 9 の三つだった。このうち 1 は自分自身の逆数なので、もちろん 1⁻¹ = 1 も四乗剰余。一方、3 と 9 は互いに逆数であり、命題1を満たす（このとき、例えば 3 ≡ 2⁴ と書くと、2⁻¹ ≡ 7 (mod 13) が 9 の4乗根の一つ。4乗根を j 倍または −1 倍または −j 倍したものも4乗根）。

〔補足〕　素数 p を法とするとき、≡ 0 以外の数には必ず逆数が一つ存在する。これを抽象代数的に証明することは難しくないが、原始根の存在からも、直ちに同じ結論を導ける: 原始根 g を一つ選んで固定したとき、≡ 0 ではない任意の数 u を g^e ≡ u の形で表現できる（指数 e は整数）。今 g^p−1−e を ≡ v と置くと、uv ≡ g^p−1 ≡ 1 なので（フェルマーの小定理）、u と v は互いに逆数。具体例として g = 2 は mod 13 の原始根: 3 ≡ 2⁴ の逆数は 2¹²⁻⁴ = 2⁸ (= 256 = 260 − 4 ≡ −4) ≡ 9。 2 ≡ 2¹ 自身の逆数は 2¹²⁻¹ = 2¹¹ (= 2048 = 13×157+7) ≡ 7。実用上の逆数計算には、互除法に似たもっと便利な方法がある。

〔例3〕　例1と同様にすると、mod 17 の四乗剰余は 1, 4, 13, 16 の4個（この個数は 17 − 1 の4分の1）。このうち 1 と 16 ≡ −1 は、それぞれ自分自身の逆数。4 と 13 は（4×13 = 52 = 17×3+1 ≡ 1 なので）互いに逆数。

4n+1型の素数 p は、n が偶数 2k か奇数 2k+1 かに応じて、4(2k)+1型つまり8k+1型の素数（愛称: 春素数）と、4(2k+1)+1型つまり8k+5型の素数（愛称: 秋素数）に分けられる。mod p での四乗剰余の合計個数は、1 から p−1 までの数の4分の1なのだから（7.参照）、p が8k+1型なら 8k/4 = 2k 個、p が8k+5型なら (8k+4)/4 = 2k+1 個、つまりそれぞれ偶数個と奇数個。

これらの四乗剰余について、互いに逆数の関係にある数をペアとして（命題1参照）、考えてみよう。

〔例4〕　上の例2では (3, 9) は（互いに逆数である2種類の数の）ペアだが、(1, 1) は自分自身とペアになる。例3では (4, 13) が2種類の数のペアだが、(1, 1) と (−1, −1) はそれぞれ自分自身とペアになる。

すなわち、一般的には、2種類の2数がペアになり、一つのペアに2種類の四乗剰余が含まれる: 例えば mod 13 のペア (3, 9) は2種類の四乗剰余 3 と 9 を含む。一方、1種類の数が自分自身とペアになる特殊なケースでは、一つのペアに1種類の四乗剰余しか含まれていない: 例えばペア (−1, −1) は1種類の四乗剰余しか含んでいない。従って、前者（不合同な2数のペア）が合計 F 組あって、後者（自分自身とのペア）が合計 G 組あるとすると、四乗剰余は合計 2F + G 種類存在する。上記の考察と組み合わせると:
　　p が8k+1型　⇒　四乗剰余は偶数個。その個数は 2F + G
　　p が8k+5型　⇒　四乗剰余は奇数個。その個数は 2F + G
…となるので、前者では G が偶数、後者では G が奇数。

ところで u の逆数が u 自身になるというのは、u ≡ u⁻¹ (mod p) ということ: その両辺を u 倍すると u² ≡ u⁻¹u ≡ 1。これは2次方程式なので、解は最大2個（そして u ≡ 1 と u ≡ −1 の二つは明らかに解）。つまり「自分自身とのペア」の個数 G は最大 2――この最大 2 という個数は、もちろん2組のペア (1, 1) と (−1, −1) の存在の可能性に対応する。ところが 1⁴ ≡ 1 は常に四乗剰余であり、言い換えれば、(1, 1) はいつでも有効なペアとしてカウントされる。結局、G が偶数か奇数かというのは G = 2 か G = 1 かの違いであり、その違いは、−1 が四乗剰余かどうか――言い換えれば (−1, −1) が有効なペアかどうか――によって決まる。整理すると:
　　p が8k+1型　⇒　四乗剰余の個数 2F + G は偶数　⇒　G = 2　⇒　1 も −1 は四乗剰余
　　p が8k+5型　⇒　四乗剰余の個数 2F + G は奇数　⇒　G = 1　⇒　1 は四乗剰余だが −1 は四乗剰余でない

結論　p が8k+1型の素数なら −1 は四乗剰余。

10.　だから p が8k+1型の素数なら、y⁴ ≡ −1 (mod p) を満たす y が存在する。y の逆数 y⁻¹ も四乗剰余であることを思い出そう（命題1）。今 y とその逆数の和を平方すると:
　　(y + y⁻¹)² = y² + 2⋅y⋅y⁻¹ + y⁻²
　　つまり　(y + y⁻¹)² = y² + 2 + y⁻²　　‥‥（＊）
ここで条件 y⁴ ≡ −1 の両辺の逆数を考えると y⁻⁴ ≡ −1、その両辺を y² 倍すると y⁻² ≡ −y²。これを（＊）に代入して:
　　(y + y⁻¹)² ≡ y² + 2 + (−y²)
　　つまり　(y + y⁻¹)² ≡ 2

すなわち 2 は mod p の平方剰余で、具体的に「平方すると ≡ 2 になる数」は y + y⁻¹。この結論は 6. の式⑧と一致する！

〔例5〕　17 は8k+1型の素数なので −1 は mod 17 の四乗剰余になるはず。実際、2⁴ = 16 ≡ −1 (mod 17) なので −1 ≡ y⁴ に解がある: y = 2 だ。2 × 9 = 18 ≡ 1 なので、この y の逆数は y⁻¹ ≡ 9 (mod 17)。従って y + y⁻¹ ≡ 2 + 9 = 11 が「平方すると ≡ 2 になる数」ということに…。確かめてみよう: 11² ≡ (−6)² = 36 = 17 × 2 + 2 ≡ 2 (mod 17)。確かにそうなってる。平方するのだから、11 の代わりに −11 ≡ 6 を使っても結果は同じ。

同様に (y − y⁻¹)² = y² − 2⋅y⋅y⁻¹ + y⁻² = y² − 2 + y⁻² ≡ y² − 2 + (−y²)
　　つまり　(y − y⁻¹)² ≡ −2

すなわち −2 も mod p の平方剰余で、具体的に「平方すると ≡ −2 になる数」は y − y⁻¹。

〔例6〕　例5の途中結果を使って、y − y⁻¹ ≡ 2 − 9 = −7 が「平方すると ≡ −2 になる数」。平方するのだから符号は ±7 のどっちでも結果は同じ: (±7)² = = 49 = 17 × 3 − 2 ≡ −2 (mod 17)。

±2 が 春素数の平方剰余であることが、あらためて証明された！

11.　本題は「四乗剰余の考察」ではなく、あくまで「±2 が平方剰余か非剰余か」。その本題からはそれてしまうが、この先に、寄り道のしがいのある「ちょっとすてきな風景」がある…。上記 10. の議論から「8k+5型素数（秋素数）を法とすると −1 は四乗剰余でない」ことは明白（G = 1 なのでペア (−1, −1) の存在が否定される）。では、法が8k+3型（夏）や8k+7型（冬）のときは、どうなるか？

今回主に考えたのは4n+1型の素数（愛称: バニラ素数）だった。バニラ素数が、春（8k+1)と秋（8k+5）に分かれ、そのうち春素数だけが「それを法として ±2 がどちらも平方剰余」という特別な性質を持つ。

一方、4n+3型の素数（愛称: チョコレート素数）は、n が偶数 2k か奇数 2k+1 かに応じて、夏素数（8k+3)と冬素数（8k+7）に分かれる。ところが、第一補充法則によると、mod がチョコレート素数のとき −1 は平方剰余ではない。つまり p がチョコレート素数のとき j² ≡ −1 (mod p) を満たす j は存在しない。このことから、この場合「ましてや −1 の4乗根があるわけない」ことが直ちに分かる。というのも、p がチョコレート素数のとき、もしも y⁴ ≡ −1 (mod p) を満たす y があったとすると（−1 が四乗剰余とはそういう意味である）、その y の2乗を j とすれば、こうなる:
　　j ≡ y²　⇒　j² ≡ y⁴ ≡ −1
　　要するに　j² ≡ −1 (mod p)
この結論が不可能なことは（平方剰余の第一補充法則によって）分かっているので、上記のような y は存在し得ない。つまり mod が夏素数や冬素数のときも、決して −1 は四乗剰余にならない。

まとめると…

四乗剰余の第一補充法則　p を 3 以上の素数とすると、p が8k+1型なら（そしてその場合に限って）、−1 は mod p の四乗剰余。すなわち y⁴ ≡ −1 (mod p) に解がある。p がそれ以外の型なら、−1 は四乗非剰余。すなわち y⁴ ≡ −1 (mod p) に解がない。

別に壮大な定理じゃないけれど、きれいにまとまってチャーミング…。「伴侶論法」（2種類のものがペアになる場合と、1種類のものが自分自身とペアになる場合の区別）を使う証明の仕方も、軽妙でいい感じ。

（付記）

「○次方程式の解は○個以下なので…」のような論法を随所で使ったが、これは考えている世界が整域だから成り立つこと。mod が素数の世界は整域なので問題ないが、mod が素数でない場合には、この主張は成り立たない。

例えば「u² ≡ 1 (mod m) は2次方程式なので、解は u ≡ ±1 の2種類」という主張。m が 3 以上の素数ならいいのだが、m が素数以外、例えば 8 とすると…。u² ≡ 1 (mod 8) は「4種類」の解 u = ±1, ±3 を持つ！

他方、m = 2 は素数だが、その場合 1 ≡ −1 (mod 2) なので、u ≡ ±1 は実は「1種類」の解になる（「2次方程式の解は2個以下」という法則には反してないが、ちょっと例外的）。

2022-09-03　第二補充法則の散歩道・3　ガウスの手書きメモ

12.　DAの出版後、ガウスは第114節の内容について、さらに巧妙な証明を思い付いたらしい。「ガウスの手書きの覚書」として、全集・第1巻に収録されている。自著の余白か、原稿の隅にでもメモしたのだろう。

DA114節では、mod が8k+1型素数のとき、任意に選んだ原始根 g について g^4k ≡ −1 となることから、ガウスはこの合同式を
　　(g^2k ± 1)² ≡ ±2⋅(a^k)²
と変形し、そこから ±2 が平方剰余であると論じた（1. 参照）。ガウスの手書きメモでは代わりに次の変形が使われ、±2 が平方剰余であることが明示的に表現されている。
　　(g^3k − g^k)² = 2 + (g^4k + 1)(g^2k − 2)　　☆
　　(g^3k + g^k)² = −2 + (g^4k + 1)(g^2k − 2)　　★
ここで g^4k ≡ −1 つまり g^4k + 1 ≡ 0 なので、☆と★のどちらでも、右辺第2項は ≡ 0 になって消滅。従って、次のように「平方すると ≡ ±2 になる数」が得られる:
　　(g^3k − g^k)² ≡ 2　　☆☆
　　(g^3k + g^k)² ≡ −2　　★★

ガウスは詳しい説明を記していないが、表面的な計算としては、☆の左辺を展開すると
　　g^6k − 2g^3kg^k + g^2k = g^6k − 2g^4k + g^2k
☆の右辺を展開すると
　　2 + g^6k − 2g^4k + g^2k − 2 = g^6k − 2g^4k + g^2k
…なので、確かに☆の両辺は等しい。★についても同様。けれど、これだけでは天下り的で、「これらの式はどこから来たのか・どういう意味なのか」という点が不透明だ。

6. で確かめ 10. で整理したことだが、mod 8k+1 において、2 の平方根（平方すると ≡ 2 になる数）は y + y⁻¹ の形を持ち、−2 の平方根は y − y⁻¹ の形を持つ――ここで y は「4乗すると ≡ −1 になる数」（4種類あるが、そのどれを選んでもいい）。g^4k ≡ −1 だから、最も手っ取り早い選択肢は y ≡ g^k だろう。その逆数 y⁻¹（つまり g^k との積が ≡ 1 になる数）は ≡ g^7k。実際、フェルマーの小定理から g^k × g^7k = g^8k ≡ 1。

従って y + y⁻¹ の具体的な値としては、g^k + g^7k を使うことができる。あるいは g^7k = (g^4k)g^3k ≡ −g^3k なので、代わりに g^k − g^3k を使うこともできる。すなわち (g^k − g^3k)² ≡ 2。符号が逆の −(g^k − g^3k) つまり g^3k − g^k も、平方してしまえば結果は同じなので:
　　(g^3k − g^k)² ≡ 2

これがガウスの☆☆の真意だろう。★★についても同様: g^k − g^7k の平方が ≡ −2 だから、g^k − (−g^3k) の平方、つまり (g^3k + g^k)² は ≡ −2。

上記では g^7k の代わりにそれと合同な −g^3k を使ったが、g^7k をそのまま使って、次のようにまとめて書くこともできる:
　　(g^k ± g^7k)² ≡ ±2

g が原始根という条件は、必要以上に強い。g^4k ≡ −1 さえ成り立てば、g は原始根でなくても構わない。

13.　具体例で確かめてみよう。mod 41 の場合、41 = 5⋅8 + 1 だから k = 5、最小の原始根は g = 6 だった（4. 参照）。☆☆を使うには g^k = 6⁵ と g^3k = 6¹⁵ を mod 41 で計算する必要がある。コンピューターを使えば、
　　6⁵ = 7776 ≡ 27
　　6¹⁵ = 470184984576 ≡ 3
という計算は一瞬だが、32ビットの整数演算だと、6¹⁵ はオーバーフローしてしまう…。一般論として「べき剰余」は、次のように計算した方が速く（繰り返し2乗法）、メモリーも節約できる（この例では手計算・暗算も難しくない）:
　　まず　6² = 36 ≡ −5　（なぜなら 36 = 41 − 5）
　　だから　6⁴ = (6²)² ≡ (−5)² = 25 ≡ −16　（なぜなら 25 = 41 − 16）
　　従って　6⁵ = (6⁴)⋅6 = (−16)⋅6 = −96 ≡ −14　（なぜなら −96 = −2(41) − 14）
この 6⁵ ≡ −14 を3乗すれば 6¹⁵ だが、2乗と1乗の積を考えた方が話が早い:
　　6¹⁰ = (6⁵)² ≡ (−14)² = 196 (= 5(41) − 9) ≡ −9
　　6¹⁵ = (6¹⁰)(6⁵) ≡ (−9)(−14) = 126 (= 3(41) + 3) ≡ 3
この例では g^3k は 6¹⁵ で g^k は 6⁵ なのだから:
　　g^3k − g^k ≡ 3 − (−14) = 17　これを平方すると…
　　(g^3k − g^k)² ≡ 17² = 289 (= 7(41) + 2) ≡ 2
…確かに 2 になる。つまり x² ≡ 2 (mod 41) は解を持ち、2 は平方剰余！

次に★★を使って:
　　g^3k + g^k ≡ 3 + (−14) = −11　これを平方すると…
　　(g^3k − g^k)² ≡ (−11)² = 121 (= 3(41) − 2) ≡ −2
すなわち −2 も平方剰余！

実際には、より小さい値 g = 3（それは原始根ではないが、g^4k ≡ −1 を満たす）を使うことができる。3¹⁵ ≡ 14 と 3⁵ ≡ −3 の差・和は、それぞれ 17 と 11。それらを平方すれば、上と同様 ±2 になる。

この手の計算では、10台の数の2乗に慣れていると便利。上記では 11² = 121, 14² = 196, 17² = 289 が登場した。

Gauß の覚書は、Werke 第1巻、475ページに載っている:
https://archive.org/details/werkecarlf01gausrich
Concinnius demonstratio ita adornatur（より巧妙に証明はこう用意される）以下がガウスの言葉。形容詞 concinnus（巧妙な）の比較級は規則的で、男性形・女性形 concinnior、中性形 concinnius; 副詞 concinne（巧妙に）の比較級も同形の concinnius。ここでは副詞。なぜなら、demonstratio（証明）は女性名詞なので「より巧妙な証明」なら形容詞は concinnior になるはずだし、ラテン語では、通常、形容詞は名詞の後ろに置かれる。…いずれにしても、自分用の覚書までわざわざラテン語で書くとは、ガウスは古風な学者タイプだったようだ。思い付いたことを几帳面にメモするところは、いかにもドイツ人らしい（ステレオタイプな見方かもしれないが…）。「最も驚嘆すべき証明を発見したが、この余白は狭過ぎる」などと、思わせぶりに中身のないメモを書くどこかのフランス人とは、大違いである（笑）！

高木は Gauß DA の表現形式について「一種の韜晦（とうかい）であって、頭の中では ω によって構成した理論を発表するのに f を籍（か）りたかの観がある」と記しているが、Abel も Gauß について「He is like the fox, who effaces his tracks in the sand with his tail」というコメントを記している。☆の式がどこからやって来たのか、導出過程は秘密なのだ…。Gauß いわく「No self-respecting architect leaves the scaffolding in place after completing the building」（まともな建築家なら、工事が終わったら足場を撤去するものだ）。

2022-08-29　温故知新　「フランスの数学教育」のジョーク

「第二補充法則の散歩道」では、ガウスのDA第114節を紹介した。「8k+1型の素数を法として ±2 は平方剰余」というものであり、ガウスは原始根を使ってこれを証明し、ディリクレは原始根を使わずに済むように、それをアレンジしている。

よくよく考えてみると、原始根を使うガウスの方法は、必要以上に強い制約を課している。「g は原始根」というのは、実は不必要な仮定。その意味で、余計な条件を取り払ったディリクレ版は一歩前進しているのだが、ディリクレ版には「入り口の部分が不必要にややこしい」という別の短所がある。

これらのもやもやを解消すべく「散歩道」と「簡単な証明・春」の両方に多少の追記を行った。

ところで、おおよそ次のような趣旨のジョークがある。

「フランスの数学教育の現代化は、大成功だった。試しにフランスの小学生に 3 + 4 が分かるか尋ねてみると、すぐに次の答えが返ってきた。『加法の可換性によって、それは 4 + 3 に等しい』」

このジョークの意味は、分かる人にはすぐ分かるだろう。詳しい説明は省くが、ブルバキ流の構造主義は、文脈がずれるとばかげたことになる。これに似た「数学教育の現代化」の試みは実際に行われたし、成功もあれば失敗もあった。身近な例でいえば、現代の数学で当たり前のように使われる空集合の記号とか、写像の概念（単射・全射・双射）は、ブルバキによって導入されたものだろう。

で、まぁ、「ガウスはすごい天才だなぁ」という認識は普通にあったものの、200年前の著書、ガウスのDAやディリクレの講義（それはガウスのDAの一般向け解説書と言ってもいいだろう）を実際に読んでみようという「物好き」な考えは、もともとなかった。偶然のきっかけから、ディリクレの講義をちょっと読んでみて、非常に驚いた。極端に言うと、世界観が変わった。

例えば「3 は平方剰余か？」という問題を相互法則を使って抽象的・機械的に解決する現代のアプローチは、上記のジョークの「フランスの小学生」のようなものだと感じるようになった。現代の教科書の方法だと「確かに構造を理解できるようになる。確かに正しい答えを出せるようになる。でも本当の意味で中身が分かっていない」のではないか…。抽象的な構造は重要だが、「具体的な実例」も面白いし奥深い。むしろ後者に支えられて、前者がより透明に見通せるようになる面もある。

例えばガウスDA115の内容を発展させると、「奇素数 p を法として −1 が四乗剰余」と「素数 p が8k+1型」が同値であることが、「伴侶」論法風にエレガントに証明される。このチャーミングな構造は、「8k+1型素数 p を法として ±2 は平方剰余になる」という非常に具体的な議論と関連している（現代の教科書では、こんな具体的過ぎること、いちいち扱わないだろう）。一つ非常に良いこととして、200年前の文献だと当然著作権が切れているので、パブリックドメインで自由に読める。「学問の自由」の理想形と言えるだろう。

200年前なので、もちろん現代から見ると「アナクロ」な面もあるのだが、ガウスやディリクレには、それを補って余りある価値がある。ラテン語やらドイツ語やらというのも、一般人にとっては敷居が高いかもしれないけど、文学ならともかく、数学の場合、数式と数式の間で何を言っているのかは、読まなくても結構予想がつく（上の式から下の式を導く練習問題だと思ってもいい）。趣味や向き不向きはそれぞれだろうけど、息抜きとして、のんびり昔の文献を解読してみるのも、また一興ではないだろうか。

---