メモ(数論9): ガウスの第一証明の森

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

数論(メモ)の目次

***

2022-09-23 ガウスの第一証明・ディリクレの工夫 イントロ

平方剰余の相互法則についての Gauß の第一証明は、発想は壮大だが、実装は強引で「スパゲティ」(ごちゃごちゃ)ともいえる。

Dirichlet(ディリクレ)は、そのごちゃごちゃを整理して、証明を半分くらいに短縮した。Dirichlet の工夫は、大ざっぱに言えば Jacobi(ヤコビ)記号を使うこと。それだけでなく Jacobi 記号の「分母」として 1 や負数を許容する…。今で言う Kronecker(クロネッカー)記号に当たるが、Dirichlet がこれをやったのは、Kronecker 記号が導入される数十年前らしい!

現代では Gauß の第一証明自体も、その Dirichlet 版も、ほとんど紹介されない。そのため歴史的文脈が見通しにくいが、面白い冒険コースであることは間違いない。残念ながら本題に入るまでの準備が長く、いろいろなことが絡み合って見通しが悪いのだが…

【1】 −1 の逆数は −1 自身: (−1)−1 = 1/(−1) = −1。この結果として、任意の整数 c について
  (−1)c = (−1)−c
が成り立つ。早い話、(−1) の整数乗は、偶数乗なら = +1 で奇数乗なら = −1。これについては、正の偶数・負の偶数の区別、正の奇数・負の奇数の区別は関係ない。従って a, b を任意の整数として
  (−1)ab
のような値があるとき、指数の符号を反転させて (−1)−ab としても値は変わらないし、指数の任意の因子の符号を反転させて (−1)a(−b) などとしても値は変わらない。普段あまり使わない発想かもしれないが、内容的には当たり前。

さて Q を 3 以上の(従って奇数の)素数、a をある整数として、2次の合同式 x2 ≡ a (mod Q) に解 x があるかないか。もし a ≡ 0 なら x ≡ 0 という1種類の解がある。それ以外の場合、解があるとすれば2種類の解があり、解がないとすれば全く解がない――前者のケース(2種類の解あり)は平方剰余だが、これを L(a, Q) = 1 で表し、後者のケース(解なし)を平方非剰余(略して非剰余)と呼び L(a, Q) = −1 で表すことにする。この L は Legendre(ルジャンドル)記号と呼ばれるもので、一般的には「分数に丸かっこを付けた形」で表される。例えば x2 ≡ 3 (mod 13) には x ≡ ±4 という解があるから:
  ( 3 13 ) = 1

↑大抵のブラウザでうまく表示されるはずだが、分数のようなものをウェブページで表現するのは、結構手間がかかる。JavaScript を利用すれば割と簡単にできるし、画像にして貼り付ける手もあるが、面倒なので、ここではこれを L(3, 13) = 1 のように書く。

a ≡ 0 という特殊な場合については、L(a, Q) = 0 としよう。すると、この L という関数は「2次方程式における判別式のようなもの」とも解釈できる。値が +1 なら2種の解、値が 0 なら1種の解、値が −1 なら解なし。…これは、2次方程式の「判別式の正負」と「実数解の数」の関係に似ている。

a ≡ 0 の特殊ケース(a が Q で割り切れる)を度外視すると、この「判別式」の具体的な値は、オイラーの基準によって計算される(結果はガウスの補題とも等しい)。

【2】 Legendre 記号を使うと、平方剰余の相互法則は L(p, Q) L(Q, p) = (−1)[(p−1)/2][(Q−1)/2] と表現される。ここで p, Q は 3 以上の相異なる素数。指数については、もちろん分数の掛け算をして (p−1)(Q−1)/4 と書いても構わない。

Jacobi 記号は、Legendre 記号 L(a, Q) を拡張したもので、「Q が3以上の素数」という制限を緩め「Q は3以上の任意の奇数」としたもの。その定義の仕方は単純で、Q が
  Q = p1p2p3…pn
のように n 個の(必ずしも相異ならない)素数の積に分解されるとき、Jacobi 記号(以下 J で表す)を…
  J(a, Q) = L(a, p1) L(a, p2) L(a, p3) … L(a, pn)
…と定める。Q は3以上の奇数なので、p たちも、それぞれ3以上の素数。

〔例〕 例えば J(2, 15) というのは L(2, 3) と L(2, 5) の積…というわけ(Q = 15 = 3 × 5, p1 = 3, p2 = 5)。

〔注意〕 n = 1 の場合、つまり Q が1個の素数 p1 に等しい場合、J(a, Q) = J(a, p1) = L(a, p1) となり、この場合、Jacobi 記号と Legendre 記号は、全く同じ意味を持つ。

Jacobi 記号は、Legendre 記号と同じ相互法則・補充法則を満たし、J は L 同様「乗法的関数」となる: 例えば Q が3以上の素数のとき、L では
  L(−2, Q) = L(−1, Q) L(2, Q)
のような「分解」が成り立つが(形式的には分数の計算 −2/Q = −1/Q × 2/Q に似ている)、同じような計算が J においても、成立する(J においては、Q は「3 以上の素数」とは限らず、「3 以上の任意の奇数」に拡張されている)。…この点は説明・証明が必要だが、後回しにして、ここではこの性質を事実と認めておく。

【3】 Dirichlet は、この Jacobi 記号をさらに拡張し、「分母」に当たる Q が 1 でも良いとし、そればかりか「分子」が正なら「分母」が負の奇数でも良いとした。この件については、とりあえず次のように理解できる。

a と b を正とすると、Jacobi 記号の相互法則から、
  J(a, b) J(b, a) = (−1)[(a−1)/2][(b−1)/2]  ①
