メモ(数論8): 平方剰余の相互法則

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

数論(メモ)の目次

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

***

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 つまり 22 が ≡ D となる。5 についても同様。このように、ax ≡ D で a ≡ x となる場合――言い換えれば x2 ≡ D に解がある場合――、それは2次方程式なので、2種類の解を持つ(r が解なら −r ≡ p − r も解): この場合、S の要素のうちその2種類は特例的になるが、それ以外の要素は、例1同様、過不足なくペアを作る。対照的に、例1は x2 ≡ D に解がない場合。

☆ x2 ≡ D (mod p) に解があるとき、D は mod p において平方剰余と呼ばれる。x2 ≡ 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 ≡ 53  ←これが 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 ≡ 42  ←これが D(p−3)/2
  右端の指数の 2 は (p−3)/2 = (7−3)/2

特例の2個は x2 ≡ D の解だから ±x の形を持つ。その2個の積は:
  x(−x) ≡ −x2 ≡ −D  ← x2 ≡ 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 の場合、x2 ≡ 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 = 23 = 8 ≡ +1 (mod 7) ⇒ 判定結果=mod 7 において 2 は平方剰余
一方、3(7−1)/2 = 33 = 27 ≡ −1 (mod 7) ⇒ 判定結果=3 は平方非剰余

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

【8】 第一補充法則 p が「4k+1型」の素数なら x2 ≡ −1 (mod p) は解を持つ(言い換えると −1 は平方剰余)。p が「4k+3型」の素数なら x2 ≡ −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。従って、平方非剰余。□

〔例題〕 ① x2 ≡ −1 (mod 13) に解があるか? 13 は4k+1型なのでYes。② x2 ≡ −1 (mod 17) に解があるか? 17 も4k+1型なのでYes。③ x2 ≡ −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−1 についてオイラーが使った概念らしい(sŏcĭī、単数形 socius)。一般の D についての a の伴侶は a−1D。

⁂

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

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

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

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