となり、第一補充法則(の Jacobi 版)と組み合わせると、
  J(−a, b) J(b, a) = J(−1, b) × J(a, b) J(b, a) = (−1)(b−1)/2 × (−1)[(a−1)/2][(b−1)/2]
  = (−1)[1 + (a−1)/2][(b−1)/2] = (−1)[(a+1)/2][(b−1)/2]
となるが、右端の指数の因子 [(a+1)/2] は正の偶数ないし正の奇数。それを −1 倍すると、負の偶数ないし負の奇数になるが、偶・奇は変わらない。従って【1】で見たように、指数を −1 倍しても、最終結果が (−1) の偶数乗か奇数乗か?という結論には影響しない。つまり、こう書き換えることができる:
  J(−a, b) J(b, a) = (−1)[(−a−1)/2][(b−1)/2]  ②
  ↑ [(a+1)/2] を、−1 倍の [(−a−1)/2] に置き換えた

一方 ① の正の数 a を、形式的に負の数 −a に置き換えると:
  J(−a, b) J(b, −a) = (−1)[(−a−1)/2][(b−1)/2]  ③
②と③の右辺は同一だから、②と③の左辺が同一であると考えても、少なくとも相互法則に関する限り、問題はないだろう。すなわち b が正であるという条件においては:
  J(b, a) = J(b, −a)  ④
と考えることができそうだ。

そこで、④を定義とすると…。②が成り立つ以上、定義④から必然的に③も成り立つ。「分子・分母」の両方が正の場合にはもちろん相互法則が成り立つのだが、一方が正で他方が負の場合にも、Jacobi 記号の相互法則がそのまま成り立つことになる!

最後に Jacobi 記号の乗法的性質に照らすと、④について、右辺を「分解」してJ(b, a) = J(b, a) J(b, −1) と書ける。その両辺を J(b, a) で割ると J(b, −1) = 1 となり、再び④を使うと J(b, 1) = 1 となる。これによって Jacobi 記号は、「分母」が ±1 の場合にも拡張される。

上記の議論では b が正という条件が付くが、「分母」が Q = +1 の場合については、例えば次のように理解することもできる:
  Q = 3n = 3 × 3 × … 3 のとき定義から J(b, Q) = J(b, 3n) = L(b, 3) × L(b, 3) × … × L(b, 3) = [L(b, 3)]n
  だから Q = 1 = 30 なら J(b, Q) = J(b, 30) = [L(b, 3)]0 = (±1)0 = +1

【4】 これらの形式的議論の実質的意味は、今のところ不透明だが、重要な伏線として…。Legendre 記号と違い、Jacobi 記号は、もはや純粋な「判別式」ではない。つまり J(a, b) = 1 だからといって x2 ≡ a (mod b) に解があるとは限らない。例えば、L(2, 3) = −1, L(2, 5) = −1 は簡単に直接確認できるし、第二補充法則からも明らかだが、Jacobi 記号の定義によると
  J(2, 15) = L(2, 3) L(2, 5) = (−1)(−1) = 1
となる。Legendre 記号の感覚だと、一見 2 が mod 15 の平方剰余のように見えるが、その解釈は正しくない。

実際、mod 15 では (±1)2 ≡ 1, (±2)2 ≡ 4, (±3)2 ≡ 9, (±4)2 ≡ 1, (±5)2 ≡ 10, (±6)2 ≡ 6, (±7)2 ≡ 4 なので、2は非剰余。

〔注意〕 J(a, b) の b が3以上の素数なら、J と L は全く同じことなので、J も L も同じ意味での「判別式」。けれど、拡張版である J では b が素数とは限らない。b が素数でない場合、J はもやは純粋な「判別式」ではなく、一般的には「複数の判別式の積」のようなものになる。

「単純に判別式のように解釈できるかどうか」という解釈問題を別にすれば、形式的に J は L の上位互換であり、従って J の相互法則を証明することで L の相互法則も証明される。そして第一証明に関する Dirichlet の工夫を理解するためには、Jacobi 記号のさらなる拡張 がかなめとなる――そこにおいては、正負を問わず任意の奇数が「分母」になることができる。

この説明だけでは、何が何だか分からないかもしれないけど、実際の証明本体に取り組みながら、真意を探っていきたい。(続く)

⁂

2022-09-20 連続する3個の整数の積は6で割り切れる 連続するN整数の積は…

以下の内容はたわいもないことだが、ガウスの第一証明はここから始まる。

【1】 連続する3整数、例えば 4, 5, 6 の積 4 × 5 × 6 = 120 は、3! = 1 × 2 × 3 = 6 で割り切れる。

理由。1, 2, 3 の中には偶数(つまり2の倍数)が1個しかない。連続する3整数は、順に「偶数・奇数・偶数」か「奇数・偶数・奇数」なので、どちらにしても2の倍数を1個含む(場合によっては2個含む)。

同様に 1, 2, 3 の中には3の倍数が1個しかない。他方、連続する3整数 A, A+1, A+2 の中にも、必ず3の倍数が1個含まれている。

A を 3 で割ると、余りは 0, 1, 2 のどれか。つまり A は 3k, 3k+1, 3k+2 のどれかの形を持つ(k は整数)。もし A = 3k なら、もちろんそれは3の倍数。もし A = 3k+1 なら A+2 = 3k+3 = 3(k+1) が 3 の倍数。最後に、もし A = 3k+2 なら A+1 = 3k+3 = 3(k+1) が 3 の倍数。…要するに、任意の連続3整数は、順序の違いを無視すれば mod 3 で {0, 1, 2} と合同。

すると A(A+1)(A+2) / 3! の分母にある因数は 2, 3 が1個ずつだけだが、この分数の分子には、必ず因子として 2 が 1個以上、3 が1個あるので、通分すると分母は 1 になる。

【2】 より一般的に、連続する N 整数の積は、N! で割り切れる。理由は上記と同様。N! の積を作っている整数たち…
  1, 2, 3, 4, … , N  ①
…の中には、2 の倍数が N/2 個(端数切り捨て)、3 の倍数が N/3 個(端数切り捨て)、4 の倍数が N/4 個(端数切り捨て)…しか含まれていないが、任意に選択された連続 N 整数…
  A+1, A+2, A+3, A+4, …, A+N  ②
…の中には、2の倍数・3の倍数・4の倍数などが、それぞれ①と比べて少なくとも同数含まれている。

〔注〕 説明の便宜上、ここでは連続N整数の最初の数を A+1 とする(【1】ではそれを A とした)。

2の倍数について言うと、もし②が奇数から始まっていれば、列①と列②には、2の倍数が同じ個数含まれる。どちらも「奇数・偶数・奇数・偶数…」となるから。けれど、もし②が偶数から始まっていて、しかも N が奇数の場合、①は奇数から始まって奇数で終わるのに対して、②は偶数から始まって偶数で終わることになり、この場合、②の方が偶数を1個多く含む:
  例  ① = 1, 2*, 3, 4*, 5 vs. ② = 4*, 5, 6*, 7, 8*
この例では 4 の倍数も、①には1個しかないが、②には2個含まれる。

このように、数列の中にある数 b の倍数が何個含まれているか?というと、①については N/b 個(端数切り捨て)に限られるが、②に含まれる b の倍数の個数は、それと同数か、またはそれより1個多い。

【3】 ②の最初の数が ≡ 1 (mod b) ならば――言い換えると b で割って 1 余る数ならば(要するに A が b の倍数ならば)――、②に含まれる b の倍数の個数は、①に含まれる b の倍数の個数と等しい。例えば
  ① = 1, 2, 3, 4, 5*, 6, 7 vs. ② = 6, 7, 8, 9, 10*, 11, 12
は、どちらも5で割って1余る数から始まっていて、同じ順序で5の倍数*が現れるので、「含まれる5の倍数の個数」は正確に一致。これは「数列の先頭から数えて、4回待った後でようやく5の倍数が出現するパターン」であり、仮に5の倍数が多ければ多いほど「良い」とするなら、「最も悪い」配置に当たる。逆に「最も良い」のは、全然(あるいはほとんど)待たずに 5 の倍数が現れるパターン:
  例 = 10*, 11, 12, 13, 14, 15*, 16 あるいは 9, 10*, 11, 12, 13, 14, 15*
これらの例も「連続7整数」という点には変わりないが、5の倍数が1個多く含まれる!

1 から始まる整数の列というのは、どんな数 b の倍数について考えても、その出現の頻度については最も不利。例えば 13 の倍数は、12回も待った後でようやく出現する。一方、任意の数から始まる数列は、最悪の場合でも、それと同様の配置なので「含まれる b の倍数の個数」は同じ。最悪でない場合、例えば 13, 14, 15, … のように、いきなり13の倍数から始まる可能性だってある。いったん、まとめると…。
  数列 A+1, A+2, A+3, A+4, …, A+N
に含まれる 2 の倍数・3の倍数・4の倍数など(一般に b の倍数)の個数は、
  数列 1, 2, 3, 4, …, N
に含まれる 2 の倍数・3の倍数・4の倍数など(一般に b の倍数)の個数と比べて、それぞれ最悪でも同じ。だから、
  N! = 1 × 2 × 3 × … × N の積を作る N 整数の中に b の倍数が○個含まれてるとすると、
  (A+1)(A+2)(A+3)…(A+N) の積を作る N 整数の中にも b の倍数が○個以上含まれる。
「b の倍数」の b が何であろうと同じことが言えるので、
  [(A+1)(A+2)(A+3)…(A+N)] / N!
という分数は、割り切れて、整数になる。分子と分母で b を約分すると、分子の b の個数は分母の b の個数以上なので、分母の b は全部消滅する。

【4】 説明としては、だいたいそんなもんで十分だろうけど、例えば 100! には具体的に因子 3 が何個含まれているのか?

端数切り捨てを E() で表すことにすると E(100/3) = 33 だから、1 から 100 までの整数の中に、3の倍数が33個あることは言うまでもない。

しかし、これらの整数の中には、9 = 32 や 18 = 2⋅32 のように、因子 3 を複数個含んでいるものもある。具体的に、9 の倍数には、それ以外の3の倍数にはない「2個目の因子3」が含まれている。1 から 100 の範囲の 9 の倍数は E(100/9) = 11。だから 100! は、少なくとも E(100/3) + E(100/9) = 33 + 11 = 44 回、3で割れる。

話がどこに行くのかは、見当がつくだろう…。27 = 33 の倍数には「3個目の因子3」があり、81 = 34 の倍数には「4個目の因子3」があるので、それらを追加すると:
  100! に含まれる因子3の合計個数 = E(100/3) + E(100/32) + E(100/33) + E(100/34) = 33 + 11 + 3 + 1 = 48

どうして E(100/34) で止まっていいのか? E(100/35) 以降は考えなくていいのか?

考えたければ考えてもいいのだが、35 = 343 の倍数はこの範囲にはないので、端数切り捨ての結果 E(100/343) = 0 となる。0 なので、足しても足さなくても結果には影響しない。