Dirichlet (1863, 4th ed. 1894): Vorlesungen über Zahlentheorie, §41
https://archive.org/details/vorlesungenber00lejeuoft
[Gauß: Disquisitiones Arithmeticae の art. 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 が夏素数か秋素数のとき、x2 ≡ 2 (mod p) を満たす x はない。言い換えると、8k±3型素数を法として 2 は平方非剰余。

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

〔解説〕 p が春素数か冬素数なら x2 ≡ 2 (mod p) は解を持つ。例えば p = 17 のとき:
  62 = 36 ≡ 2 (mod 17) なので x = 6 は一つの解。
また例えば p = 23 のとき:
  52 = 25 ≡ 2 (mod 23) なので x = 5 は一つの解。
ここで ≡ 2 (mod □) という記号については「余りは 2 だよ、□で割ると!」と解釈しておこう(もっと正確な説明)。
一方、p が夏素数か秋素数のとき、x2 ≡ 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】 x2 ≡ 2 (mod p) が解を持つような、夏または秋素数(つまり8k±3型の素数)p が存在する…と仮定する(当然 p は奇数)。もちろん「事実の反対をあえて主張し、矛盾を発生させてやる」という魂胆である。兵は詭道きどうなり!

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

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

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

奇数の2乗を 8 で割ると 1 余る。12 = 1, 32 = 9, 52 = 25, 72 = 49…おおぉホントだっ!

【3】 『し』の両辺は等しいのだから、その左辺を 8 で割った余りと、右辺を 8 で割った余りは、当然、等しい:
  x2 − 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。『し』に代入すると:
  x2 − 2 = pQ = pqr
従って x2 − 2 は q で割り切れる(商は pr)。言い換えると:
  x2 − 2 ≡ 0 (mod q) 移項すると
  x2 ≡ 2 (mod q) ここで q は Q 以下の夏 or 秋素数  ‥‥『た』

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

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

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

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

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

『た』の 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】 上記で証明されたこと:

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

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

*

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

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

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

証明 x2 − 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 = {p1, p2, …, pn} の n 個しか存在しないと仮定し、ユークリッドの手筋に従って、それらの積を
  t = p1p2…pn
とする。

x = 4t と置くと:
  x2 − 2 = (4t)2 − 2 = 2[8(t2) − 1]

↑ちょっと待て、その x = 4t とか x2 − 2 って式は、どっから出てきたんだ? 天下り的に置換するな!

…という疑問もおありでしょう。全部見せます舞台裏↓

〔秘密の思考過程〕 8t + 7 か 8t − 1 を使えれば一番楽だけど…その数が素数になってくれりゃ、新しい「8k+7型」素数が見つかる…。けど、この数が合成数になったらどうしよ。「この数の因子の中には、必ず新しい8k+7型素数が…」というパターンにするには…。素因子を春・冬に絞れれば補助命題2が使える。絞らない状態だと、夏(8k+3型)と秋(8k+5型)の積として冬(8k+7型)を作れるので(3 × 5 = 15 ≡ 7 mod 8)、8k+7型の奇数を構成しても、因子が「新しい冬素数」を全然含んでない可能性が*3…。夏・秋の素因数がない保証が欲しい…だから補助命題1を使おう。使うには「何とかの2乗マイナス2」の形にすれば…つまり 8t2 − 2 あたりで…いや、それじゃ第1項が「何とかの2乗」じゃないぞ…係数を2倍して 16t2 − 2 = (4t)2 − 2 なら…

…と一生懸命考えたことはナイショ。さも当たり前のように、涼しい顔で↓

x = 4t と置くと:
  x2 − 2 = (4t)2 − 2 = 2[8(t2) − 1]
補助命題1により、この数の奇数の素因数は、春または冬素数に限られる。右辺の因数 8(t2) − 1 は「8k−1型」の奇数であり、①それ自身が素数であるか、さもなければ、②奇素数の積に分解される。

①もし 8(t2) − 1 が素数なら、それは明らかに S のどの素数よりも大きい: S に含まれない冬素数。

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

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

〔例1〕 冬素数が {7, 23} だけと仮定。t = 7 × 23 = 161。
8t2 − 1 = 207367。これは新しい冬素数。

〔例2〕 冬素数が {7, 23, 31} だけと仮定。t = 7 × 23 × 31 = 4991。
8t2 − 1 = 199280647 = 17 × 11722391。17 は春素数、11722391 は新しい冬素数。

〔例3〕 冬素数が {7, 23, 31, 47, 71, 79, 103} だけと仮定。t = 135521466479。
8t2 − 1 = 5231 × 20479 × 42967 × 31921087169。
最初の3個の素因数は冬、最後の1個の素因数は春。

この方法では、8t2 − 1 の因数として奇数個の「新しい冬素数」が生成される。

*3 単に 8t − 1 を使うんじゃ駄目な例: 冬素数が {7, 23} だけと仮定。t = 7 × 23 = 161。8t − 1 = 1287。この奇数は確かに「8k+7型」だが、1287 = 32 × 11 × 13 と素因数分解される。この因数のうち 3, 3, 11 の三つは夏素数、13 は秋素数で、新しい冬素数の因子が出てこない。8k+7型の素因数を含んでなくても、積は8k+7型の奇数になり得るのだ:
  3 × 3 × 11 × 13 ≡ 3 × 3 × 3 × 5 ≡ 135 ≡ 7 ≡ −1 (mod 8)
「夏素数と秋素数の積」は、8k+7型の奇数なので…。「夏・秋の素因数を持たない数」を作れば、このパターンを排除できる。

〔追記〕 次の文献は、上記と同じ方法で定理3(冬素数の無限)を証明している。Ireland & Rosen (1982): A Classical Introduction to Modern Number Theory, Chapter 5, §1

⁂

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

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

【7】 今回も元ネタは DirichletVorlesungen §41 の続き: Gauß DA art. 113)

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

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

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

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

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

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

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

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

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

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

【9】 『に』の左辺は、正の奇数(なぜなら奇数の平方プラス2 = 正の奇数プラス2 = 正の奇数)、右辺の p も正の奇数だから、Q も正の奇数。前回見たように(『す』『せ』)、奇数 x の平方は x2 ≡ 1 (mod 8) を満たす。その両辺に 2 を足すと:
  x2 + 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 とでも置いて、それを『に』に代入すると:
  x2 + 2 = pqr
この右辺は q で割り切れるので、それに等しい左辺も、もちろん q で割り切れる。言い換えると:
  x2 + 2 ≡ 0 (mod q) ここで q は秋 or 冬素数  ‥‥『の』

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

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

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