従って、100! = 1 × 2 × 3 × … × 100 は、3 で48回割り切れるが、49回は割り切れない: 100!/348 は整数だが、100!/349 は整数ではない。

同様に考えると、100! は…2 で
  E(100/2) + E(100/4) + E(100/8) + E(100/16) + E(100/32) + E(100/64) = 50 + 25 + 12 + 6 + 3 + 1 = 97 回
割り切れる。
  5 では E(100/5) + E(100/25) = 20 + 4 = 24 回
  7 では E(100/7) + E(100/49) = 14 + 2 = 16 回
割り切れる。11 以上の各素数 p では、E(100/p) 回、割り切れる―― p2 > 100 なので、E(100/p2) = 0 以降は結果に影響しない。特に、50~100 の範囲での素数では、1 回しか割り切れない。結局:
  100! = 297⋅348⋅524⋅716
   × 119⋅137⋅175⋅195⋅234⋅293⋅313⋅372⋅412⋅432⋅472
   × 53⋅59⋅61⋅67⋅71⋅73⋅79⋅83⋅89⋅97

【5】 今、比較的大きい自然数 N が与えられたとしよう。例えば N = 12。次に、比較的小さい2個の自然数 a, b があって、N = a + b としよう。例えば a = 5, b = 7, N = 12 = a + b。このとき:
  N! / (a! × b!) は割り切れて整数になる
…上記の例で言えば:
  (1 × 2 × 3 × … × 12) / [(1 × 2 × 3 × 4 × 5) × (1 × 2 × 3 × 4 × 5 × 6 × 7)] は割り切れる

理由。分子 12! に含まれる因子 2 の個数は E(12/2) + E(12/4) + E(12/8) = 6 + 3 + 1 = 10。一方、分母のうち…
  5! に含まれる因子 2 の個数は E(5/2) + E(5/4) = 2 + 1 = 3
  7! に含まれる因子 2 の個数は E(7/2) + E(7/4) = 3 + 1 = 4
  合計7個
分母側には、因子 2 が10個もあるのだから、約分すれば分子側の因子 2 は全滅し、商は素因数 2 を3個含むだろう。

これと同様のことが、分母・分子両方に含まれる各素因数 p について言える。分子に含まれる p の個数は:
  E(12/p) + E(12/p2) + E(12/p3) + …
一方、分母に含まれる p の個数は:
  E(5/p) + E(5/p2) + E(5/p3) + …
  + E(7/p) + E(7/p2) + E(7/p3) + …

より一般的に N = a + b のとき N! / (a! × b!) の分子に含まれる素因数 p の個数は:
  E(N/p) + E(N/p2) + E(N/p3) + …
一方、分母に含まれる p の個数は:
  E(a/p) + E(a/p2) + E(a/p3) + …
  + E(b/p) + E(b/p2) + E(b/p3) + …

〔注〕 無限に続く足し算のような書き方になっているが、実際にはある項から先は全部 0 なので、その時点で(あるいは 0 になる直前の項で)計算は打ち切られる。

これを証明するには、項ごとに比較して
  E(N/p) ≥ E(a/p) + E(b/p)
  E(N/p2) ≥ E(a/p2) + E(b/p2)
  E(N/p3) ≥ E(a/p3) + E(b/p3)
  etc.
を示せばいい。ある正の素数 p の一定の自然数乗を q とすれば、これらの不等式は次の一つの不等式に要約される:
  E(N/q) ≥ E(a/q) + E(b/q)  ‥‥③
この不等式を示せば、「分母の因数は常に分子の因数以下なので、約分すると分母は全部キャンセルされて、分数は整数になる」と結論される。

このことは日常の話として、直観的に理解可能。お買い上げ100円ごとに福引券が1枚もらえるとしよう。例えば、合計520円の買い物をすれば券が5枚もらえる。250円の商品Aと270円の商品Bを買ったような場合だ。ところが、AとBを2回に分けて別々に精算すると、福引券は2枚ずつ、計4枚しかもらえず、1枚「損をする」。…このように、端数切り捨てってのは、切り捨ての機会が多ければ多いほど、「損をする」可能性が増えるもの。運良く損をしないとしても、逆に得をするってことはあり得ない(まとめて1回だけの端数切り捨てなら、最悪でも99円分の損だが、2回の端数切り捨てだと最悪99円×2の損が発生)。「100円ごと」を「q 円ごと」に置き換えても、話は同じ。まとめて1回だけ端数切り捨てが起きる E(N/p) に比べると、E(a/q) + E(b/q) は最良でも「等しい」、最良でなければ「より小さい」。

0 以上の(必ずしも整数ではない)実数 x について、端数を切り捨てたもの――言い換えれば x の整数部分――を E(x) とした。切り捨てられる端数(小数部分)を F(x) とすれば:
  x = E(x) + F(x) ただし 0 ≤ F(x) < 1
すると証明したい不等式③に関連して、次の等式が成り立つ:
  N = a + b なので、その両辺を q で割ると
  N/q = a/q + b/q つまり端数まで正確に考慮すれば等号が成り立ち
  E(N/q) + F(N/q) = E(a/q) + F(a/q) + E(b/q) + F(b/q)  ‥‥④

右辺 a/q + b/q の項ごとの小数部分の和 F(a/q) + F(b/q) は、0 以上 1 未満か、1 以上 2 未満かのどちらか。もし前者なら、それは a/q + b/q = N/q 全体の小数部分と一致する:
  F(N/q) = F(a/q) + F(b/q)
このとき E(N/q) = E(a/q) + E(b/q) となり、③の両辺は等しい(従って、不等号 ≥ は正しい)。

一方、もし F(a/q) + F(b/q) が 1 以上 2 未満の場合、定義上 F(N/q) は 1 未満なので、
  F(N/q) < F(a/q) + F(b/q)
この不等式を等式④の両辺から引くと:
  E(N/q) > E(a/q) + E(b/q)
となり、③の左辺の方が大きい(従って、やはり不等号 ≥ は正しい)。より正確に言うと、この場合、③の左辺は右辺よりちょうど 1 大きい。

〔例〕 q = 51 = 5 とする。N = 12, a = 5, b = 7 について:
  E(12/5) = E(5/5) + E(7/5) つまり 2 = 1 + 1
については、等号が成り立つ。このとき F(5/5) + F(7/5) = 2/5 は 1 未満。一方、同じ N, a, b でも q = 22 = 4 とすると:
  E(12/4) > E(5/4) + E(7/4) つまり 3 > 1 + 1
については、左辺の方が大きい。このとき F(5/4) + F(7/4) = 1/4 + 3/4 = 1 は 1 以上。

E(a/q) + E(b/q) と2項に分けて、2回、端数の切り捨てが行われた場合、切り捨てられる端数の合計が 1 以上になる可能性がある(たくさん捨てられて損をする)。一方 E((a+b)/q) = E(N/q) のように、一つにまとめてから端数を切り捨てると、切り捨てられる小数部分は必ず 1 未満なので、そのような「損」が発生することはない。

【6】 上記の N! / (a! × b!) が必ず割り切れ、整数になること…。例えば
  (1 × 2 × 3 × … × 12) / [(1 × 2 × 3 × 4 × 5) × (1 × 2 × 3 × 4 × 5 × 6 × 7)]
が割り切れるということは、その分母分子を (1 × 2 × 3 × 4 × 5) で約分すれば、
  (6 × 7 × 8 × 9 × 10 × 11 × 12) / (1 × 2 × 3 × 4 × 5 × 6 × 7) = (6 × 7 × 8 × 9 × 10 × 11 × 12) / 7!
が割り切れるということで、これは「連続N整数の積は N! で割り切れる」という最初の観察の別証明に他ならない。

【7】 (参考) 「組み合わせ」からの見方。例えば (3 × 4 × 5 × 6)/4! = (6 × 5 × 4 × 3)/4! = 15 というのは、6個の物(例えば、みかん・りんご・バナナ・梨・桃・いちごが1個ずつある)から4個を選ぶパターンの数に当たる。ただし選ぶ順序については区別しない: 「みかん・りんご・バナナ・いちご」「みかん・バナナ・いちご・りんご」「みかん・バナナ・りんご・いちご」などなどは、どれも同じ4個を選んだと解釈。

実際、6個の物の中から、最初の1個を選ぶ方法は、明らかに6種類の可能性がある。それを選び終わった後では、5個の物しか残っていないので、そこから1個を選ぶ方法は5種類。それを選んだ後では、4個の物しか残っていないので、そこから1個選ぶ方法は4種類。そして最後に、まだ選ばれていない3個のどれを選んでもいいので、選択肢は3種類。単純計算で 6 × 5 × 4 × 3 パターンの選び方がある。

ところが、上記の単純計算では、「みかん・りんご・バナナ・いちご」「みかん・バナナ・いちご・りんご」のように、「選ぶ順序が違うだけで、最終的に選ばれた4個は同じ」というケースが重複してカウントされてしまう。それを修正するためには、最終的に選ばれた4個が一定として(例えば「みかん・りんご・バナナ・いちご」として)、その4個を選ぶ方法が何通りあるか考えるべきだろう。それは、相異なる4個のものを並べるパターンなので、もちろん 4! 種類。結局、
  ・単純計算で 6 × 5 × 4 × 3 パターンの選び方
  ・選ぶ順序の違いを区別しないで、最終結果だけを考えるなら 4! 分の1
  ・だから選ぶ順序の違いを区別しないなら 6 × 5 × 4 × 3 / 4! パターン
これは「選び方のパターン数」なので、必ず整数になる。

より一般的に M 個のものから N 個のものを選ぶ方法の数は(選ぶ順序を区別しないとすると)
  M(M−1)(M−2)…(M−(N−1)) / N!
のようになって、分子も分母も連続 N 個の整数だが、分子については M から降順に N 個を考えている(もちろん M と N は自然数で M は N 以上とする)。この分数が常に割り切れて整数を表すのだから、それを別の角度から言うと、1 以上の任意の数 A について、「A から連続 N 個の昇順の整数の積」は N! で割り切れる。

【8】 (参考2) 「2項係数」からの見方。「組み合わせ」の数は「2項係数」でもある(なぜ?)。

2 / 1! = 2
  (x+y)2 = x2 + 2xy + y2
の係数として現れる。

3 × 2 / 2! = 3
  (x+y)3 = x3 + 3x2y + 3xy2 + y3
の係数として現れる。