補助命題3 x2 + 2 の奇数の素因数があるとすれば、春または夏素数に限られる。

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

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

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

証明 8k+3型素数(夏素数)が S = {p1, p2, …, pn} の n 個しか存在しないと仮定し、ユークリッドの手筋に従って、それらの積を
  t = p1p2…pn
とする。t は奇数の積なので奇数。

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

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

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

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

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

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

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

素数が無限にあることは、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 = 36 = 729 ≡ +1 (mod 13)  ‥‥『は』
   13 × 56 = 13 × 50 + 13 × 6 = 650 + 78 = 728 なので
   728 は 13 の倍数。729 は 13 の倍数より 1 大きい。

一方 b = 2 は平方非剰余:
  2(13−1)/2 = 26 = 64 ≡ −1 (mod 13)  ‥‥『ひ』
   64 は 13 の倍数(65)より 1 小さい。
このとき ab = 6 が平方剰余かどうか判定するのに、普通に…
  6(13−1)/2 = 66 = 46656 ≡ −1 (mod 13)
…を計算してもいーんだけど、もっと単純に
  6(13−1)/2 = 66 = 36 × 26 ≡ (+1)(−1) = −1
ってできるってこと。説明↓

☆ 最後の式の2個目の等号の意味は:
  66 = (3⋅2)6
  = (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個
  = 36 × 26

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

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

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

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

第二に、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 = 56 = 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 は平方剰余。言い換えると x2 ≡ 10 (mod 13) に解があると判定される。果たして x = 6 とすれば 62 = 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】 x2 ≡ 2 (mod p) は解を持つか? p が夏・秋・冬素数の場合については、結論が出た: p が冬ならYes、夏・秋ならNo。残された問題は p が春素数、つまり8k+1型の場合だが…

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

Dirichlet は、このケースを次のように軽妙に扱っている。

【14】 代数学によると xk − yk は x − y で割り切れる。特に y = 1 とすると、xk − 1 は x − 1 で割り切れる。具体的には:
  xk − 1 = (x − 1)(xk−1 + xk−2 + … + x2 + x + 1)  ‥‥『ま』

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

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

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

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

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

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

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

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

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

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

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

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

謎めいた式『よ』がどうやって導出されるかはさておき*5、「それで合ってる」こと――確認済みの『や』&『ゆ』と意味が一致すること――を確かめておく。『や』の p = 8k±1 の場合、
  p2 = (8k ± 1)2 = 64k2 ± 16k + 1 そこから 1 を引くと
  p2 − 1 = 64k2 ± 16k = 8[8k2 ± 2k] = 8[2(4k2 ± k)]
なので、p2 − 1 は「8 × 偶数」に当たり、8 で割れば「偶数」になる。要するに、p = 8k±1 なら『よ』は (−1) を偶数乗しろということで、結果は +1、『や』と一致。一方、『ゆ』の p = 8k±3 の場合、
  p2 = (8k ± 3)2 = 64k2 ± 48k + 9 そこから 1 を引くと
  p2 − 1 = 64k2 ± 48k + 8 = 8[8k2 ± 6k + 1] = 8[2(4k2 ± 3k) + 1]
なので、p2 − 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 が平方剰余。この事実については、別ルートで確かめることもできる: 『も』と同様にして y4 + 1 ≡ 0 を (y2 − 1)2 + 2y2 ≡ 0 と書けば (y2 − 1)2 ≡ −2y2 となるから、【15】と全く同じ議論から、法が8k+1型の素数なら −2 も平方剰余と結論される。

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

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

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

別の例として、春素数 p = 41 を考える。x = y8 と置いて公式『ま』を使うと:
  y40 − 1 = x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1)
  = (y8 − 1)(y32 + y24 + y16 + y8 + 1)
  = (y4 + 1)(y4 − 1)(y32 + y24 + y16 + y8 + 1) ≡ 0 (mod 41)

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

「いまいち納得がいかない」「前編・中編の背理法による証明が分かりにくい」「どうでもいいけど長ったらしい」…といったご批判もあるでしょうが、後からガウスの補題経由で直接的に第二補充法則を再証明し、両面から眺めてみたい。「最初からガウスの補題をやった方が効率的」と思えるかもしれないが、ガウス自身も、このように3つに分けて研究を進めた(前編・中編は本質的に Gauß DA art. 112, 113 と同じ。後編の証明法は Dirichlet のオリジナルだが、証明される内容は Gauß DA art. 114, 115 に当たる)。「天才ガウスにもすぐには思い付けなかったトリッキーなショートカット」をいきなり理解させようとする現代の教科書は、不親切を通り越して無謀だろう。急がば回れ。