4 × 3 × 2 / 3! = 4 と 4 × 3 / 2! = 6
  (x+y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
の係数として現れる。

5 × 4 × 3 × 2 / 4! = 5 と 5 × 4 × 3 / 3! = 10
  (x+y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5
の係数として現れる。

6 × 5 × 4 × 3 × 2 / 5! = 6 と 6 × 5 × 4 × 3 / 4! = 15 と 6 × 5 × 4 / 3! = 20
  (x+y)6 = x6 + 6x5y + 15x4y2 + 20x3y3 + 15x2y4 + 6xy5 + y6
の係数として現れる。

一般に (x+y)n を展開したとき、各項の係数は 1 以上の整数なので、上記のような形の分数は割り切れる。

⁂

2022-09-12 無味乾燥だが超絶技巧 第一証明の森の入り口

平方剰余の相互法則について、ごく一般的なガウスの第三証明を紹介した。今度は、あまり人気のないガウスの第一証明を紹介したい。

あえてこの険しい道を行く意味は、次第に明らかになるだろう。

無味乾燥な補助定理から…。その内容は平凡で「4k+1型の素数 Q が与えられたとき、Q より小さい奇素数の中には Q mod q が非剰余になるような q が少なくとも一つある」。言ってることは当たり前。大ざっぱなイメージとして、平方剰余になるか非剰余になるかは「半々の確率」だが、素数は無限にある。例えば Q = 53 未満の奇素数は14個、Q = 101 未満の奇素数は24個…。Q = 53 未満の奇素数 q の一つ一つを mod として、確率半々で Q が剰余または非剰余になるとすれば、そのどれも非剰余にならない確率は「コインを14回投げて、一度も裏が出ない(連続して表が出る)ようなもの」で、ありそうにない

実際のデータは次の通り。R で剰余、N で非剰余を表すと、8個が剰余、6個が非剰余:
53N3, 53N5, 53R7, 53R11, 53R13, 53R17, 53N19,
53N23, 53R29, 53N31, 53R37, 53N41, 53R43, 53R47

ガウスも「一見とても明白だと思われ、ある人々は実際、証明の必要性を認めなかったのであるが…」とコメントしている。その言い回しからも分かるように、厳密性のためには、ここから始める必要がある。

定理(Gauß D.A. Art. 125–129) 任意のバニラ素数 Q に対して、Q が mod q の非剰余になるような、3 以上 Q 未満の素数 q が存在する。

バニラ素数(4k+1型)は、春素数(8k+1型)と秋素数(8k+5型)に分けられる。秋素数 Q が、必ず自分より小さいどれかの素数 q の非剰余になることは、簡単に示される。

以下、Legendre 記号を L(A, B) で表す(A と B を相異なる3以上の素数として、A が mod B の平方剰余なら L(A, B) = 1、非剰余なら = −1 とする)。

1. Q ≡ 5 (mod 8) の場合。

奇数 Q − 2 は ≡ 3 (mod 8) なので、必ず8k±3型の素因数を少なくとも一つ含む。

もしも Q−2 の素因数が全部 ≡ ±1 (mod 8) なら、それらの積も ≡ ±1 (mod 8) になり、Q−2 ≡ 3 (mod 8) という事実に反する。

Q − 2 の8k±3型(つまり8k+3型 or 8k+5型)の素因数の一つを q とすると:
  第二補充法則により L(2, q) = −1
一方 Q − 2 ≡ 0 (mod q) つまり Q ≡ 2 (mod q) だから:
  L(Q, q) = L(2, q)
上記のようにこの値は −1 に等しい。これは Q が mod q の非剰余であることを意味する。□

〔例〕 最初の 4 個の秋素数(8k+5型)は 5, 13, 29, 37:
Q = 5 のとき Q−2 = 3 は、8k+3型の素因数 3 を含む。 L(5, 3) = L(2, 3) = −1 だから Q = 5 は mod 3 の非剰余。
Q = 13 のとき Q−2 = 11 は、8k+3型の素因数 11 を含む。 L(13, 11) = L(2, 11) = −1 だから Q = 13 は mod 11 の非剰余。
Q = 29 のとき Q−2 = 27 = 33 は、8k+3型の素因数 3 を含む。 L(27, 3) = L(2, 3) = −1 だから Q = 29 は mod 3 の非剰余。
Q = 37 のとき Q−2 = 35 = 5 × 7 は、8k+5型の素因数 5 を含む。 L(37, 5) = L(2, 5) = −1 だから Q = 37 は mod 5 の非剰余。

2. Q ≡ 1 (mod 8) の場合。

Gauß による手品のような証明。Dirichlet の Zahlentheorie §50 に沿って紹介する。Gauß 自身、「ずいぶん長い間、努力を逃れた定理」(=なかなか努力が実らなかった・証明に苦労した)と告白している。Dirichlet は「極度に鋭敏な考察」とコメント。

Q 未満のとある(正の)奇数 2m+1 を考える。2m+1 以下のどの奇素数を法としても Q は平方剰余…と仮定する。このとき、2 以上 2m+1 以下のどの整数 n も、素因数として「2m+1 以下の素数(ここでは 2 を含めていう)」またはその「べき」だけを含むので、mod n においても Q は平方剰余。ゆえに Q は M = (2m+1)! を法としても平方剰余であり、r2 ≡ Q (mod M) を満たす r が存在。

〔例〕 Q = 409, 2m+1=5 とすると 5 以下のどの奇素数(つまり 3, 5)を法としても Q は平方剰余: 409 ≡ 12 (mod 3), 409 ≡ 22 (mod 5)。Q は8k+1型なので、mod 2 や mod 4 でも平方剰余: 409 ≡ 12 (mod 2 or 4)。ゆえに 409 は M = 5! = 1⋅2⋅3⋅4⋅5 = 120 を法としても、平方剰余。例えば 72 = 49, 132 = 169, 172 = 289 はどれも ≡ 409 (mod 120) なので、上記の r として 7 や 13 などを選ぶことができる。

M は、2m+1(それは素数 Q より小さい)以下の自然数の積なので、Q と互いに素。従って r と M も互いに素

r2 ≡ Q (mod M) なので r2 − Q = Mの倍数、つまり Q = r2 − Mの倍数。もしも r と M がどちらもある素数 s の倍数なら、Q も s の倍数でなければならない。これは M と Q が互いに素という事実に反する。上の例で M = 1⋅2⋅3⋅4⋅5 と r = 7 or 13 は互いに素である。

r2 ≡ Q (mod M) という事実を使って、r(Q − 12)(Q − 22)(Q − 32)…(Q − m2) という積を考えると:
  r(Q − 12)(Q − 22)(Q − 32)…(Q − m2) ≡ r(r2 − 12)(r2 − 22)(r2 − 32)…(r2 − m2)
  ≡ r[(r − 1)(r + 1)][(r − 2)(r + 2)][(r − 3)(r + 3)]…[(r − m)(r + m)] (mod M)
これは r − m から r + m までの全整数の積なので、並び替えると:
  ≡ (r − m)…(r − 3)(r − 2)(r − 1)r(r + 1)(r + 2)(r + 3)…(r + m)
この数は連続 2m+1 個の整数の積なので、(2m+1)! つまり M で割り切れる。

〔注意〕 これが割り切れるということを言うために、「連続N整数の積は N! で割り切れる」という命題が必要になる。

〔例〕 Q = 409, 2m+1=5, m = 2, r = 17 の場合、r−m からの5整数の積 A = 15⋅16⋅17⋅18⋅19 が M = (2m+1)! = 5! = 1⋅2⋅3⋅4⋅5 で割り切れる。

割られる積の因子のうち r は M と互いに素なので、割り切れるかどうかと無関係。因子 r を除去した積 B = (Q − 12)(Q − 22)(Q − 32)…(Q − m2) もまた (2m+1)! で割り切れる。

上の例では B = (409−12)(409−22) = 165240 が M = 5! で割り切れる。

M = (2m+1)(2m)(2m−1)(2m−2)…3⋅2⋅1 =
(m+1) [(m+2)m] [(m+3)(m−1)] [(m+4)(m−2)]…[(2m+1)1] =
(m+1) [(m+1)2 − 12] [(m+1)2 − 22] [(m+1)2 − 33]…[(m+1)2 − m2] なので:

B/M = {1/(m+1)} {(Q−12)/[(m+1)2 − 12]} {(Q−22)/[(m+1)2 − 22]} {(Q−32)/[(m+1)2 − 33]}…{(Q−m2)/[(m+1)2 − m2]}

上の例では B/M = (1/3)[(409−12)/(32−12)][(409−22)/(32−22)] = 1377。

上の B/M は無条件で必ず整数になるわけではない。√Q の端数を切り捨てた整数を m とすると:
  m < √Q < m+1 従って Q < (m+1)2
この m に対しては、B/M の式の各 {} 内は、分子より分母が大きい分数、つまり 1 より小さい正の有理数: この場合 B/M は整数ではない。

しかも √Q と Q の大きさの差は、Q が大きくなればなるほど広がる。素数ではないが仮に Q = 9 とすると既に:
  7 = 2√9 + 1 < 9
従って、春素数が生じる Q ≥ 17 の場合、このような m の設定は、常に条件 2m+1 < Q を満たす:
  2m + 1 < 2√Q + 1 < Q

要するに、もしも 2m+1 以下の全素数に対して Q が平方剰余なら、上の B/M が整数になるはずだが、2m+1 がある程度大きい場合には――具体的には √Q の端数を切り捨てた整数を m とした場合には――、B/M は決して整数にならない。すなわち 2m+1 がこの大きさの場合、もはや「それ以下のどの素数を法としても Q は平方剰余」ということは不可能。

結論として、Q が8k+1型の素数のとき、2√Q + 1 より小さい範囲には、必ず L(Q, q) = −1 を満たすような奇素数 q が、少なくとも一つ存在する。□

〔コメント〕 この定理は、ガウスの第一証明において理論上不可欠な役割を果たすが、数値的にはかなり緩い評価だ。8k+1型の素数のうち、Q = 53881 は、19 以下の任意の奇素数 p に対し L(Q, p) = 1 となる最小の例だが、ガウスの評価では、この Q に対して 2√53881 + 1 ≈ 465 より小さい範囲に L(Q, q) = 1 を満たす素数 q が存在…となる。実際には、はるかに小さい範囲にそのような q が存在する(q = 23 は mod Q の非剰余)。ちなみに:
78992 ≡ 3, 120862 ≡ 5, 32582 ≡ 7, 152392 ≡ 11, 49352 ≡ 13, 50432 ≡ 17, 108902 ≡ 19 (mod 53881)

⁂

文献

Disquīsītiōnēs Arithmēticae

数論の歴史上、最も重要な出版物ともいえる。体系的理論としての現代の数論は、ここから始まった。しばしば単に Disquisitiones と呼ばれる。DA, D.A., Disq. Arith. などとも略される。ディ クィースィーティオーネー・アリ[rɪ]メーティカェ、arithmetic の disquisitions。…Dis- は discussion の dis- と同じで「異なる意見を闘わせる=細かく検討する」。dis-quisitio は dis-quiro の名詞形で、英語の in-quiry と似ていて、コンピューター用語の query とも同系。

disquīsītiō のように tiō で終わる語は女性名詞で、屈折するとき tiōn-is のように n が付く(英語の -tion に相当)。

◆オリジナル(ラテン語) https://archive.org/details/disquisitionesa00gaus
 ↑一つのPDFとしてダウンロード可能だが重い。ブックマークなし。DjVu版なし。
別のスキャン https://www.e-rara.ch/zut/content/structure/1254642
 ↑分割されているが軽い。ページ単位のブックマークあり。
さらに別のスキャン https://edoc.hu-berlin.de/handle/18452/1163
 ↑一つのPDF。軽い。ブックマークなし。
https://gdz.sub.uni-goettingen.de/download/pdf/PPN235993352/PPN235993352.pdf
 ↑全集版・第1巻(1863)※。ガウス自身のメモが巻末に収録されている。軽い。章ごとのブックマーク付き。
https://archive.org/details/werkecarlf01gausrich
 ↑全集版・第1巻・第2版(1870)。こちらの方がスキャンが高品質。軽いDjVu版あり。
書き起こし(一部) https://la.wikisource.org/wiki/Disquisitiones_arithmeticae
◆フランス語訳 https://archive.org/details/recherchesarithm00gaus
 ↑DjVu版あり。
書き起こし https://fr.wikisource.org/wiki/Recherches_arithm%C3%A9tiques
◆ドイツ語訳※ https://gdz.sub.uni-goettingen.de/download/pdf/PPN373456743/PPN373456743.pdf
 ↑ガウスの数論関係の論文も同時収録。脚注付き。一括だが軽い。章単位のブックマークあり。
◆スペイン語訳(テキストベース・軽量)
https://web.archive.org/web/20210603153444/http://elaprendiz.es/disquisitionesarithmeticae_Gauss.pdf

約200年遅れで比較的最近英訳も出たが、まだパブリックドメインになっていないので自由に参照できない。

※ ゲッティンゲン大学のウェブサイトの資料のうち、
https://gdz.sub.uni-goettingen.de/id/PPN235993352
は全集版(ラテン語原文)、
https://gdz.sub.uni-goettingen.de/id/PPN373456743
はドイツ語訳。どちらについても、章ごとなどの分割ダウンロードが可能(要JavaScript)。右上の Ansicht から Export を選択後、「PDFs für einzelne Elemente」ボタンをクリックすると、分割ダウンロード用のリストが表示される。ボタンより上にある「PDF download」は全体を一つのPDFとしてダウンロードしたい場合(ブラウザ内でPDFが開いてしまう環境の場合、ブラウザ自体にダウンロードの選択肢があるはず=右クリックメニューなど)。ドイツのオンライン・ライブラリーは、このインターフェースに統一されていることが多い。

〔参考〕 Gauss なのか Gauß なのか? どちらでも同じ意味。現代ドイツのドイツ語の正書法では、原則として長い母音・二重母音の後ろの ss を ß と書く。これは「ベータ」ではなく、もともとは ſs の合字(リガチュール)であり、エスツェットと呼ばれる。その前半の ſ は s の変種。だから Gauſs と書いてもいい(古いドイツ語の論文ではこの表記も)。ガウスは、ドイツ語ではなくラテン語で著述したのだから、ドイツ語の正書法ではなくラテン語の正書法で Gauss とするのが正しい!という考え方もあるかもしれない。ところが、少し前まで、ラテン語でも ſ の文字が結構よく使われていた。しかもガウス本人もサイン(署名)するとき、ſs を使っていたようだ。…というわけで、あまり細かいことにこだわらず「同じ意味の異字体」「フォントの問題」「どっちでもいい」と解釈するのが吉だろう。

Dirichlet (& Dedekind): Vorlesungen über Zahlentheorie

フォァレー[leː]ズンゲン[ŋən]・ウュバー・ツァーレン[lən]・テオリー[ʁiː]

ページ数などを記す場合、第4版による。こちらも約200年遅れで比較的最近英訳が出たものの、結構、誤字(誤植)が多く、全訳ではない上、まだパブリックドメインになっていないので自由に参照できない。

Dirichlet (1863, 4th ed. 1894):
https://archive.org/details/vorlesungenber00lejeuoft
DjVu版が便利。

(2nd ed.):
https://gdz.sub.uni-goettingen.de/download/pdf/PPN30976923X/PPN30976923X.pdf
第2版のスキャンには、セクションごとにブックマークがあり便利。

〔参考〕 語源と関係ないが Dirichlet の名前を正しく書くトリック: Di に続けて rich (金持ち)、let (させる)と覚えると間違いがない。語末の t を発音しないのは Fermat 同様、なんとなくフランス語っぽい名前だが、名前の本人はドイツ語圏の人だった。

平方剰余の相互法則・ガウスの第一証明

初出はDA。上記 Vorlesungen では Dirichlet による簡単化について解説されている。Dirichlet 版の原論文は:

Crelle, Bd. 47 (1854): Über den ersten der von Gauß gegebenen Beweise des Reciprocitätsgesetzes in der Theorie der quadratischen Reste.
https://www.digizeitschriften.de/download/pdf/243919689_0047/log10.pdf (3 MiB) または
https://gdz.sub.uni-goettingen.de/download/pdf/PPN243919689_0047/LOG_0010.pdf (20 MiB)
全集版 Über den ersten der von Gauss gegebenen Beweise des Reciprocitätsgesetzes in der Theorie der quadratischen Reste.
https://www.e-rara.ch/zut/content/zoom/5613392
https://www.e-rara.ch/download/pdf/5688113

フランス語訳 (1859): Sur la première démonstration donnée par Gauss de la loi de réciprocité dans la théorie des résidus quadratiques
http://portail.mathdoc.fr/JMPA/PDF/JMPA_1859_2_4_A37_0.pdf

平方剰余の相互法則・ガウスの第三証明

◆オリジナル 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
https://archive.org/details/vorlesungenber00lejeuoft (第4版、96ページ~)
https://gdz.sub.uni-goettingen.de/download/pdf/PPN30976923X/PPN30976923X.pdf (第2版、§43(94ページ)~)
 ↑第4版のスキャンのPDF版は重い。DjVu版は軽量。
◆アイゼンシュタインによる簡単化 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種以上、時代順にリストアップ。


<メールアドレス>