⁂

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 とする。x2 ≡ q (mod p) を満たす解 x は存在するか、つまり
  x2 ≡ 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)n = ±1
…の右辺の符号がプラスかマイナスかで、平方剰余・非剰余を判定できる。この性質は、ガウスの補題(Gauss’s lemma)と呼ばれる。オイラーの(判定)基準と似てるので、ガウスの(判定)基準と呼んだ方が分かりやすいかもしれない。

例題の一つの解は x ≡ 6。実際 62 ≡ 36 ≡ 10 (mod 13)。これは「36 も 10 も、13 で割った余りは同じ」という意味だった。同じことだが「36 と 10 の差は 13 の倍数」という意味。2乗するのだから符号はどっちでもよく x ≡ −6 ≡ 7 も解: 72 ≡ 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 個あるとする)
  《キ》 c1, c2, c3, … , cm
とデカ余り(合計 n 個あるとする)
  《ク》 d1, d2, d3, … , dn
を合わせたものについて、どの2個を選んでも不合同であることは、上述の通り。《ク》を小さくした
  《ケ》 p − d1, p − d2, p − d3, … , p − dn
についても、mod p では、順に
  《コ》 −d1, −d2, −d3, … , −dn
と合同なので(p で割った余りで分類してるんだから、p を足し算しても(商が1増えるだけで)余りつまり分類結果は変わらない)、《ク》の各数が不合同であるからには、《ケ》ないし《コ》の各数も不合同(もしも《コ》の数について −d2 ≡ −d3 のような事態が発生するとすれば、両辺を −1 倍して d2 ≡ d3 となるが、その可能性は《ク》において否定されている)。

従って(《キ》の内部にも《ケ》の内部にも互いに合同な数はないので)、《キ》と《ケ》にまたがって合同な数がないことを示せば、《キ》《ケ》の各数は全部不合同と結論される。仮に《キ》の数のどれか 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)をそれぞれ
  《ツ》 a1, a2, a3, … , aH
とすると、q ≡ a1, 2q ≡ a2, … (mod p) となり、《チ》の各数はそれぞれ《ツ》の各数と合同。以下、合同式は全て mod p で考え、しばしば mod p という表記を省く。《ツ》をチビ余り・デカ余りに分類して並び替えると:
  《テ》 c1, c2, c3, … , cm, d1, d2, d3, … , dn
もちろん m + n = H である。《テ》は《ツ》を並び替えただけなので、《テ》の各数は、引き続き、全体としては《チ》の各数と合同。他方、《テ》について、デカ余りの部分を次のように小さくした場合、その結果は、全体として《タ》の数を並び替えただけ(【3】参照):
  《ト》 c1, c2, c3, … , cm, p − d1, p − d2, p − d3, … , p − dn

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

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

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

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

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

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

ガウスの補題 p を奇素数、q を p で割り切れない数、H = (p−1)/2 とする。
  q, 2q, 3q, … , Hq
を p で割った余りのうち p/2 より大きいものの合計個数を n とすると、L(q, p) = (−1)n。ここで 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 = 28 = 256 ≡ 1 (mod 17)。Yes判定。

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

p = 11 のとき: 33 は 11 の倍数。従って 2(11−1)/2 = 25 = 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)4 = 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)3 = −1。No判定。

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

さて mod 11 で 3 は平方剰余だろうか?
  3, 6, 9, 12, 15
これを 11 で割った余りは:
  3, 6, 9, 1, 4
デカ余りが 6, 9 の 2 個なのでYes判定。実際 52 = 25 ≡ 3 (mod 11)。では 4 は平方剰余か?
  4, 8, 12, 16, 20
これを 11 で割った余りは:
  4, 8, 1, 5, 9
デカ余りが 8, 9 の 2 個なのでYes判定(4 は平方数なので、判定するまでもなく 22 ≡ 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 は平方剰余: x2 ≡ 1 を満たす x は必ず存在する。つまり x ≡ ±1)。0 を別にすると、平方剰余も非剰余も 5 個ずつ存在する。

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

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

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

《タ》~《テ》が同じで《ト》の代わりに、次を使う:
  《ド》 c1, c2, c3, … , cm, d1 − p, d2 − p, d3 − p, … , dn − p
このとき《チ》の数全部の積と《ド》の数全部の積が(ダイレクトに!)合同になる。前者は《ナ》で見たように (H!)qH。後者について、《ド》は絶対値においては 1 から H までの各数、そのうちマイナスが付く数が n 個あるのだから (−1)n(H!)。従って:
  (H!)qH ≡ (−1)n(H!)
両辺を H! で割れば、直ちにガウスの補題を得る。おおっ!

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

証明という点では高木の方法はエレガントだが、実際の計算の観点からは、多くの場合、「絶対的最小剰余が負のものの個数」を数えるより、単に「普通に割り算して余りが p/2 より大きいものの個数」を数える方が自然だろう。しかも 1⋅2⋅3…H の因子の「不定の位置に不定の個数のマイナスが付く」という状況を式で表現しようとすると、若干技巧的になってしまう。Gauß / Dirichlet の方法だと、1⋅2⋅3…H という積(符号は全部プラス)に話が固定され、具体的で分かりやすい。Gauß は、第三証明(1808)のときには【2】以下の方法で《ノ》を導き、第五証明(1818)のときは、同様に《ニ》まで進めてから両辺に (−1)n を掛け算して、p − d を d − p に変更している。Hardy & Wright, §6.11 は Gauß / Dirichlet をベースにしつつ、高木と同様に符号を設定している。

文献
[1] Dirichlet, Vorlesungen, §43
https://archive.org/details/vorlesungenber00lejeuoft
[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

前回の続き。Dirichlet–Dedekind: Vorlesungen の §44(99~102ページ)の内容を扱う。
https://archive.org/details/vorlesungenber00lejeuoft

【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) の通り。HH + 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 デカ余り: d1 = 7
  2q = 14 に対して 14÷13 商 1 余り 1 チビ余り: c1 = 1
  3q = 21 に対して 21÷13 商 1 余り 8 デカ余り: d2 = 8
  4q = 28 に対して 28÷13 商 2 余り 2 チビ余り: c2 = 2
  5q = 35 に対して 35÷13 商 2 余り 9 デカ余り: d3 = 9
  6q (= Hq) = 42 に対して 42÷13 商 3 余り 3 チビ余り: c3 = 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 商 s1 余り a1
  2q に対して 2q÷p 商 s2 余り a2
  3q に対して 3q÷p 商 s3 余り a3
  4q に対して 4q÷p 商 s4 余り a4
  ………
  Hq に対して Hq÷p 商 sH 余り aH
《あ》のように書くなら:
  《い》 1q = ps1 + a1
  《う》 2q = ps2 + a2
  《え》 3q = ps3 + a3
  ………
  《か》 Hq = psH + aH

これら H 個の余り a1, a2, …, aH が、前回のように
  m 個のチビ余り c1, c2, c3, …, cm
  n 個のデカ余り d1, d2, d3, …, dn
に分類されたとする。全部のチビ余りを足し合わせたものを大文字の C で表すことにする:
  C = c1 + c2 + … + cm
同様に、全部のデカ余りを足し合わせたものを大文字の D で表すことにする:
  D = d1 + d2 + … + dn
《い》から《か》までの全部の余りの和 a1 + a2 + … + aH は、もちろん C + D に等しい。ついでに H 個の商の和を大文字の S で表すことにしよう:
  S = s1 + s2 + … + sH

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

さらに、《い》から《か》までの全部の右辺の和を考える(余りの和が C + D に等しいことを利用):
  (ps1 + a1) + (ps2 + a2) + … + (psH + aH)
  = ps1 + ps2 + … + psH + a1 + a2 + … + aH
  = p(s1 + s2 + … + sH) + C + D
  = pS + C + D  ←【右】

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

一方、デカ余りを(p から引く方法で)小さくしたもの(前回の【2】)と、チビ余りを合わせると:
  《く》 c1, c2, …, cm, p − d1, p − d2, …, p − dn
この余りたちは、全体として
  《け》 1, 2, 3, …, H
を並び替えたものになるのだった(前回の【3】)。《く》は順序の違いを無視すれば《け》と同じなので、《く》の全部の数を足し合わせたもの…
  c1 + c2 + … + cm + pn − (d1 + d2 + … + dn)
  = 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 ≡ (p2 − 1)/8 (mod 2)  ← (p+1)(p−1) を展開すると p2−1

結局、3 以上の素数 p が与えられたとき、もし (p2 − 1)/8 が偶数なら 2 は mod p において平方剰余、(p2 − 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) ≡ qH (mod p)。ここで H = (p − 1)/2。

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

第三に、ガウスの補題からの発展として、q が奇数という条件なら、L(q, p) = (−1)S とも書ける(【9】参照)。ここで S は、チビ余り・デカ余りを求めるときに発生する商の和:
  S = s1 + s2 + s3 + … + sH
この場合、というのは【8】で見たように:
  1q/p の(小数点以下の)端数を切り捨てたものが s1
  2q/p の端数を切り捨てたものが s2
  3q/p の端数を切り捨てたものが s3
  ………
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)12 = 1 となり 9 は mod 11 において平方剰余。…これは説明のための例で、9 = 32 が平方数(従って平方剰余)ってことは、初めから分かり切っている。

【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 未満の増加とはいえ、結果的に整数部分が 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)12 = 1。実際 r = 8 が r2 ≡ 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 = s1 + s2 + … + sH を構成する項として、同じ一つの値(それを y としよう)の項が何回反復するか?が問題だった(【13】の例参照)。その重大な手掛かりとして、値が y に増える直前の項を sx とすると、《と》によって、その項の番号 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項 s1 から始まるので、第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 を持つ。

〔念のための解説〕 この手の計算では、「並んでる物の個数」と「間隔の個数」の区別が重大。例えば、99~102ページは合計4ページだが、102 − 99 = 3 と計算すると、実際のページ数より 1 小さい。また例えば、4本の桜の木 A1, A2, A3, A4 が並んで立ってるとして、桜は 4 本あるが、桜と桜の間のスペースは A1~A2, A2~A3, A3~A4 の3個しかない。【14】【15】の考え方は次の通り…。今、桜の木のそれぞれに、和 S 同様の「値」があるとして、例えば、A1 = 13, A2 = 14, A3 = 14, A4 = 15 だとしよう。すると、桜1番が値「14」未満の最後の桜、桜3番が値「15」未満の最後の桜で、値「14」の桜の本数は「値○○未満の最後の桜」の番号同士を引き算して 3 − 1 = 2 となる。…値「14」の最後の桜の番号から、まだ値「14」になっていない最後の桜の番号を引き算することは、間隔を数えることなので、引き算の結果は、計算に関連する桜(A1, A2, A3)の総数(つまり 3)より 1 小さい。ところが「まだ値14になっていない最後の桜」(A1)は、「値14の桜の数」のカウントに含めてはいけないので、1 小さくてちょうどいい。

もし値「14」の最後の桜の番号から、値「14」の最初の桜の番号を引き算すると、数えようとしているものより 1 小さくなってしまう。値「14」の最後の桜の番号から、値「13」の最後の桜の番号を引き算すれば、うまくいく。

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

ここで「小計」というのは…。例えば、値「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  HI の定義より
  だから 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)27 = −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 の平方剰余か。すなわち r2 ≡ 7 (mod 19) を満たす r が存在するか。r = 8 のとき r2 = 64 は 19 の倍数 57 より 7 大きいのだから、答えはYes。すると、ひっくり返した問い「19 は mod 7 の平方剰余か?」は、確かめるまでもなく、逆の答えNoとなる。…確認として r2 ≡ 19 (mod 7) を満たす r は存在しない: 19 ≡ 5 (mod 7) なので、r2 ≡ 5 (mod 7) を考えても同じことだが、r = ±1, ±2, ±3 のどれを試しても、r2 はそれぞれ 1, 4, 9 ≡ 2 (mod 7) なので ≡ 5 にはならない。[実は 19 ≡ 5 ≡ −2 (mod 7)。第二補充法則との関連において、「法の素数が春・夏のときに限って −2 が平方剰余」ってことを証明してあるので(第二補充・後編【16】)、「mod が冬素数 7 の場合には −2 は非剰余」と直接判定できる。

*

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

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

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

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

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

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

まず《は》右辺の L(5, 1847) つまり r2 ≡ 5 (mod 1847) の解の有無だが、それを調べるために、約900種類の r の可能性を一つずつ試すのは、あまり優雅ではない。ところが 5 はバニラ素数なので、
  L(5, 1847) = L(1847, 5)
…と、そのままひっくり返すことができる。これで問題は r2 ≡ 1847 (mod 5) の解の有無に帰着され、1847 ≡ 2 (mod 5) なので、要するに r2 ≡ 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)  ← 4は平方数(22 ≡ 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
すなわち、r2 ≡ 365 (mod 1847) は解を持つ*6…と結論される。

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

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

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

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

平方剰余の相互法則・ガウスの第三証明
◆オリジナル Theorematis arithmetici demonstratio nova 下記の69ページ~
https://gdz.sub.uni-goettingen.de/download/pdf/PPN35283028X_0016_1NS/LOG_0041.pdf
 <英訳>
https://archive.org/details/sourcebookinmath1929smit 112ページ~(PDF版)
https://archive.org/details/sourcebookinmath00smit (PDF版とDjVu版)
 <ドイツ語訳>
https://gdz.sub.uni-goettingen.de/download/pdf/PPN373456743/LOG_0014.pdf
◆ディリクレによる解説 Vorlesungen über Zahlentheorie 96ページ~
https://archive.org/details/vorlesungenber00lejeuoft
◆アイゼンシュタインによる簡単化 Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste
https://www.digizeitschriften.de/download/pdf/243919689_0028/log27.pdf (原論文の本文)
https://www.digizeitschriften.de/iiif/image/dzeit:243919689_0028:00000301/full/full/0/default.jpg (原論文の図版)
https://archive.org/details/abhandlungenzurg07leip (私信)
https://gdz.sub.uni-goettingen.de/download/pdf/PPN599415665_0040/LOG_0080.pdf (別のスキャン)
 <原論文の英訳>
https://archive.org/details/collmathpapers03caylrich 39ページ~
◆参考: Proofs of the Quadratic Reciprocity Law
 https://www.mathi.uni-heidelberg.de/~flemmermeyer/qrg_proofs.html
 https://www.mathi.uni-heidelberg.de/~flemmermeyer/fchrono.html
 ↑相互法則の証明を300種以上、時代順にリストアップ。

**

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

⁂

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

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

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

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

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

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

1 Disquīsītĭōnēs Ărithmētĭcaĕ [ディ クィースィー ティオーネー・アRィ メーティカェ]、しばしば D.A. または DA と略される(母音の長短を表す記号は「振り仮名」的意味で付加したもの。本来のラテン語のアルファベットの一部ではない)。

2 Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste
https://www.digizeitschriften.de/download/pdf/243919689_0028/log27.pdf

3 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 までの整数、つまり z = 1, 2, 3, 4, 5, 6 に対して zq を p で割った余りを出発点とした。アイゼンシュタインは、代わりに 1 から p − 1 までの偶数 z = 2, 4, 6, 8, 10, 12 に対して、zq を p で割った余りを考える。【1】の《ア》《イ》《ウ》に対応するものは:
  鉄ア z = 2, 4, 6, 8, 10, 12
  鉄イ zq = 20, 40, 60, 80, 100, 120
  鉄ウ a = 7, 1, 8, 2, 9, 3
ここで例えば z = 2 なら zq = 20 となり(q = 10 なので)、それを p = 13 で割ると余り a = 7 を得る。同様に z = 4 なら zq = 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 なども同様。

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

【20】 以下、「q と p は互いに素」という条件を付ける。

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

zq が p で割り切れて、余りが a = 0 になる可能性はない。というのも、p は素数なので、zq が p で割り切れるためには z または q が p で割り切れる必要がある。ところが z は 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 は z を並び替えただけ」という結論に)。その理由は下記の通り。f たちの各数と g たちの各数はそれぞれ合同なので、一方に重複がなければ他方にも重複がなく、過不足が起きない――そこで f たちの中に重複がないことを示す。

今 zq = 2q, 4q, 6q, …, (p − 1)q を p で割った余りをそれぞれ a1, a2, a3, … aH として、こう書くことにする(q と p は互いに素):
  2q ≡ a1 (mod p) → a1 が偶数なら f1 = a1、奇数なら f1 = −a1
  4q ≡ a2 (mod p) → a2 が偶数なら f2 = a2、奇数なら f2 = −a2
  6q ≡ a3 (mod p) → a3 が偶数なら f3 = a3、奇数なら f3 = −a3
  ………
  (p − 1)q ≡ aH (mod p) → aH が偶数なら fH = aH、奇数なら fH = −aH

これら H 個の a たちの中に、合同なものが重複して含まれてないのは明らか: 例えばもしも a2 ≡ a3 になったとすると、それは 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 ――それを fi と fj とする――が符号だけ逆だとすれば、ai ≡ −aj (mod p) となり、移項すると:
  ai + aj ≡ 0 (mod p) つまり ai + aj は p の倍数
けれど ai も aj も「2 以上 p − 1 以下の偶数」なので、両者の和は「4 以上 2p − 2 以下」。この範囲にある p の倍数は p 自身だけなので、上の条件は
  ai + aj = p
を意味する。この左辺は偶数の和で偶数、右辺は仮定により奇数(の素数)――この等式はあり得ない!

この議論は、ガウス/ディリクレ版【2】に対応する。

【21】 結局、z の数も g の数も、順序の違いを無視すれば 2, 4, 6, …, p − 1 を過不足なく 1 個ずつ含んでいる。さらに、g の各数は f の各数と合同。よって、ガウス/ディリクレ版と同様、z の各数の積と f の各数の積は合同:
  鉄サ 2⋅4⋅6…(p−1) ≡ f1f2f2…fH (mod p)
一方、2q ≡ a1, 4q ≡ a2, … なので、それらの左辺同士・右辺同士の積を考えると:
  2q⋅4q⋅6q…(p−1)q ≡ a1a2a3…aH つまり
  鉄シ 2⋅4⋅6…(p−1) qH ≡ a1a2a3…aH (mod p)

ここで a たちの一つ一つとそれに対応する各 f の関係は、もし a が偶数なら f = a で、奇数なら f = −a だった。アイゼンシュタインは、これを
  f = (−1)aa  ← (−1)a が符号部分(a の正負)を表す
と表現した。例えば a が偶数 4 なら、符号部分は (−1)4 = +1 なので f = a となる。また例えば a が奇数 3 なら、符号部分は (−1)3 = −1 なので f = −a となる。この考え方を使うと、
  f1 = (−1)a1a1, f2 = (−1)a2a2, …
なので、鉄サの右辺は:
  (−1)a1a1 × (−1)a2a2 × (−1)a3a3 × … × (−1)aHaH
  = (−1)a1(−1)a2(−1)a3…(−1)aH (a1a2a3…aH)
  = (−1)a1+a2+a3+…+aH (a1a2a3…aH)

簡潔に A = a1 + a2 + a3 + … + aH と置くと、上の値はこうなる:
  (−1)A (a1a2a3…aH)
従って、鉄サは:
  2⋅4⋅6…(p−1) ≡ (−1)A (a1a2a3…aH)
これを鉄シの左辺に代入すると:
  鉄ス (−1)A (a1a2a3…aH) qH ≡ a1a2a3…aH (mod p)

a1, a2 などは、素数 p 未満(の偶数)なので、p と互いに素。だから、鉄スの両辺を a1a2a3…aH で割ることが許される。それを実行すると:
  鉄セ (−1)A qH ≡ 1 (mod p)

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

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

鉄セによれば、(−1)A と qH の積は ≡ 1 なので、これら二つの値は、一方が ≡ 1 なら他方も ≡ 1、一方が ≡ −1 なら他方も ≡ −1 でなければならない。q が mod p の平方剰余か非剰余かに応じて L(q, p) を 1 ないし −1 とすると、オイラーの基準によれば L(q, p) ≡ qH (mod p) だが、上記の観察によれば、この qH の代わりに (−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)30 = 1、つまり 10 は mod 13 の平方剰余(ガウスの補題【1】の例題参照)。

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

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

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

一方、この先で使われる幾何学的議論は見事なもので、現代でも多くの教科書で、アイゼンシュタインのアイデアが利用されている。上記の補題からその有名な部分への過程でも、アイゼンシュタインは「なるほど!」と思わせるエレガントな議論(知名度は高くないかもしれないが)を行った。(続く)


<メールアドレス>