メモ（数論9）: 相互法則の第一証明 - 長く険しい道

チラ裏　＞　数論　＞　メモ9

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

ドイツ語圏では有名だが、日本語圏・英語圏では知名度の低い Dirichlet バージョン。綱渡りのような証明。

• 2022-09-23　ガウスの第一証明・ディリクレ版　初めに　イントロ
• 2022-09-26　ガウスの第一証明・平方剰余の場合（前編）
• 2022-09-30　ガウスの第一証明・平方剰余の場合（中編）
• 2022-10-02　ガウスの第一証明・平方剰余の場合（後編）
• 2022-10-08　ガウスの第一証明・非剰余の場合　ディリクレ版をさらに簡単化
• 2022-09-12　ガウスの第一証明・「超絶技巧」補助定理
• 2022-09-20　連続する3個の整数の積は6で割り切れる　連続するN整数の積は…

2022-09-23　ガウスの第一証明・ディリクレ版　初めに　イントロ

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

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

Gauß の第一証明は、発想は壮大だが、実装は強引で「スパゲティ」（ごちゃごちゃ）ともいえる。

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

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

【1】　−1 の逆数は −1 自身: (−1)⁻¹ = 1/(−1) = −1。この結果として、任意の整数 w について
　　(−1)^w = (−1)^−w
が成り立つ。

〔例〕　w = 15 とすると (−1)¹⁵ = (−1)^3 × 5 = ((−1)³)⁵ と書けるが、同様に…
　　(−1)¹⁵ = (−1)⁻¹⁵
…が成り立つ。なぜなら、その右辺について
　　(−1)⁻¹⁵ = (−1)^−1 × 15 = ((−1)⁻¹)¹⁵
と書けるが、前述の通り (−1)⁻¹ = −1 なので、上の式の右端の数は (−1)¹⁵ に等しい。

早い話、(−1) の整数乗は、偶数乗なら = +1 で奇数乗なら = −1。これについては、正の偶数・負の偶数の区別、正の奇数・負の奇数の区別は関係ない。従って u, v を任意の整数として
　　(−1)^uv
のような値があるとき、指数の符号を反転させて (−1)^−uv としても値は変わらないし、指数の任意の因子の符号を反転させて (−1)^(−u)v あるいは (−1)^u(−v) などとしても値は変わらない。普段あまり使わない発想かもしれないが、内容的には当たり前。

【2】　さて Q を 3 以上の（従って奇数の）素数、a をある整数として、2次の合同式 x² ≡ a (mod Q) に解 x があるかないか。もし a ≡ 0 なら x ≡ 0 という1種類の解がある。それ以外の場合、解があるとすれば2種類の解があり、解がないとすれば全く解がない――前者のケース（2種類の解あり）を平方剰余と呼び、この状況を L(a, Q) = 1 で表す; 後者のケース（解なし）を平方非剰余（略して非剰余）と呼び L(a, Q) = −1 で表す。この L(?, ?) は Legendre（ルジャンドル）記号と呼ばれるもので、一般的には「分数に丸かっこを付けた形」で表される。例えば x² ≡ 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次方程式の「判別式の正負」と「実数解の数」の関係に似ている。

この「判別式」の具体的な値は、理論的にはオイラーの基準によって計算される。相互法則が証明された後では、オイラーの基準を使うまでもなく、全てが第一・第ニ補充法則に帰着される。

【3】　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 = p₁p₂p₃…p_n
のように n 個の（必ずしも相異ならない）素数の積に分解されるとき、Jacobi 記号（以下 J で表す）を…
　　J(a, Q) = L(a, p₁) L(a, p₂) L(a, p₃) … L(a, p_n)
…と定める。Q は3以上の奇数なので、p_○ たちも、それぞれ3以上の素数。

〔例〕　例えば J(2, 15) というのは L(2, 3) と L(2, 5) の積…というわけ（Q = 15 = 3 × 5, p₁ = 3, p₂ = 5）。

〔注意〕　n = 1 の場合、つまり Q が1個の素数 p₁ に等しい場合、J(a, Q) = J(a, p₁) = L(a, p₁) となり、この場合、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 以上の任意の奇数」に拡張されている）。…この点は説明・証明が必要だが、後回しにして、ここではこの性質を事実と認めておく。

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

a と b を 3 以上の奇数とすると、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]}　　③

〔解説〕　②右辺 = ③右辺 の関係は、【1】で見た (−1)^uv = (−1)^(−u)v に当たる: ②の指数の因子 u = [(a+1)/2] を③では −u = [(−a−1)/2] に置き換え、もう一方の因子 v = [(b−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 = 3ⁿ = 3 × 3 × … 3 のとき定義から J(b, Q) = J(b, 3ⁿ) = L(b, 3) × L(b, 3) × … × L(b, 3) = [L(b, 3)]ⁿ
　　だから Q = 1 = 3⁰ なら J(b, Q) = J(b, 3⁰) = [L(b, 3)]⁰ = (±1)⁰ = +1

【5】　容易に直接確認できることとして、a = ±1 の場合にも、上記の定義の下で相互法則が成り立つ。実際、a = 1 ならもちろん J(1, b) = 1、そして上記定義より J(b, 1) = 1。だから、事実として J(1, b) J(b, 1) = 1 になるはずだが、そのことは、相互法則の公式と（少なくとも形式的には）整合性がある:
　　J(1, b) J(b, 1) = (−1)^{[(1−1)/2][(b−1)/2]} = (−1)⁰ = 1
一方、a = −1 なら第一補充法則から J(−1, b) = (−1)^(b−1)/2、そして上記定義より J(b, −1) = 1。だから、事実として J(−1, b) J(b, −1) = (−1)^(b−1)/2 になるはずだが、相互法則の公式からも同じ結論が得られる:
　　J(−1, b) J(b, −1) = (−1)^{[(−1−1)/2][(b−1)/2]} = (−1)^{−[(b−1)/2]} = (−1)^[(b−1)/2]
ここでは【1】の考え方を使い、w = −[(b−1)/2] について (−1)^w を (−1)^−w で置き換えた。

【6】　これらの形式的議論の実質的意味は、今のところ不透明だが、重要な伏線として…。Legendre 記号と違い、Jacobi 記号は、もはや純粋な「判別式」ではない。つまり J(a, b) = 1 だからといって x² ≡ 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 の平方剰余のように見えるが、Jacobi 記号の世界では、その解釈は正しくない。

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

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

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

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

2022-09-26　ガウスの第一証明・平方剰余の場合（前編）

平方剰余の相互法則のガウスの第一証明は直線的で、第三証明のガウスの補題のような「天下り的」な面は全くない。発想自体は、むしろこっちの方が分かりやすい。いよいよ証明本体に突入し、冒険を始めたい。

Q を 7 以上の素数として、S を 3 以上 Q 未満の素数たちの集合とする。もしも次の命題が証明されたら、何が起きるだろうか？

命題X　集合 S の任意の（相異なる）2個の素数の間において相互法則が成り立つなら（仮定）、S に含まれる任意の素数 p と Q の間でも相互法則は成り立つ（結論）。

まず S = {3, 5} とすると、L(3, 5) = L(5, 3) が正しいことを容易に直接確認できるので、Q = 7 に対して、命題Xの仮定は満たされる。よって命題Xが正しいとすると、3 と 7 の間、5 と 7 の間にも、それぞれ相互法則が成り立つことになり、相互法則が成り立つ範囲が
　　S = {3, 5, 7}
に拡大。すると、今度は Q = 11 に対して命題Xの仮定が満たされるので、命題X によって、Q = 11 と {3, 5, 7} の任意の一つの間にも、相互法則が成り立つことになる。従って、法則が成り立つ範囲が
　　S = {3, 5, 7, 11}
に拡大。すると、今度は Q = 13 に対して命題Xの仮定が満たされるので…

…と以下同様に進んで、結局、無限の範囲の任意の素数に対して、相互法則が成り立つことになる！

言われてみると、非常にシンプルで当たり前の発想だが、さすがはガウス（？）、すごいことを考えるな…。優等生的な（？）人は「ああ、帰納法の一種ね」としたり顔で言うかもしれないが（確かに数学的帰納法に分類されるだろう）、命題Xを実際に証明するには、サーカスのような手順が必要となる。概念的には、任意の 2 素数 p, q < Q に対して
　　L(p, q) L(q, p) = (−1)^{[(p−1)/2][(q−1)/2]}
が成り立つことだけを使って、
　　L(p, Q) L(Q, p) = (−1)^{[(p−1)/2][(Q−1)/2]}
を導けばいい。しかし p と Q は、それぞれ4k+1型素数・4k+3型素数に分かれ、それによって相互法則の振る舞いが変わるので p と Q の組み合わせだけで4パターンが生じ、その各パターンについて、p が mod Q の平方剰余の場合・非剰余の場合があるので、合計8種類のパターンについて L(p, Q) と L(Q, p) の関係を考えなければならない。8種類の可能性を一つずつ細かく検討するだけでも、忍耐力と力技が要求されるのだが、より根源的な困難として、非剰余の場合には「解がないこと」を出発点に、結論を導かねばならない。解があるのなら x² ≡ p (mod Q) を満たす x が存在するので、それを e とすると…みたいに議論を進めることができるが、解がない場合、話の進めようがないように思える。ガウスがこの壁をどうやって突破したか？は、第一証明の最大の見どころだろう。

ディリクレは巧妙な議論によって、8種類のパターンを2種類に圧縮した。mod Q で R が平方剰余の場合、非剰余の場合――この二つだけを考えればいい。ガウスのオリジナルに比べると、ずいぶん歩きやすい（実際には、それでも険しいのだが…）。このディリクレ版第一証明は、ディリクレ＆デデキントの古典的教科書に掲載されているため、ドイツ語圏では知名度が高く、原論文はフランス語にも訳されているのでフランス語圏でもそれなりに知られているようだが、英語圏・日本語圏ではあまり知られていないと思われる。

日本語圏では、高木の名著――ディリクレの講義をベースに、（当時としては）さらに新しい成果を取り入れた――が昔からあるものの、高木の本には第一証明は収録されていない。「クロネッカー記号をきちんと導入せずに、場当たり的にヤコビ記号の分母を負にするのは、好ましくない」という趣旨のことを、高木は明記している（初等整数論講義、第二版、299ページ）。確かに Dirichlet の証明は危うい綱渡りのような感じもするが、それはそれで面白いし、刺激的でもある。一方、英語圏では、そもそもディリクレの講義が翻訳されたのが、200年近く遅れて結構最近の1999年。これでは知名度が低いのも、無理はない。実は G. B. Mathews という英国人が、1892年、高木より前にディリクレの講義をベースにした英語の教科書を出しているものの、この人も高木同様、分母が負になるのを回避し、ディリクレのオリジナルを直接は紹介していない。そしてもちろん英語圏での数論の古典といえば Hardy & Wright。それに比べれば Mathews なんて誰も知らない…というのが実情だろう。

というわけで、歴史に埋もれているディリクレ版を現代の立場から再検討・再評価してみたい！

§1.1　mod Q において素数 p が非剰余でも、−p は平方剰余になることがある。次の二つのケースに大別される。

• ケース1　「平方剰余の場合」
  • ケース1a　Q が4k+3型素数の場合: p or −p が mod Q の平方剰余。
  • ケース1b　Q が4k+1型素数で、p が mod Q の平方剰余の場合。
• ケース2　「非剰余の場合」
  • p も −p も mod Q の平方非剰余。Q が4k+1型素数に起きることがあるパターン。

説明の便宜上、1a と 1b に分けているが、Dirichlet の論法では、この二つはまとめて処理される。

1a の場合、mod Q において p か −p のどちらか一方が平方剰余、他方が非剰余。

なぜなら Q についての仮定から L(−1, Q) = −1 なので（第一補充法則）、L(p, Q) と L(−p, Q) = L(−1, Q) L(p, Q) は符号が反対。

1b の場合（つまり mod Q において p が平方剰余の場合）、実は −p も平方剰余。

なぜなら、この場合 L(−1, Q) = 1 なので、L(p, Q) と L(−p, Q) = L(−1, Q) L(p, Q) は符号が同じ。

イントロ【4】③で見たように、J(p, Q) J(Q, p) でも J(−p, Q) J(Q, −p) でも、相互法則は同じ形式なので、p or −p のどちらか一方について、mod Q での相互法則を証明できれば、実質的に命題Xが証明される。そこで 1a の場合、p or −p のうち mod Q の平方剰余になる方を R とする。

〔例〕　Q = 7 とすると p = 3 の場合 L(3, 7) = −1, L(−3, 7) = +1 なので、−p つまり −3 が R になる。実際、x² ≡ R (mod Q) つまり x² ≡ −3 (mod 7) が解を持つ: x ≡ ±2。
Q = 11 とすると p = 3 の場合 L(3, 11) = 1 なので p 自身つまり 3 が R になる。実際、x² ≡ R (mod Q) つまり x² ≡ 3 (mod 11) が解を持つ: x ≡ ±5。

p が4k+1型の場合、p が平方剰余なら −p も平方剰余（ケース1b）、p が非剰余なら −p も非剰余（ケース2）…という状況。ケース2については後回しにして、以下の議論には（p が4k+1型の場合については）ケース1bだけを含める。その際、R として ±p のどちらを選択しても構わないのだが、どっちでもいいのにわざわざ負を選ぶのも面倒なだけ――この場合、素直に R = p としておこう。

まとめると、p が4k+1型素数のとき、変数 R というのは p 自身の別名に過ぎない（R = p は mod Q での平方剰余…と仮定している）。p が4k+3型素数のとき、R は ±p のどちらか一方で、mod Q での平方剰余になる側の符号が選択される。仮定から L(R, Q) = 1。 Q は素数なので、ヤコビ記号でも全く同じ意味:
　　【ア】　J(R, Q) = 1

証明したいことは、相互法則…
　　【イ】　J(R, Q) J(Q, R) = (−1)^{[(R−1)/2][(Q−1)/2]}　（証明したい結論）
…命題Xと同様に考えて、絶対値 Q 未満の範囲では、既に相互法則が成立している…という仮定だけを使って【イ】を証明できればいい。

〔参考〕　実はヤコビ記号を使うことで少し有利になって、絶対値 Q 未満の因子の積については（積の値が Q より大きくても）既に相互法則が成立している…と仮定することが許される。ヤコビ記号は、ルジャンドル記号の積として定義されるから（そして Q 未満の範囲では L の相互法則が成り立つと仮定しているから）。この事実は、証明の後半「非剰余の場合」において重大な意味を持つ。

【ア】を【イ】に代入すると、結局、次を証明すればいい:
　　【ウ】　J(Q, R) = (−1)^{[(R−1)/2][(Q−1)/2]}　（証明すべきこと）

§1.2　R は mod Q の平方剰余…と仮定しているので、x² ≡ R (mod Q) を満たす x が存在する。解 x は2種類あるが、そのうち 0 以上 Q 未満の範囲にある偶数の解を e とする。すなわち:
　　【エ】　e² ≡ R (mod Q)

「必ずこの範囲の偶数の解を選べること」を示すのは易しい。末尾（§1.3）の補足説明【1】参照。

【エ】は e² − R ≡ 0 (mod Q) という意味なので、e² − R は Q の倍数。すなわち、ある整数 f があって、こう書ける:
　　【オ】　e² − R = Qf

この f は 1 以上 Q 未満の正の奇数。

その理由については、補足説明【2】参照。この範囲制限は重大な意味を持つ: 奇数であるから f をヤコビ記号の分母にでき、しかも絶対値 Q 未満であるから、帰納法の仮定の有効範囲に入ってくれる。

実はこの f が p で割り切れるかどうかで、話が変わってくる。割り切れるケースは後回しにして、以下では「f は p で割り切れない」と仮定する。

さて、式【オ】には e² という平方数が含まれている。これを利用して、【オ】から幾つかの平方剰余の関係について、情報が得られる。

そのためには、どれかの項を消去すべく、【オ】の両辺を mod f, mod Q, mod Qf あるいは mod |R| で考えればいいのだが（このうち R は負の数かもしれないので、法は正という建前上、絶対値記号を付けておく）、mod Q での平方剰余の関係については、出発点の【ア】の仮定そのものなので、新しい情報が得られない。mod f と mod |R| の二つが有用な選択肢となる（mod Qf は単に mod Q と mod f の積なので、この場合、役立たない）。他方、同じ【オ】を mod 4 で考えることが非常に役に立つ。

第一に【オ】の両辺を mod f で考えると:
　　e² − R ≡ 0 (mod f)
　　e² ≡ R (mod f)　つまり R は平方剰余だから
　　【カ】　J(R, f) = 1

J(a, b) = 1 は、a が mod b の平方剰余であるための必要条件だが、十分条件ではない。つまり J(a, b) = 1 だからといって、a が mod b の平方剰余であるとは限らない。この点は L と J の重大な違いである。けれど逆に、a が mod b の平方剰余であるなら、必ず J(a, b) = 1 となる。【カ】では、この関係において a = R, b = f としたもの。

〔注意〕　もしも p が f で割り切れると、R = p or −p も f で割り切れて、【カ】は特殊ケースの J(R, f) = 0 になってしまうように思えるかもしれない。しかしながら |R| = p は素数なので、その（正の）約数は 1 と p 自身に限られる。f = 1 の場合、拡張されたヤコビ記号において【カ】は意味を持つ。f = p の可能性については、f は p で割り切れないという仮定によって、事前に排除されている。

R は Q 未満の素数 p またはその符号を変えたものなので、絶対値 Q 未満であり、帰納法についての仮定から R と f の間には相互法則が成り立つ:
　　【キ】　J(R, f) J(f, R) = (−1)^{[(R−1)/2][(f−1)/2]}
【カ】を【キ】に代入すると:
　　【ク】　J(f, R) = (−1)^{[(R−1)/2][(f−1)/2]}
これは証明すべきこと【ウ】にかなり近い――【ク】の f を Q に置き換えることができれば、証明が完成する！

〔注意〕　【キ】【ク】については、もしも f が p で割り切れると、f は R = p or −p でも割り切れて、ヤコビ記号の値が 0 になってしまう。だからそのケースについては、別に考える必要がある。f が p で（従って R で）割り切れない…という仮定は以下の他の場所でも必要になるが、「割り切れない場合について考えている」ことを暗黙の了解として、いちいち断らない。

【オ】からもう一種類の平方剰余の関係を得るため、【オ】の両辺を mod p つまり mod |R| で考えてみよう:
　　e² ≡ Qf (mod |R|)　つまり Qf は平方剰余だから
　　J(Qf, |R|) = 1
Q も f も正なので Qf は正。従って、ヤコビ記号の「分母」は正でも負でも関係なくなるので、絶対値記号を外すことができる:
　　J(Qf, R) = 1　つまり　J(Q, R) J(f, R) = 1
この最後の等式が成り立つためには、J(Q, R) と J(f, R) は両方 +1 になるか、または両方 −1 になる必要がある（一方が +1 他方が −1 だと上の等式は不成立）。つまり両者は等しい:
　　【ケ】　J(Q, R) = J(f, R)
【ケ】を【ク】に代入すると:
　　【コ】　J(Q, R) = (−1)^{[(R−1)/2][(f−1)/2]}

【コ】は、証明すべきこと【ウ】にますます近い――【コ】右辺の指数に含まれる f を Q に置き換えられること（置き換えても右辺の値が変わらないこと）さえ示せれば、目的地【ウ】に到達する！

問題は (−1) の偶数乗なのか奇数乗なのかの区別だから、要するに、【ウ】の指数 [(R−1)/2][(Q−1)/2] と、【コ】の指数 [(R−1)/2][(f−1)/2] の偶・奇が同じであることを示せばいい。

そのためには、式【オ】を mod 4 で考えるのが早道となる。e は偶数なので e² は 4 の倍数、mod 4 では ≡ 0 となって消滅:
　　【サ】　−R ≡ Qf (mod 4)

Dirichlet は、ここでちょっとトリッキーなことをするのだが（§1.5）、もっと分かりやすい（？）ショートカットを思い付いたので、先にそっちを紹介する: 正または負の素数 R が4k+1型の場合、R−1 = 4k は 4 の倍数なので [(R−1)/2] は偶数であり、【ウ】の指数 [(R−1)/2][(Q−1)/2] と、【コ】の指数 [(R−1)/2][(f−1)/2] は、どちらも偶数――この場合、Q と f について検討するまでもなく、問題の指数はどちらも偶数乗で一致！

一方、R が4k+3型つまり4k−1型の場合、それは R ≡ −1 (mod 4) ということなので −R ≡ 1 (mod 4) となり、これを【サ】に代入すると Qf ≡ 1 (mod 4)。Q も f も奇数だから、この関係が成り立つためには Q と f が両方とも ≡ 1 (mod 4) になるか、または両方とも ≡ −1 (mod 4) になる必要がある（一方が ≡ 1 他方が ≡ −1 だと積が ≡ 1 (mod 4) になり得ない）。要するにこの場合、Q と f は両方とも4k+1型か、または両方とも4k−1型; どっちだとしても [(Q−1)/2] と [(f−1)/2] の偶・奇は一致するので、問題の2種類の指数の偶・奇は一致する。すなわち、証明が完了した！

ただし、これは f が p で割り切れない場合。f が p で割り切れる場合については、別途考える必要がある。それを別にすれば、これでケース1については（1a, 1b が一挙に）攻略された。ここまでは比較的簡単だが、まだ道は長い。

§1.3　補足説明。

【1】　0 以上 Q 未満の偶数の解 e を選択できること。mod Q において、すべての整数は、0 以上 Q 未満の Q 種類の整数のどれかと合同なので、もし x² ≡ R (mod Q) に解があるとすれば、その範囲の整数の少なくとも一つが解。その解 x が偶数なら、e = x とすればいい。もしその解 x が奇数なら Q − x ≡ −x も解であり（なぜなら (−x)² = x²）、Q − x は 0 以上 Q 未満の範囲にあり、偶数。なぜなら Q は奇素数であり、この場合、仮定により x は奇数: 奇数から奇数を引けば、偶数。

〔例〕　Q = 11, R = 5: x² ≡ 5 (mod 11) の最小の正の解は x = 4。実際、4² = 16 ≡ 5 (mod 11)。この解は偶数なので、単に e = 4 とすればいい。
Q = 11, R = 3: x² ≡ 3 (mod 11) の最小の正の解は x = 5。実際、5² = 25 ≡ 3 (mod 11)。この解は奇数だが、x = −5 ≡ 11 − 5 = 6 も解なので、偶数の解 e = 6 を選択できる。実際、6² = 36 ≡ 3 (mod 11)。

【2】　f が Q 未満の正の奇数であること。【オ】を再掲すると:
　　e² − R = Qf　（【オ】再掲）

仮定によって e が偶数、R = ±p が（正または負の）奇数だから、【オ】左辺は奇数。従って、その約数 f も奇数。

しかも、この奇数 f は正。

もしも f < 0 なら【オ】の両辺は負の数、従って R は、正の数 e² よりもっと大きな正の数なので、R = −p という選択は不可能であり R = p に限られる。しかしその場合、（【オ】の両辺は Q で割り切れるので）左辺を −1 倍した正の数 R − e² = p − e² も Q で割り切れるはずだが、それは不合理: p より小さい正の数 p − e² が、p より大きい Q で割り切れるはずがない（仮定により p < Q である）。

さて f は Q 未満。なぜなら e は Q 未満の正の数なので、【オ】左辺は Q² 未満の正の数（上記のように【オ】の両辺は正である）。それに等しい右辺も Qf < Q² を満たす。この不等式の両辺を正の数 Q で割れば f < Q。

〔参考〕　次のように論じてもいい。仮定により e は Q − 1 以下、−R は最大でも −(−p) = p だが、この値も Q − 1 以下。従って【オ】について:
　　Qf = e² − R ≤ (Q − 1)² + (Q − 1) = (Q − 1)[(Q − 1) + 1]
　　つまり　Qf ≤ (Q − 1)Q　　その両辺を正の数 Q で割ると　f ≤ Q − 1

【3】　変数名について。読み比べるとき混乱がないように、違いの要点を記しておく。このメモでは p または −p のどちらかを選択して R としているが、この R に当たる文字は、Dirichlet の原論文では ϖ （パイの筆記体）、Vorlesungen では ω になっている。（大文字の P を使っても良いのだが、大文字の P と小文字の p は少し紛らわしいので、明快さを優先して R とした。）

帰納法の仮定で「絶対値 Q 未満では相互法則が成り立つ」――この文字 Q は、Dirichlet のオリジナルでは小文字の q になっている。ここで小文字の q を使うと、証明の後半で p と p′ を使うことになって、少しゴチャゴチャする; 大文字の Q を使って小文字の q を温存しておくと、後半で代わりに p と q を使え、記述が簡潔になる。

（下に続く）

2022-09-30　ガウスの第一証明・平方剰余の場合（中編）

前回 mod 4 の処理を簡易的に済ませたが、このメモでは、その部分についてもディリクレ自身の論法を紹介（重要な補題を導入）。

証明の内容を整理して、何がどうなっているのか具体例で検討する。

§1.4　われわれは今、Gauß の第一証明 Dirichlet 版の二つのケースのうち、第一のケースを扱っている。f が p で割り切れる場合を別にすると、証明は、【ウ】の指数 [(R−1)/2][(Q−1)/2] と、【コ】の指数 [(R−1)/2][(f−1)/2] の偶・奇が一致すること（＝どちらも偶数、またはどちらも奇数になること）に、帰着された。その最後の一歩として、【オ】の e² − R = Qf を mod 4 で考えたもの…
　　−R ≡ Qf (mod 4)　　【サ】再掲
…が、重要な手掛かりとなった。

−R = p or −p は、正または負の奇数（奇素数）。f は正の奇数。Q も奇数（奇素数）。前回は場当たり的なショートカットを使ったが、一般論として:

奇数の積の補題　任意の二つの奇数 u, v が uv = w を満たすとき、
　　(u−1)/2 + (v−1)/2 ≡ (w−1)/2 (mod 2)
が成り立つ。任意の二つの奇数 u, v が uv ≡ w (mod 4) を満たす場合も、全く同じ結論が得られる。u, v は正でも負でも構わない。

証明　u, v はどちらも奇数なので u−1, v−1 はどちらも偶数。…偶数には、4の倍数（4k型）と、4の倍数以外の偶数（4k+2型）の2種類があり、それぞれ2で割ると、前者は偶数（2k型）になり、後者は奇数（2k+1型）になる――例えば、4の倍数である偶数12は半分にしても偶数だが（6）、4の倍数ではない偶数14は半分にすると奇数（7）。このことを考慮すると、(u−1)/2 ないし (v−1)/2 については、u ないし v が4k+1型の奇数か、4k+3型の奇数かに応じて、それぞれ偶数か奇数かが決まる。それらの和
　　(u−1)/2 + (v−1)/2
は、「2項が両方偶数または両方奇数」なら偶数だし（偶数同士または奇数同士の和）、「片方が偶数、他方が奇数」なら奇数（偶数と奇数の和）: 言い換えると、上の和は、u, v が「両方とも4k+1型または両方とも4k+3型」なら偶数、そうでなければ奇数。整理すると、こうなる。

(i)　u, v が両方とも4k+1型または両方とも4k+3型なら:
　　u ≡ v ≡ 1 または u ≡ v ≡ 3 (mod 4)
このとき　(u−1) + (v−1) ≡ 0 + 0 または 2 + 2 ≡ 0 (mod 4)
　　両辺を2で割ると　(u−1)/2 + (v−1)/2 ≡ 0 (mod 2)　　← mod が変わる
一方　w = uv ≡ 1⋅1 or 3⋅3 ≡ 1　つまり w−1 ≡ 0 (mod 4)
　　両辺を2で割ると　(w−1)/2 ≡ 0 (mod 2)　すなわち補題は正しい。

(ii)　u, v の一方が4k+1型、他方が4k+3型なら:
　　u ≡ 1, v ≡ 3 または u ≡ 3, v ≡ 1 (mod 4)
このとき　(u−1) + (v−1) ≡ 0 + 2 または 2 + 0 ≡ 2 (mod 4)
　　両辺を2で割ると　(u−1)/2 + (v−1)/2 ≡ 1 (mod 2)
一方　w = uv ≡ 1⋅3 or 3⋅1 ≡ 3　つまり w−1 ≡ 2 (mod 4)
　　両辺を2で割ると　(w−1)/2 ≡ 1 (mod 2)　この場合も補題は正しい。

補題の仮定 uv = w が成り立つなら、その両辺を mod 4 で考えれば、もちろん uv ≡ w (mod 4) が成り立つ――この合同式を出発点の仮定としても構わない（1を引いて2で割ったとき整数になる必要があるので、u, v が奇数であることが前提）。□

☆　この補題は意外と便利で（ヤコビ記号の導入にも役立つ）、以降の議論でも何度か使うことになる。

§1.5　指数部分についての Dirichlet の論法（ちょっとトリッキーだが面白い）

上記「奇数の積の補題」を使うと【サ】の Qf ≡ −R (mod 4) から、機械的に次の合同式が得られる（Q, f, −R はどれも奇数）:
　　(Q−1)/2 + (f−1)/2 ≡ (−R−1)/2 (mod 2)　右辺を −1 倍すると（※注1）
　　【シ】　(Q−1)/2 + (f−1)/2 ≡ (R+1)/2 (mod 2)

Dirichlet の整数論講義（1863）では、【シ】の両辺を (R−1)/2 倍するというトリッキーな手が使われる:
　　[(R−1)/2][(Q−1)/2] + [(R−1)/2][(f−1)/2] ≡ [(R−1)/2][(R+1)/2] (mod 2)
この右辺は、1 違いの2整数の積なので（※注2）、偶数×奇数 = 偶数、つまり ≡ 0 (mod 2)。ところが、2項の和…
　　[(R−1)/2][(Q−1)/2] + [(R−1)/2][(f−1)/2]
…が ≡ 0 (mod 2) つまり偶数になるためには、足し合わされる2項が偶数同士、または奇数同士になることが必要:
　　[(R−1)/2][(Q−1)/2] ≡ [(R−1)/2][(f−1)/2] (mod 2)
従って、【ウ】の指数 [(R−1)/2][(Q−1)/2] と、【コ】の指数 [(R−1)/2][(f−1)/2] の偶・奇は、確かに一致する！

〔別証明〕　Dirichlet の原論文（1854）では【シ】の代わりに、次の関係が使われる:
　　【ス】　(f−1)/2 ≡ (Q−1)/2 + (R+1)/2 (mod 2)
導出法は明記されてないが、【シ】の両辺に (Q−1)/2 を足し、左辺に生じる 2[(Q−1)/2] ≡ 0 を除去したものに当たる。【コ】の指数に【ス】を代入すると:
　　[(R−1)/2][(f−1)/2] ≡ [(R−1)/2][(Q−1)/2 + (R+1)/2] ≡ [(R−1)/2][(Q−1)/2] + (R²−1)/4 (mod 2)
奇数の平方は ≡ 1 (mod 8) だから右端の (R²−1)/4 は ≡ 0 (mod 2)。上記の [(R−1)/2][(R+1)/2] が偶数、という論法と同等。

（※注1）　これは下記の単純な性質による。

mod 2 の補題　2整数 a, b について、合同式 a ≡ b (mod 2) が成り立っているとき、その左辺だけ、または右辺だけを −1 倍した合同式も、成り立つ:
　　−a ≡ b (mod 2)　も成り立つ
　　a ≡ −b (mod 2)　も成り立つ
もちろん　−a ≡ −b (mod 2)　も成り立つ（最初の式の両辺を −1 倍）

普通の式変形では「両辺を」○倍して…などとやるのだが、mod 2 の場合に限っては、左辺だけまたは右辺だけを一方的に −1 倍しても構わない（特に、左辺または右辺がマイナスだらけでゴチャゴチャしてるとき、そのマイナス記号を一掃するのに役立つ）。

証明　mod 2 の合同は「偶数 ≡ 偶数」か「奇数 ≡ 奇数」のどっちか。偶数の −1 倍は依然として偶数、奇数の −1 倍は依然として奇数なので、−1 倍しても合同式に影響しない。□

〔例1〕 4 ≡ −6 (mod 2) は正しい。このとき 4 ≡ 6 (mod 2) も正しい。

〔例2〕 (−a − b)/z ≡ c (mod 2) が成り立つなら (a + b)/z ≡ c (mod 2) も成り立つ（左辺を −1 倍した）。

（※注2）　R は奇数なので、[(R−1)/2] と [(R+1)/2] はどちらも分子が偶数、割り切れて整数。前者に 1 = 2/2 を足すと後者になるので、両者は隣り合う2整数に当たる（後者は前者より 1 大きい）。例えば:
　　 R = 11　なら　[(R−1)/2] = 10/2 = 5, [(R+1)/2] = 11/2 = 6　なので 5 と 6
　　 R = 13　なら　[(R−1)/2] = 12/2 = 6, [(R+1)/2] = 14/2 = 7　なので 6 と 7
いずれにしても、隣り合う2整数の一方は偶数、他方は奇数なので、それらの積は偶数。

§1.6　ここまでのまとめと具体例。

帰納法の仮定（大前提）　絶対値 Q 未満の範囲では相互法則が成り立つ（Q = 7 については、この事実を直接確認できる）。

証明したいこと　Q 未満の任意の素数 p について、p と Q の間でも相互法則が成り立つこと…。この証明を大きく二つのケースに分けて、第一のケースとして、R = p or −p が mod Q の平方剰余である場合を考える。

その場合には e² = R (mod Q) を満たす偶数 e が存在し、
　　e² − R = Qf　（♪）　【オ】再掲
を満たす正の奇数 f が存在する。（♪）について、f が p で割り切れないという付帯条件の下で…
　　mod f で考えると:
　　　①　J(R, f) = 1　（【カ】再掲）
　　mod |R| で考えると:　J(Qf, R) = 1　ゆえに
　　　②　J(Q, R) = J(f, R)　（【ケ】再掲）
　　mod 4 で考えると:
　　　③　−R ≡ Qf (mod 4)　（【サ】再掲）
さて R, f は絶対値 Q 未満だから、帰納法の仮定により:
　　J(R, f) J(f, R) = (−1)^m　ここで m = [(R−1)/2][(f−1)/2]
　　ゆえに①②より　J(Q, R) = (−1)^m　（☆）

証明すべき式（相互法則）は J(R, Q) J(Q, R) = (−1)ⁿ だが――ここで n = [(R−1)/2][(Q−1)/2] である――、第一のケースの仮定として R は mod Q の平方剰余だから J(R, Q) = 1 であり、証明すべき式はこう簡約される:
　　J(Q, R) = (−1)ⁿ　（★）
（★）は（☆）とほとんど同じ式。既に導かれている（☆）から（★）を示すには、指数 m と指数 n の偶・奇が一致することを言うだけでいい…。③がその鍵となる。前回やったように直接的に考えてもいいし（§1.2）、Dirichlet の小技を使ってもいい（§1.5）。

要するに、証明すべき J(R, Q) J(Q, R) = (−1)ⁿ が、帰納法の仮定の有効範囲内（既に成立している）の式
　　J(R, f) J(f, R) = (−1)^m
の問題に、帰着される（素数 Q が、絶対値 Q 未満の奇数 f に置き換わる）。結局「m と n の偶・奇が一致すること」を示せばいい。③から、その「偶・奇の一致」が示される。

具体例1　Q = 17, p = 13　

R = p = 13 は mod Q の平方剰余。実際 e = 8 は e² ≡ 13 (mod 17) を満たす（64 を 17 で割ると 13 余る）。つまり
　　e² − 13 = 17f
を満たす奇数 f が存在（f = 3）:
　　8² − 13 = 17 × 3　（♪）

① （♪）を mod f つまり mod 3 で考えると: J(R, f) = 1 すなわち J(13, 3) = 1

この場合、ヤコビ記号はルジャンドル記号と同じ。13 ≡ 1² (mod 3) は平方剰余だから、上の式については、容易に直接確認可能。

② （♪）を mod |R| つまり mod p 要するに mod 13 で考えると: J(Qf, R) = 1 すなわち J(17 × 3, 13) = 1。従って J(Q, R) = J(f, R) すなわち J(17, 13) = J(3, 13)

17 ≡ 2² (mod 13) は平方剰余、3 ≡ 4² (mod 13) も平方剰余なので、J(17, 13) と J(3, 13) は、どちらも = 1 になる。

帰納法の仮定から J(R, f) J(f, R) = (−1)^m　ここで m = [(R−1)/2][(f−1)/2] = [(13−1)/2][(3−1)/2]

①から J(R, f) = 1 は積に影響せず、②から J(Q, R) = J(f, R) なので:
　　J(Q, R) = J(17, 13) は = (−1)^m

[(R−1)/2] = (13−1)/2 = 6 の部分が偶数なので、③を検討するまでもなく、この指数 m は、指数 n = [(R−1)/2][(Q−1)/2] と偶・奇が一致する（どちらも偶数）。

具体例2　Q = 7, p = 5　（R が負になる例）

この場合 p は Q の平方剰余ではないが、R = −p = −5 が平方剰余: e = 4 とすると e² = 16 ≡ 2 ≡ −5 (mod 7)

e² − R = Qf を満たす奇数は f = 3:
　　4² − (−5) = 7 × 3　（♪）

① （♪）を mod f つまり mod 3 で考えると: J(R, f) = 1 すなわち J(−5, 3) = 1

−5 ≡ 1² (mod 3) は平方剰余。

② （♪）を mod |R| つまり mod 5 で考えると: J(Qf, R) = 1 すなわち J(7 × 3, −5) = 1。従って J(Q, R) = J(f, R) すなわち J(7, −5) = J(3, −5)

ヤコビ記号の「分子」が正の場合、「分母」のマイナスは無視できる（イントロ【4】参照）。J(7, −5) と J(3, −5) は、それぞれ L(7, 5) と L(3, 5) に過ぎず、7 ≡ 2 も 3 も mod 5 の非剰余なのでどちらも = −1。

具体例1と同様に進めて、J(R, f) J(f, R) を特徴付ける指数 m = [(R−1)/2][(f−1)/2] = [(−5−1)/2][(3−1)/2] によって、J(Q, R) つまり J(7, −5) の値も決まる。

m の偶・奇が n = [(R−1)/2][(Q−1)/2] = [(−5−1)/2][(7−1)/2] の偶・奇と一致するかどうかが問題だが、この例では m と n は両方とも奇数になる。この一致は、「偶然がくれたラッキー」ではない: m と n の偶・奇の一致は、常に保証されている。実際、（♪）を mod 4 で考えると:
　　−R ≡ Qf (mod 4)　この例では −(−5) ≡ 7 × 3 (mod 4)
この場合、最後の合同式は両辺とも ≡ 1 (mod 4) なので、結局 Qf ≡ 1 (mod 4) だが、これは Q と f が「両方とも ≡ 1 (mod 4) であるか、または両方とも ≡ −1 (mod 4) であること」を意味する: 要するに Q ≡ f (mod 4)。その両辺から 1 を引けば:
　　Q−1 ≡ f−1 (mod 4)
この左辺と右辺はどちらも偶数なので、両辺を 2 で割ることができ、その結果は:
　　(Q−1)/2 ≡ (f−1)/2 (mod 2)
これは…
　　指数 m = [(R−1)/2][(f−1)/2]
　　指数 n = [(R−1)/2][(Q−1)/2]
…の異なる因子の部分が mod 2 では合同であること（要するに偶・奇が一致すること）を意味し、その結果 m と n は偶・奇が一致！

他方、もし Qf ≡ 1 (mod 4) にならず Qf ≡ −1 ≡ 3 (mod 4) になる場合（Q と f は両方奇数なので、積は偶数にはならない: Qf ≡ 1 or 3 mod 4 となる）、Q ≢ f (mod 4) となって、上記の異なる因子の部分の偶・奇が逆になってしまう…。けれど（♪）によれば、その場合 −R ≡ Qf ≡ −1 (mod 4) なので R ≡ 1 (mod 4) となる: つまり R は4k+1型の奇数。このパターンにおいては、具体例1で見たように [(R−1)/2] の部分が偶数になるので、異なる因子の部分の偶・奇は逆になるものの、m と n はどちらも偶数！

具体例3　Q = 11, R = p = 5　（f が 1 になる例）

e = 4 が e² ≡ 5 (mod 11) を満たす。このとき 4² − 5 = 11f を満たす f は 1。つまり（♪）は 4² − 5 = 11 × 1。

①では、（♪）を mod 1 で考えることになる。mod 1 では全ての整数が ≡ 0 なので、e² の存在を考えるまでもなく J(R, f) = J(5, 1) = 1 は意味的にも、定義上も、正しい。

〔注意〕　狭義のヤコビ記号は、「分母」が 3 以上の奇数の場合にのみ定義される。Dirichlet はこの定義を拡張して、「分母」が正または負の任意の奇数となることを許容した（ただし「分母」が負になり得るのは「分子」が負でない場合のみ）。この拡張された定義においても、狭義のヤコビ記号の性質（相互法則など）がそのまま成り立つ。ヤコビ記号の「分母」が 1 になっても構わない（イントロ【5】参照）。

②では、J(Qf, R) = J(11 × 1, 5) = 1 であることから、J(11, 5) = J(1, 5) としている。これは具体的な等式（♪）を mod Qf つまり mod 11 × 1 で考えた結果だが、一般に J(a, b) = 1 が成り立っているなら、自動的に J(a, b) = J(1, b) が成り立つ（その右辺は定義から = 1 なので）。

f = 1 の場合でも、これ以降は、単なる m と n の偶・奇の検討になり、何も特別なことは起きない。

（下に続く）

2022-10-02　ガウスの第一証明・平方剰余の場合（後編）

R = p or −p が mod Q の平方剰余になる場合のうち、「f が p で割り切れる場合」だけは別扱いが必要。綱渡りのような証明。

§1.7　例えば Q = 37, p = 7 とすると、R = p は mod Q の平方剰余。

実際 x = ±9 のとき x² = 81 = 37 × 2 + 7 ≡ 7 (mod 37)。 −9 ≡ 28 (mod 37) なので、Q 未満の偶数の解は e = 28。対応する f は 21:
　　e² − R = Qf　つまり　28² − 7 = 37 × 21

J(R, Q) J(Q, R) を J(R, f) J(f, R) に帰着させる…という証明の方向性に変わりはないが、この場合、R と f が互いに素でない（f は R の倍数）。そのため、通常の意味では J(R, f) などが定義されず、定義されるとしても = 1 でも = −1 でもない = 0 という特殊な値になってしまって、「mod f で考えると J(R, f) = 1 うんぬん」という、いつもの論法が使えない。

困難の原因は、
　　e² − R = Qf　例えば　(4 × 7)² − 7 = (37 × 3 × 7)
の全部の項が R で割り切れてしまうことにある。だから全部の項を R で「約分」して
　　(4² × 7) − 1 = (37 × 3)
のような形にしてから、議論を進めればいい。

(1)　f が R で割り切れるのだから、その商を f/R = F と置くと f = FR。これを e² − R = Qf に代入すると:
　　【タ】　e² − R = Q(FR)
移項した e² = QFR + R は R の倍数同士の和だから、R で割り切れる。しかも R = p or −p は（正または負の）素数だから、e² = e × e が R で割り切れるからには、e 自身が R で割り切れる。そこで e/R = E と置くと、e = ER。それを【タ】に代入すると:
　　【チ】　(ER)² − R = QFR　　両辺を R で割ると
　　【ツ】　E²R − 1 = QF
【ツ】の値は、素数 R の倍数より 1 小さいので、もはや R では割り切れない。特に【ツ】右辺 QF は R で割り切れないので F は R で割り切れない。「小文字の f が R で割り切れる」という状況への対応として「大文字の F なら R で割り切れない」という保証が得られた！

ここで F は奇数 f の約数だから奇数。R は正にも負にもなり得るので、F = f/R は正にも負にもなり得る（常に正の f とは、その点が違う）。F の符号は R の符号と一致。f は既に絶対値 Q 未満だから、f の約数 F の絶対値はさらに小さく、もちろん Q 未満。F は帰納法の仮定の有効範囲内にある。

E は偶数 e を奇数 R で割ったものだから、偶数。こちらも R の符号に応じ正にも負にもなり得るが、以下の議論で必要なのは E が偶数であることだけ。E の具体的な値の範囲は、問題にならない。

(2)　一般に D が mod M の平方剰余であるということは、x² ≡ D (mod M) に解があるということ。つまり x² − D ≡ 0 (mod M) が成り立つこと。これは
　　x² − D は M の倍数
と同値（ただし M は法なので正とする）:
　　D は mod M の平方剰余　⇔　x² − D が M の倍数になるような x が存在

われわれの例では、【タ】から
　　【テ】　e² − R が FR の倍数（つまり f の倍数）になるような e が存在
これはもちろん
　　e² − R が F の倍数、従って |F| の倍数になるような e が存在
…という意味でもあるから、上記の同値性から、
　　R は mod |F| の平方剰余
であり（末尾（§1.9）の補足説明【3】参照）、記号的にはこう書ける:
　　【ト】　J(R, |F|) = 1

【テ】からも分かるように、もともと R は mod f の平方剰余なのだから、単純に J(R, f) = 1 と書きたいところだが、ヤコビ記号 J(a, b) は a と b が互いに素の場合に限って ±1 の値になる…。互いに素でない場合には、平方剰余だからといって = 1 とできない。そのため J(R, f) = 1 とは書けないが J(R, |F|) = 1 なら正しい。ちょっと面倒な話で、真意が分かりにくいかもしれない（補足説明【1】参照）。

(3)　同様に、f が |R| で割り切れる場合、e² − R = Qf を直接 mod |R| で――要するに mod p で――考えて J(Qf, |R|) = 1 とすることはできない。代わりに「約分」されている【ツ】を mod |R| で考えると:
　　−1 ≡ QF (mod |R|)　　両辺を −1 倍して
　　1 ≡ 1² ≡ −QF (mod |R|)　　ゆえに
　　【ナ】　J(−QF, |R|) = 1

〔解説〕　上記のように、x² ≡ −QF (mod |R|) には x ≡ 1 という解があるから、−QF は mod |R| の平方剰余。−QF と |R| は互いに素なので（なぜなら Q と |R| は相異なる素数であり、F は |R|=p で割り切れない）、【ナ】のように書ける。

§1.8　これで「互いに素でない」という問題は、解消された。「Dirichlet 版ヤコビ記号 J(a, b) では a, b が同時に負になれない」という制約に注意しつつ、【ト】と【ナ】の絶対値記号を除去しよう。F と R は符号が同じなので【ナ】については、単に |R| を R にできる。その結果、R が正なら「分子」の −QF は負、「分母」の R は正だし、R が負なら分子は正、分母は負になる（分子が正の場合、分母の符号は正でも負でも同じなので、正の数 |R| を負の数 R に置き換えても構わない）:
　　【ニ】　J(−QF, R) = 1
§1.2 の【ケ】を導いたときと同様に、形式的には【ニ】は2通りに分解可能:
　　【ヌ】　J(−Q, R) = J(F, R)
あるいは、マイナスを F 側に付けて:
　　【ネ】　J(Q, R) = J(−F, R)
実際に証明を進めると、【ネ】の形が役立つことが分かる。

〔注意〕　Q は帰納法の「最前線」に当たる重要な境界値なので、−Q にせず、そのまま使った方が便利。だが、もっと根本的な問題として、−Q は常に負。R は負にもなり得るので、【ヌ】の左辺は分子・分母が両方負になる可能性があり、ヤコビ記号の制約に違反してしまう――【ヌ】【ネ】はどちらも形式的には正しそうだが、実際には【ネ】だけが正しい。

さて【ト】の J(R, |F|) = 1 の絶対値を外すのは、少しトリッキー。【ト】から次が成り立つ:
　　【ノ】　J(R, −F) = 1
R, F が正の場合（両者の符号は一致する）、【ト】の真意は J(R, F) = 1 であり、分子が正なので分母の符号はどっちでもよく、確かに【ノ】が成立。他方、R, F が負の場合、|F| とは正の数 −F であり、【ト】の真意は【ノ】。

〔F が負の例〕　p = 3, R = −p = −3, Q = 43, f = 21 とすると、F = f/R = −7。このとき【ト】は:
　　J(R, |F|) = J(−3, |−7|) = 1
それは【ノ】と同じ意味:
　　J(R, −F) = J(−3, −(−7)) = 1
見た目はちょっとややこしいが、どちらも分母はプラス7。

R が正の場合には F も正なので、そのままでいいようだが、あえて符号を逆にして −F にしておくことで、R が負でも大丈夫になる。「分子・分母（どちらも奇数）の符号を逆にしておけば、何が起きても両方負にはならない」という発想。綱渡りのような際どい議論だが、ぎりぎりセーフで、どこにも穴はない（補足説明【4】参照）。

ここまで来れば、あとは一本道。R も −F も絶対値 Q 未満なので、帰納法の仮定から:
　　【ハ】　J(R, −F) J(−F, R) = (−1)^{[(R−1)/2][(−F−1)/2]}
【ハ】左辺の第1因子は【ノ】によって消滅、第2因子は【ネ】によって J(Q, R) に置換可能。従って【ハ】はこうなる:
　　【ヒ】　J(Q, R) = (−1)^{[(R−1)/2][(−F−1)/2]}　　←　実際に成り立つ式

証明したいことは Q, R に対する相互法則だった（【ウ】参照）:
　　【フ】　J(Q, R) = (−1)^{[(R−1)/2][(Q−1)/2]}　　←　証明したい式
それには【ヒ】右辺の指数と【フ】右辺の指数について、偶・奇の一致を示せばいい。

【テ】を mod 4 で考えると −1 ≡ QF (mod 4) なので、Q と F の一方は ≡ 1、他方は ≡ −1 (mod 4)。すなわち:
　　Q ≡ −F (mod 4)
その両辺（どちらも奇数）から 1 を引くと:
　　Q−1 ≡ −F−1 (mod 4)　　両辺（どちらも偶数）を 2 で割ると
　　(Q−1)/2 ≡ (−F−1)/2 (mod 2)
これは【ヒ】の指数と【フ】の指数の偶・奇が一致することを意味する。証明が完了した。□

上記の指数処理の手順は、Dirichlet のオリジナル版と少し異なる。補足説明【2】参照。

§1.9　補足説明。

【1】　なぜルジャンドル記号・ヤコビ記号には「分子・分母」が互いに素という条件が付き、互いに素でないと特殊ケースになるのか？

具体例として L(7, 7) を考える。7 と 7 は互いに素ではない。けれど x² ≡ 7 ≡ 0 (mod 7) には x ≡ 0 という解があるので、7 は mod 7 の平方剰余には違いない。

従って L(7, 7) = 1 と書きたいような気もする。けれど、それだと、7^(7−1)/2 = 7³ ≡ 0 (mod 7) となり、オイラーの基準による判定（平方剰余なら ≡ 1）との整合性が保たれない。オイラーの基準はいろいろなことの理論的基礎となるので、それと不整合な定義をすると、多大な不都合が生じるだろう。

普通の算数で「0 で割ってはいけない」というのと同様、剰余演算では「割られる数」と「法」が互いに素でない場合、何かと面倒なことが起きる…。そのため、多くの場面で「問題の数が法と互いに素の場合」と「そうでない場合」を分けて扱う必要がある。一つの背景として、ヤコビ記号などは、単純に「平方剰余なら +1 で非剰余なら −1」という便宜上の記法ではなく、代数構造に関わるもっと深い意味を持っている。

実は f と R が互いに素の場合（最大公約数が 1）とそうでない場合について、両者の最大公約数を変数にして統一的に扱うアプローチも考えられ、それはそれで興味深いことかもしれないが、変数の数を増やせば、別の意味でややこしい議論になってしまう。「細かい場合分け」は面倒ではあるが、ガウスの第一証明の「直接性・単純性」と、コインの裏表の関係にある。

【2】　Dirichlet 自身による符号処理（参考）

(−1) の指数は符号を反転できる…という性質（イントロ参照）を使い、Dirichlet は【ハ】【ヒ】の指数 [(R−1)/2][(−F−1)/2] を [(R−1)/2][(F+1)/2] に置き換え、その偶・奇が [(R−1)/2][(Q−1)/2] の偶・奇と一致することを次のように論じている。【テ】を mod 4 で考えると −1 ≡ QF なので、Q と F の一方は4k+1型の奇数、他方は4k+3型の奇数。どちらがどちらだとしても、次が成り立つ:
　　(F+1)/2 ≡ (Q−1)/2 (mod 2)

上の式にまず F = 4k+1, Q = 4k+3 を代入し、次に F = 4k+3, Q = 4k+1 を代入すれば、どちらでも両辺が一致することを確認可能。次のように言い換えることもできる。F ≡ 1, Q ≡ 3 (mod 4) または F ≡ 3, Q ≡ 1 (mod 4) なので (F, Q) = (1, 3) または (F, Q) = (3, 1)。上の式に代入した結果は、前者の場合 1 ≡ 1、後者の場合 0 ≡ 0 であり、偶・奇が一致する。

【3】　J(R, |F|) = 1 についての別の角度からの考察（参考）

式【ツ】の E²R − 1 = QF を mod |F| で考えると:
　　E²R − 1 ≡ 0　つまり　E²R ≡ 1 (mod |F|)

このとき E² と R は積が 1 だから、mod |F| において互いに逆数:
　　R ≡ (E²)⁻¹　　従って
　　R ≡ E⁻² ≡ (E⁻¹)²
r ≡ E⁻¹ と置くと:
　　R ≡ r² (mod |F|)
これは R が mod |F| において平方剰余であることを示している。のみならず、x ≡ E⁻¹ は x² ≡ R (mod |F|) の解の一つとなる。

法 |F| は奇数だが、素数とは限らない。従って、一般には、その世界の数に逆数が存在する保証はない。この場合に限っては、上記のように E⁻¹ は必ず存在する。

法が必ずしも素数でないため x² ≡ R (mod |F|) の解は、2種類とは限らない。特に |F| = 1 の場合、自明な解 x ≡ 0 の1種類に限られる。

実際 mod 1 では、全ての数は ≡ 0 ≡ 0² であり、非剰余というものはない。それに呼応するかのように、|F| = 1 の場合、拡張されたヤコビ記号は常に J(R, 1) = 1 なので、平方剰余・非剰余について具体的に考えるまでもない。

他方、x² ≡ R (mod |F|) は、通常の「平方根」のイメージと異なり、場合によって2種類より多くの解を持つ――それは法 |F| が2種類以上の素数から成る合成数の場合で、例えば Q = 367, p = 5, R = −5 のとき e = 340, f = 315, E = −68, F = −63 となり x² ≡ −5 (mod 63) は4種類の解 x ≡ ±11, ±25 を持つ（このとき E⁻¹ ≡ 25 (mod 63) は、確かに解の一つ）。ここで |F| = 3²⋅7 は、2種類の素因数 3, 7 を持つ。2次方程式が2種類より多くの解を持ち得るのは、この場合、考えている世界が整域とは限らないため。

【4】　符号のトリッキーな処理について（参考）

Dirichlet の原論文 Über den ersten… (1854) では、分母にマイナスを付けずに J(R, F) = 1 としている。これだと両方の数が負になり得るので、厳密に言うとギャップが生じる。やはりそこが気になったのか、Dirichlet は後に Vorlesungen (1863) において J(R, F) = J(R, −F) = 1 という書き方をしている。「R, F が正なら J(R, F) を使い、R, F が負なら J(R, −F) を使えば、どちらにしても J(R, −F) に等しい」と解釈するなら、内容は正しい。現代の感覚からすると、両方負になったら困る場合――しかも法は正の方がいいので――、とりあえず安全のため F に絶対値記号を付けておき、その絶対値記号を外す方法を論じるのが無難だろう（本文参照）。

これはささいな形式的問題で、Dirichlet の証明の本質を損なうものではない。ところで、原論文のフランス語訳 Sur la première démonstration… には誤植があり、「ϖ と φ は同じ符号を持つ」（われわれの R と F に当たる変数名）という部分が「ε と φ は同じ符号を持つ」（われわれの E と F に当たる）になっている。E, F, R が同じ符号を持つのは事実だが、オリジナルのドイツ語版の方が文脈的に妥当: R と F の符号が同じだからこそ R と −F は決して両方負にはならず、帰納法の仮定から、R と −F の間に（どちらも絶対値 Q 未満なので）相互法則が成り立つ。

「分母」が負のケースの綱渡りを避けたければ、ヤコビ記号の相互法則をあらかじめ次の形にしておくことも考えられる。互いに素な奇数 a, b について:
　　a, b の少なくとも一方が正ならば　J(a, |b|) J(b, |a|) = (−1)^{[(a−1)/2][(b−1)/2]}
さらに（第一証明には必要ないが）このとき:
　　a, b が両方とも負ならば　J(a, |b|) J(b, |a|) = −(−1)^{[(a−1)/2][(b−1)/2]}
これはクロネッカー記号の振る舞いを暗示している（Kenneth H. Rosen: Elementary Number Theory and Its Applications (1986), 9.3 Prob. 8）。証明は次の通り。A = |a|, B = |b| と置く。a, b が両方正の場合、証明することは何もない。片方だけ、例えば a が負の場合、A = −a に注意すると:
　　J(−A, b) J(b, A) = (−1)^(b−1)/2 (−1)^{[(A−1)/2][(b−1)/2]}
　　= (−1)^{[(A+1)/2][(b−1)/2]} = (−1)^{[(−a+1)/2][(b−1)/2]} = (−1)^{[(a−1)/2][(b−1)/2]}
一方 a, b が両方負の場合:
　　J(−A, B) J(−B, A) = (−1)^(B−1)/2 (−1)^(A−1)/2 (−1)^{[(A−1)/2][(B−1)/2]}
　　= (−1)^(−b−1)/2 (−1)^(−a−1)/2 (−1)^{[(−a−1)/2][(−b−1)/2]}
　　= (−1)^(b+1)/2 (−1)^(a+1)/2 (−1)^{[(a+1)/2][(b+1)/2]}
この値は a, b の両方が ≡ 3 (mod 4) だと正、そうでなければ負になるが、いずれのケースも (−1)^{[(a−1)/2][(b−1)/2]} とは符号が逆。すなわち、両方の数が負の場合の（クロネッカー記号の）相互法則は、古典的な相互法則の値の −1 倍になる。

2022-10-08　ガウスの第一証明・非剰余の場合　ディリクレ版をさらに簡単化

平方剰余の相互法則についての Gauß の第一証明は、Dirichlet によって整理され、大幅に簡単化された。このメモでは、その Dirichlet 版の後半「非剰余の場合」をさらに簡単化して紹介する。

簡単化といっても、第一証明が長く険しい道であることに変わりはない。相互法則を証明することだけが目的なら、比較的シンプルな第三証明の方が便利だろう。第一証明をあえて研究する目的は、一般的に言えば、ガウスやディリクレの感性に触れて「巨匠から学ぶ」こと、天下り的な面のある第三証明と対比的に「直接的な証明」の手応えを味わうこと。

特殊的に言えば、ディリクレの証明法の核心はヤコビ記号の拡張であり、クロネッカー記号やディリクレ標数の概念の萌芽を含んでいて、「証明のツール」そのものが興味深い。ガウスの D.A. だけを見て「第一証明＝美しくない」と決め付けず、ディリクレ版の面白さとセットで再評価したい。

§2.1　「絶対値 Q 未満の2個の奇素数について相互法則が成り立つなら、絶対値 Q 未満の任意の奇素数 p と Q の間にも相互法則が成り立つ」――この命題（命題X）を証明できるなら、全ての奇素数について相互法則が成り立つ。

p or −p が mod Q の平方剰余の場合については、既に証明が完了した。具体的に、4k+3型の Q については完全に証明が終わり、4k+1型の Q については p mod Q が平方剰余の場合について証明が終わった（Dirichlet の方法では、これらすべてのパターンが一括証明される）。

残っているのは「Q が4k+1型の素数、かつ p mod Q が非剰余の場合」だけ。このケースの証明手順は次の通り。以下 Q を4k+1型素数とする。

(1)　Q mod q が非剰余になるような、Q 未満の奇素数 q が存在する（「超絶技巧」補助定理）:
　　【ホ】　L(Q, q) = −1

このとき、もしも L(q, Q) = 1 なら、前半で証明済みの結果から、帰納法の仮定の下で L(Q, q) = 1 となり【ホ】と矛盾。従って、この q については、
　　【マ】　L(q, Q) = −1
でなければならず、L(Q, q) L(q, Q) = (−1)(−1) = 1。これは Q と q の間の相互法則…
　　L(Q, q) L(q, Q) = (−1)^{[(Q−1)/2][(q−1)/2]} = 1
…の正しさを示している。

Q は4k+1型なので、指数の因子 [(Q−1)/2] は偶数。従って指数は偶数であり、最後の等号の後ろは 1。

もしも Q 未満の素数のうち、mod Q の非剰余になるのが q だけだったら、これで証明が完了するわけだが、実際にはそれ以外にも mod Q の非剰余になる素数 p が存在し得る。以下では mod Q の非剰余であるような、Q 未満の任意の正の奇素数（q とは異なるもの）を p とする:
　　【ミ】　L(p, Q) = −1

【ミ】を仮定した上で、上記同様 L(Q, p) L(p, Q) = 1 を――言い換えれば L(Q, p) = −1 を――証明したい。

【ミ】の意味は、x² ≡ p (mod Q) に解が無いということ。「存在しない解」（解が存在しないこと）を使って上記のことを証明しようとしても、どこから手を付けていいのか、困ってしまう。けれど L(Q, p) = −1 を証明する代わりに、それと【ホ】を掛け算したもの、つまり…
　　【ム】　J(Q, pq) = L(Q, p) L(Q, q) = (−1)(−1) = 1
…を証明してもいいわけである。さらに、ルジャンドル記号の性質を使うと【ミ】と【マ】の積から:
　　J(pq, Q) = L(pq, Q) = L(p, Q) L(q, Q) = (−1)(−1) = 1
となり、これは証明したい【ム】をひっくり返した形になっているばかりか、これによって
　　【メ】　x² ≡ pq (mod Q)
に解があることが保証される。この「存在する解」が突破口となる！

一定の法において、非剰余と非剰余の積（この場合 p と q の積）が平方剰余になることについては、第二補充法則【11】参照。

(2)　いつものように【メ】の偶数の解（0 以上 Q 未満）を e と置くと:
　　e² ≡ pq　つまり　e² − pq ≡ 0 (mod Q)
従って e² − pq は Q の整数倍。いつものように、その整数を f とすると:
　　【モ】　e² − pq = Qf

f は絶対値 Q 未満の奇数であり、正とは限らない。

実際 e, p, q はそれぞれ 0 以上 Q 未満の範囲にあるので、【モ】左辺は −Q² より大きく Q² より小さい。すなわち絶対値 Q² 未満。それと等しい右辺 Qf についても |Qf| < Q² が成り立ち、その両辺を正の数 Q で割ると |f| < Q。ここで e は偶数、p, q は奇数なので【モ】左辺は奇数、それと等しい右辺 Qf も奇数。だから f は奇数。

積 pq が Q より大きいとしても、成分 p, q がそれぞれ Q 未満なので、pq は「帰納法の仮定の有効範囲」に入る。なぜなら pq と Q の間の（ヤコビ記号の）相互法則は、「p と Q の間の（狭義の）相互法則」「q と Q の間の（狭義の）相互法則」にのみ依存し、それら二つは「帰納法の仮定の有効範囲内」。

さて、【モ】に関連して、3種類の状況が生じ得る: ①f が p でも q でも割り切れない場合; ②f が p または q のどちらか一方で割り切れるが、他方では割り切れない場合; ③f が p でも q でも割り切れる場合。

§2.2　便利なショートカット。

pq を R と置くと【モ】はこうなる:
　　【ヤ】　e² − R = Qf　　（←仮定していること）
証明すべき【ム】はこうなる:
　　【ユ】　J(Q, R) = 1　　（←仮定【ヤ】からこれを導きたい）

この【ヤ】は、「平方剰余の場合」で最初に扱った【オ】と全く同じ。その結果、ケース①については【オ】以下の議論が再利用可能。ケース③についても、「平方剰余の場合」後編の議論を再利用できる。残念ながら、このシンプルなショートカットは、ケース②では役立たない――それでも①②③のうち実質的には②だけを考えれば良いことになり、証明の手間が約3分の1で済む。

このショートカットは、外形的には単に pq を R と置くだけだが、それだけのことで見通しが良くなる: 既に一回歩いた道の再利用なので、迷わず前進できる。①③のケースで pq を一つの文字のように扱うのは明白なアプローチであり、Dirichlet 自身も（少なくとも無意識的には）この方法に気付いていたと思われる。

§2.3　ケース①　f が p でも q でも割り切れない場合（f と R が互いに素）

この場合 §1.2 とほとんど同じ。【ヤ】を mod R で考えると e² ≡ Qf (mod R)、【ケ】と同様に:
　　J(Qf, R) = 1　つまり　J(Q, R) = J(f, R)
この値 J(f, R) が = 1 であることを示せばいい（【ユ】参照）。

【ヤ】を mod |f| で考えると【オ】【カ】と同様に:
　　J(R, |f|) = J(R, f) = 1　　← R は正なので f の正負はどちらでもいい
帰納法の仮定から:
　　J(f, R) = J(R, f) J(f, R) = (−1)^{[(R−1)/2][(f−1)/2]}
この値が = 1 であることを示したいのだった。(−1) の肩に乗っている指数が偶数であることを示せばいい。それには (R−1)/2 または (f−1)/2 が偶数であることを示せばいい。いつものように【ヤ】を mod 4 で考えると、この場合 Q ≡ 1 (mod 4) という前提があるので:
　　−R ≡ f (mod 4)
R, f は奇数なので R ≡ 1, f ≡ −1 または R ≡ −1, f ≡ 1 (mod 4) のいずれかが成立。前者なら (R−1)/2 は偶数、後者なら (f−1)/2 は偶数。証明が完了した。□

§2.4　ケース③　f が p でも q でも割り切れる場合

この場合、f が R = pq で割り切れる。§1.7 と同様に f = FR, e = ER と置くと、【ト】に当たる J(R, |F|) = 1 が出る。「分子」の R = pq は常に正なので、絶対値記号を外した上で「分母」を −F に固定できる（F が正なら −F は負、F が負なら −F は正）:
　　J(R, −F) = 1
一方、【ナ】に当たる J(−QF, R) = 1 から（R は正なので絶対値記号は不要）、【ネ】に当たる J(Q, R) = J(−F, R) が出る。【ハ】【ヒ】と同様に:
　　J(Q, R) = (−1)^{[(R−1)/2][(−F−1)/2]}
この値が = 1 であることを示したい（【ユ】参照）。指数が偶数であることを示せばいい。【ツ】に当たる式を mod 4 で考えると −1 ≡ F つまり −F ≡ 1 従って −F−1 ≡ 0 (mod 4)。ゆえに −F−1 は4の倍数、(−F−1)/2 は偶数。証明が完了した。□

§2.5　ケース②　f が p または q のどちらか一方で割り切れるが、他方では割り切れない場合

このケースについては、①③と違い簡単なショートカットができないので、Dirichlet の議論をそのまま紹介する。これはこれで含蓄がある。

実は、全部を一括して扱う「第一証明の大統一理論」も提示されていて（Carlitza: A Note on Gauss’ First Proof on the Quadratic Reciprocity Theorem, 1959）、研究の余地がある。

必要に応じて p と q の変数名を入れ替えることで、一般性を失うことなく、こう仮定できる: f は p では割り切れないが q では割り切れる。

〔注意〕　q には「Q が mod q で非剰余」という特別な仮定があるが、p にはそのような仮定がない。しかし、ここではこの特別な仮定を使わず、p も q も mod Q で非剰余ということだけを仮定する。従って p と q は立場が対等で、必要なら変数名を交換できる（この扱いの厳密性に疑念があるなら、f が p でだけ割り切れるケースについては、q を p、p を q に置き換えて、以下の議論を反復すればいい――変数名の交換と実質同じことだが）。

最初の部分は §1.7 と似ている。F = f/q と置くと、F は絶対値 Q 未満の奇数で f = qF。【ヤ】の e² − R = Qf つまり e² − pq = Qf にそれを代入して:
　　e² − pq = QqF
このとき e² = QqF + pq も q の倍数の和なので、素数 q で割り切れ、従って e は q で割り切れる。E = e/q と置くと、E は偶数で e = qE。上の式にこれを代入して:
　　(qE)² − pq = QqF
両辺を q で割ると:
　　【ヨ】　qE² − p = QF

第一に【ヨ】を mod |F| で考えると qE² − p ≡ 0 つまり qE² ≡ p (mod |F|)。この両辺のヤコビ記号の値を考えると:
　　J(qE², |F|) = J(p, |F|)　ゆえに　J(q, |F|) = J(p, |F|)　従って:
　　【ラ】　J(pq, |F|) = J(pq, F) = 1

〔解説〕　「両辺のヤコビ記号の値を考える」とは: 奇素数 c を法として a ≡ b のとき、「a が平方剰余か非剰余か」と「b が平方剰余か非剰余か」は当然一致するので、L(a, c) ≡ L(b, c) となる――それのヤコビ記号版。ヤコビ記号は「平方剰余か非剰余か」を直接表すわけではないが、奇数 d = c₁c₂… を法として a ≡ b なら明らかに J(a, d) = J(b, d)。ここで c₁, c₂, … は d の素因数。

J(qE², |F|) = J(q, |F|) J(E, |F|) J(E, |F|) と分解されるが、このうち J(E, |F|) の部分について = +1 だとしても = −1 だとしても2回掛ければ = 1 なので、因子 J(E, |F|) J(E, |F|) を無視できる（1倍というのは、何もしないことと同じ）。より直接的に、E² は平方数なので J(E², |F|) = 1。なぜなら、E² はもちろん（任意の素数を法として）平方剰余: ヤコビ記号の定義上、|F| が s 個の素数の積だとして、J(E², |F|) は s 個の 1 の積。さて J(q, |F|) = J(p, |F|) が = +1 だとしても = −1 だとしても、それらの積は +1、このことから【ラ】が得られ、pq は正なので、分母の符号はどちらでもよく、絶対値記号を除去できる。【ラ】が意味を持つためには pq と F が互いに素でなければならないが、事実そうなっている: 仮定により f は p で割り切れないから、f の約数 F は p で割り切れない; F は q でも割り切れないない（もしも F が q で割り切れるなら【ヨ】の両辺は q で割り切れ、素数 p が素数 q で割り切れることになるが、それは不可能）。

第二に【ヨ】を mod p で考えると qE² ≡ QF (mod p)、上と同様に J(q, p) = J(QF, p) = J(Q, p) J(F, p)、両辺を J(F, p) 倍して:
　　J(q, p) J(F, p) = J(Q, p) J(F, p) J(F, p)
J(F, p) = ±1 なので因子 J(F, p) J(F, p) = 1 を除去できる:
　　【リ】　J(q, p) J(F, p) = J(Q, p)

第三に【ヨ】を mod q で考えると −p ≡ QF (mod q)、従って J(−p, q) = J(QF, q) = J(Q, q) J(F, q)、両辺を J(F, q) 倍して:
　　【ル】　J(−p, q) J(F, q) = J(Q, q)

【リ】【ル】の左辺同士、右辺同士の積を考える:
　　J(q, p) J(−p, q) × J(F, p) J(F, q) = J(Q, p) J(Q, q)
帰納法の仮定から J(q, p) = J(q, −p) と J(−p, q) の間には、相互法則が成立:
　　(−1)ⁿ × J(F, pq) = J(Q, pq)　ここで　n = [(q−1)/2][(−p−1)/2]
両辺を (−1)ⁿ 倍して:
　　【レ】　J(F, pq) = (−1)ⁿ J(Q, pq)

〔解説〕　(−1)ⁿ = ±1 なので因子 (−1)ⁿ (−1)ⁿ = 1 を除去できる。

最後に F と pq も帰納法の有効範囲なので:
　　J(F, pq) J(pq, F) = (−1)^m　ここで　m = [(F−1)/2][(pq−1)/2]
【レ】【ラ】を代入して:
　　(−1)ⁿ J(Q, pq) × 1 = (−1)^m
両辺を (−1)ⁿ 倍して:
　　J(Q, pq) = (−1)^m × (−1)ⁿ = (−1)^m+n
この値が +1 であること、すなわち指数 m+n が偶数であることを示したい（【ユ】参照: R = pq）。

Q ≡ 1 (mod 4) という前提に留意しつつ【ヨ】を mod 4 で考えると:
　　−p ≡ F (mod 4)
その両辺は奇数だから −p ≡ F ≡ 1 または −p ≡ F ≡ 3 (mod 4)、つまり −p と F は、両方とも4k+1型の奇数か、または両方とも4k+3型の奇数。もし両方とも4k+1型なら [(F−1)/2] と [(−p−1)/2] はどちらも偶数なので、
　　m = [(F−1)/2][(pq−1)/2],
　　n = [(q−1)/2][(−p−1)/2]
はどちらも偶数、和は偶数。一方、もし −p と F が両方とも4k+3型なら [(F−1)/2] と [(−p−1)/2] はどちらも奇数つまり ≡ 1 (mod 2) なので:
　　m+n ≡ 1 × [(pq−1)/2] + [(q−1)/2] × 1 ≡ [(pq−1)/2] + [(q−1)/2] (mod 2)　★
この「もし」では −p ≡ 3 ≡ −1 すなわち p ≡ 1 (mod 4) と仮定しているので:
　　pq−1 ≡ (1)q−1 ≡ q−1 (mod 4)
その両辺は偶数なので 2 で割ると:
　　(pq−1)/2 ≡ (q−1)/2 (mod 2)
それを★に代入して:
　　m+n ≡ [(q−1)/2] + [(q−1)/2] ≡ q−1 ≡ 0 (mod 2)
どちらの場合でも m+n は偶数。証明が完了した。□

Dirichlet 自身は、二つの「もし」に分岐しない方法で「指数が偶数」を示した。上の議論が分かりにくい場合、その別解が参考になるかもしれない（§2.7）。①②③どのケースについても、証明の意味が分かりにくい場合、数値例の研究が役立つだろう（§2.6）。

これによってケース①②③の全てが証明され、すなわち「非剰余の場合」が解決し、前半の「剰余の場合」と併せることで、平方剰余の相互法則についてのガウスの第一証明が完成したのである。□□

§2.6　上記①②③の各ケースについて、具体的な数値例によって、証明の流れを確認しておく（これは証明の一部ではない）。

4k+1型の素数 Q が与えられたとき、L(Q, q) = −1 を満たす Q 未満の素数 q が存在する――この補題は「存在定理」であり、実際には q の値は分からない。

補助定理の証明の仕方から、Q が8k+5型素数の場合は、Q − 2 の8k±3型の素因数が q であり、Q が8k+1型の素数なら q は 2√Q + 1 より小さい。q についてそれ以上の情報はない（証明上、必要もない）。

【例1】　Q = 13 の場合　13 を法とする平方剰余は、
　　1² = 1, 2² = 4, 3² = 9, 4² = 16 ≡ 3, 5² = 25 ≡ 12, 6² = 36 ≡ 10
の6種類なので、13未満の奇素数のうち p = 3 は「平方剰余の場合」になるが、それ以外の p = 5, 7, 11 は mod Q の平方非剰余。この Q は8k+5型なので、Q−2 の素因数、すなわち Q−2 = 11 自身が q となる。出発点として、
　　L(Q, q) = −1　つまり　L(13, 11) = −1
であることが確定している。

p = 5 のとき R = pq = 5 × 11 = 55。 p と q はどちらも mod Q の非剰余なので、55 は mod Q の平方剰余。実際 55 = 13 × 4 + 3 ≡ 3 (mod 13) が mod 13 の平方剰余であるのは、上記の通り（4² = 16 ≡ 3）。つまり x² ≡ 55 (mod 13) に解がある（x ≡ ±4 ≡ 4 or 9）。Q 未満の正の偶数解を選んで e とする。【ヤ】の e² − R = Qf は、こうなる:
　　《ヤ1》　4² − 55 = 13 × (−3)　つまり e = 4, f = −3

この f = −3 は p でも q でも割り切れないので、ケース①に当たる。そこで《ヤ1》を mod R つまり mod 55 で考えると:
　　4² ≡ 13 × (−3) (mod 55)　つまり　J(13 × (−3), 55) = 1
　　ゆえに　J(13, 55) = J(−3, 55)
従って、右辺の J(f, R) つまり J(−3, 55) が = 1 であることを示せば、自動的に左辺の J(Q, R) つまり J(13, 55) も = 1 であることが示される。そして
　　J(Q, R) = L(Q, p) L(Q, q) = 1
を示すことは、L(Q, p) = −1 を示すことに他ならない――なぜなら L(Q, q) = −1 は確定しているので。

さて、《ヤ1》を mod |f| つまり mod 3 で考えると:
　　4² − 55 ≡ 0　つまり　4² ≡ 55 (mod 3)　ゆえに　J(55, −3) = 1
すなわち J(R, f) = 1。帰納法の仮定から:
　　J(−3, 55) = J(f, R) = J(R, f) J(f, R) = (−1)^{[(55−1)/2][(−3−1)/2]}
この値が = 1 であることを示したい。(−1) の肩の指数が偶数であることを示せばいい。それには (R−1)/2 または (f−1)/2 ――つまり (55−1)/2 または (−3−1)/2 ――が偶数であることを示せば十分。この具体例では (−3−1)/2 が偶数であることは直接的に確認可能だが、一般論として《ヤ1》のような式を mod 4 で考えると:
　　−55 ≡ −3 (mod 4)　　← Q = 13 の部分は Q ≡ 1 (mod 4) なので除去される
　　すなわち −R ≡ f (mod 4)
これは R と f の一方は4k+1型（他方は4k−1型）という意味なので、(R−1)/2 または (f−1)/2 の一方は確かに偶数。

〔注意〕　ヤコビ記号の「分母」が合成数の場合、例えば J(−3, 55) = 1 だとしても、x² ≡ −3 (mod 55) に解があるとは限らない。J(−3, 5) と J(−3, 11) の両方が −1 なら、それらの「積」である J(−3, 55) は +1 になるが、その場合、x² ≡ −3 (mod 5) にも x² ≡ −3 (mod 11) にも解がないのだから、x² ≡ −3 (mod 55) にも解はない。ヤコビ記号の「分母」について L(Q, p) = −1 と L(Q, q) = −1 から J(Q, pq) = 1 が生じるのは、異なる法 mod p と mod q から、形式的に mod pq へと移行する話。一方、ルジャンドル記号の「分子」について、L(p, Q) = −1 と L(q, Q) = −1 から L(pq, Q) = 1 が生じるのは、一定の法 mod Q における話。これは…
　　x² ≡ Q (mod pq)　と　x² ≡ pq (mod Q)　の違い　← pq の場所が違う！
…であり、前者は解を持たず、後者は解を持つ。

【例2】　Q = 13 の場合（続き）　p = 7 とすると、R = pq = 77。【ヤ】に当たる式は:
　　《ヤ2》　8² − 77 = 13 × (−1)　つまり e = 8, f = −1
この f = −1 もケース①。mod R つまり mod 77 で考えると:
　　J(13 × (−1), 77) = 1　ゆえに　J(13, 77) = J(−1, 77)
mod |f| つまり mod 1 で考えると:
　　8² ≡ 77 (mod 1)　従って　J(77, −1) = 1　すなわち　J(R, f) = 1
「例1」同様、帰納法の仮定から:
　　J(−1, 77) = (−1)^{[(77−1)/2][(−1−1)/2]}
この場合も R と f のどちらかは4k+1型なので、指数は偶数。実際 (77−1)/2 = 38。

【例3】　Q = 17 の場合　mod Q では 3, 5, 7, 11 が平方非剰余。仮に q = 5 が選ばれたとすると、p = 3, 7, 11 について相互法則を証明しなければならない。【ヤ】に当たる式は、それぞれこうなる:
　　p = 3 のとき　R = pq = 15 となり 10² − 15 = 17 × 5　すなわち e = 10, f = 5
　　p = 7 のとき　R = pq = 35 となり 16² − 35 = 17 × 13　すなわち e = 16, f = 13
　　p = 11 のとき　R = pq = 55 となり 2² − 55 = 17 × (−3)　すなわち e = 2, f = −3
このうち、2番目と3番目は、ケース①であり、例1・例2と全く同様になるが、1番目の例（p = 3）では f = 5 が p = 3 では割り切れないが q = 5 では割り切れるため、ケース②になる（この具体例については「例6」参照）。

【例4】　ケース③は比較的まれで、最小の例は Q = 137 で生じる―― q = 3, p = 5 の場合（または q = 5, p = 3 の場合）。【ヤ】に当たる式は:
　　p = 5, q = 3, R = 15; 120² − 15 = 137 × 105　すなわち e = 120, f = 105
この f は、p でも q でも割り切れ、要するに R = pq = 15 で割り切れる。そのため、直接ヤコビ記号で表そうとすると = 0 になってしまい、うまくいかない。「互いに素」を回復させるため 15 で「約分」する。【ツ】に当たる式は:
　　8² × 15 − 1 = 137 × 7　すなわち E = 8, F = 7
【ト】に当たる式は J(15, 7) = 1、【ナ】に当たる式は J(−(137 × 7), 15) = 1、【ネ】に当たる式は J(137, 15) = J(−7, 15)、【ノ】に当たる式は J(15, −7) = 1、ゆえに【ヒ】に当たる式は:
　　J(Q, R) = J(137, 15) = (−1)^{[(15−1)/2][(−7−1)/2]}
この指数が偶数であることを示したい。§2.4 で見たように −F ≡ 1 (mod 4) すなわち −7 ≡ 1 (mod 4) であるから、−F−1 すなわち −7−1 は4の倍数、その半分の (−7−1)/2 は偶数。

【例5】　ケース②の例: Q = 41, p = 13, q = 3, pq = 39 の場合:
　　30² − 13 × 3 = 41 × 21　すなわち e = 30, f = 21
この f = 21 は p = 13 では割り切れないが q = 3 では割り切れる。F = f/q = 7, E = e/q = 10 となり、【ヨ】に当たる式は:
　　《ヨ1》　3 × 10² − 13 = 41 × 7

第一に《ヨ1》を mod |F| つまり mod 7 で考えると 3 × 10² ≡ 13、従って:
　　J(3, 7) = J(13, 7)　ゆえに　J(3, 7) J(13, 7) = J(39, 7) = 1　《ラ1》

この場合 J(3, 7) = J(13, 7) = −1 なので、それらの積は (−1)(−1) = 1 で上記の通りだが、もし仮に J(3, 7) = J(13, 7) = +1 だったとしても、それらの積が (+1)(+1) = 1 であることに変わりない。感覚的には、ヤコビ記号の積について「因子の移項」ができる:
　　J(3, 7) = J(13, 7)　右辺の J(13, 7) を左辺に「移項」して　J(3, 7) J(13, 7) = 1

第二に《ヨ1》を mod p つまり mod 13 で考えると 3 × 10² ≡ 41 × 7、従って:
　　J(3, 13) = J(41, 13) J(7, 13)　両辺を J(7, 13) 倍して J(3, 13) J(7, 13) = J(41, 13)　《リ1》

この場合 J(3, 13) = J(41, 13) J(7, 13) は (+1) = (−1)(−1) なので（両辺は 1 に等しい）、その両辺を −1 倍したことになる（新しい両辺は −1 に等しい）。これも感覚的には「因子の移項」:
　　J(3, 13) = J(41, 13) J(7, 13)　右辺の J(7, 13) を左辺に「移項」して　J(3, 13) J(7, 13) = J(41, 13)

第三に《ヨ1》を mod q つまり mod 3 で考えると −13 ≡ 41 × 7、従って:
　　J(−13, 3) = J(41, 3) J(7, 3)　両辺を J(7, 3) 倍して J(−13, 3) J(7, 3) = J(41, 3)　《ル1》

この場合 J(−13, 3) = J(41, 3) J(7, 3) は (−1) = (−1)(+1) なので（両辺は −1 に等しい）、その両辺を +1 倍したことになる（新しい両辺も −1 に等しい）。やはり感覚的には「因子の移項」:
　　J(−13, 3) = J(41, 3) J(7, 3)　右辺の J(7, 3) を左辺に「移項」して　J(−13, 3) J(7, 3) = J(41, 3)

《リ1》と《ル1》を辺々掛け算すると:
　　J(3, 13) J(7, 13) × J(−13, 3) J(7, 3) = J(41, 13) × J(41, 3)
拡張されたヤコビ記号の性質上 J(3, 13) = J(3, −13)。それを考慮しつつ、掛け算の順序を変え、帰納法の仮定を適用すると:
　　J(3, −13) J(−13, 3) × J(7, 13) J(7, 3) = J(41, 39)
　　つまり　(−1)^{[(3−1)/2][(−13−1)/2]} × J(7, 39) = J(41, 39)
両辺を (−1)^{[(3−1)/2][(−13−1)/2]} 倍して:
　　つまり　J(7, 39) = J(41, 39) × (−1)^{[(3−1)/2][(−13−1)/2]}　《レ1》

この場合、実は (−1)^{[(3−1)/2][(−13−1)/2]} = −1 なので、上の変形は −J(7, 39) = J(41, 39) だから J(7, 39) = −J(41, 39) という当たり前のことに過ぎない。もしもこの (−1) の累乗が = +1 だったとしても、+J(7, 39) = J(41, 39) ならば J(7, 39) = +J(41, 39) という当たり前の話に。《レ1》も
　　(−1)^{[(3−1)/2][(−13−1)/2]}
が、左辺から右辺へ「因子移項」されたもの。

最後に F = 7 と pq = 39 は（各因子が Q = 41 未満なので）帰納法の仮定の有効範囲にあり:
　　J(7, 39) J(39, 7) = (−1)^{[(7−1)/2][(39−1)/2]}
《レ1》《ラ1》を代入して:
　　J(41, 39) × (−1)^{[(3−1)/2][(−13−1)/2]} × 1 = (−1)^{[(7−1)/2][(39−1)/2]}
　　J(41, 39) = (−1)^{[(7−1)/2][(39−1)/2]} × (−1)^{[(3−1)/2][(−13−1)/2]}
　　= (−1)^{[(7−1)/2][(39−1)/2]+[(3−1)/2][(−13−1)/2]}
この指数 [(7−1)/2][(39−1)/2]+[(3−1)/2][(−13−1)/2] が偶数であることを示したい。

Q = 41 ≡ 1 (mod 4) に考慮しつつ《ヨ1》を mod 4 で考えると −13 ≡ 7 (mod 4)。この例では −p = 13 と F = 7 が両方4k+3型。[(F−1)/2] = 3 と [(−p−1)/2] = −7 はどちらも奇数、つまり ≡ 1 (mod 2) なので、指数の偶・奇に影響しない:
　　[(7−1)/2][(13⋅3−1)/2] + [(3−1)/2][(−13−1)/2] ≡ [(13⋅3−1)/2] + [(3−1)/2] (mod 2)　★
p = 13 ≡ 1 (mod 4) なので、(pq−1)/2 ≡ (q−1)/2 (mod 2) が成り立ち、★ ≡ [(3−1)/2] + [(3−1)/2] ≡ (3−1) ≡ 0 (mod 2)。

【例6】　「例3」で後回しにした Q = 17, p = 3, q = 5 のケース。 10² − 15 = 17 × 5 つまり e = 10, f = 5。【ヨ】に当たる式は:
　　5 × 2² − 3 = 17 × 1　すなわち E = 2, F = 1
証明は一般の Q, p, q に対して有効なので、この場合も「例5」と数値が置き換わるだけで、全ての式がそのまま成り立つ（この例では F = 1 なので、幾つかの式は自明な内容になる。例えば【ラ】に当たる式は J(15, 1) = 1）。最終的には、
　　m = [(F−1)/2][(pq−1)/2],
　　n = [(q−1)/2][(−p−1)/2]
の和が偶数であることを示せばいい。この場合 −p = −3, F = 1 は両方とも4k+1型なので、直ちに m, n は両方偶数。

§2.7　（付録）　ケース②の指数の偶・奇: Dirichlet 自身による議論

§2.5 では −p ≡ F (mod 4) について、≡ 1 の場合と ≡ 3 の場合に分けて考えたが、これを次のように一括処理することもできる。まず −p ≡ F の両辺から 1 を引いて:
　　−p−1 ≡ F−1 (mod 4)
この両辺は偶数なので、2 で割ることができる:
　　(−p−1)/2 ≡ (F−1)/2 (mod 2)
左辺に mod 2 の補題（§1.5）を適用すると (p+1)/2 ≡ (F−1)/2 (mod 2)。つまり (F−1)/2 と (−p−1)/2 ≡ (p+1)/2 は mod 2 で合同。この合同関係を使って…
　　m+n = [(F−1)/2][(pq−1)/2] + [(q−1)/2][(−p−1)/2]
…を mod 2 で整理すると:
　　m+n ≡ [(p+1)/2][(pq−1)/2] + [(q−1)/2][(p+1)/2] ≡ [(p+1)/2] × [(pq−1)/2 + (q−1)/2] (mod 2)
今 pq = (pq) に奇数の積の補題（§1.4）を適用すると (p−1)/2 + (q−1)/2 ≡ (pq−1)/2 (mod 2)、従って上の式はこうなる:
　　m+n ≡ [(p+1)/2] × [(p−1)/2 + (q−1)/2 + (q−1)/2] (mod 2)　☆
(q−1)/2 は、偶数だとしても奇数だとしても、2倍すれば偶数: (q−1)/2 + (q−1)/2 ≡ 0 (mod 2)。上の式はこう簡約される:
　　m+n ≡ [(p+1)/2] × [(p−1)/2] (mod 2)
この右辺は、連続する2整数の積なので、因子の一方は偶数。ゆえに m+n は偶数。

変数名などの多少の変更はあるが、上記は Vorlesungen (1863) に基づく。原論文 (1854) では ☆ の後、次のような処理になっている:
　　= (p+1)/2 × [(p−1)/2] + (p+1)/2 × [(q−1)/2 + (q−1)/2]
　　= (p²−1)/4 + (p+1)(q−1)/2 = 偶数 + 偶数
実際、奇数の平方は ≡ 1 (mod 8) なので (p²−1) は8の倍数、従って (p²−1)/4 は偶数。(p+1) と (q−1) はどちらも偶数なので (p+1)(q−1)/2 も偶数。

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, p) で表す: p を3以上の素数、a を p の倍数ではない整数として、a が mod p の平方剰余なら L(a, p) = 1、非剰余なら L(a, p) = −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 = 3³ は、8k+3型の素因数 3 を含む。 L(29, 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 の Vorlesungen über Zahlentheorie §50 に沿って紹介する。Gauß 自身、「ずいぶん長い間、努力を逃れた定理」（＝何日考えても、なかなか捕捉できなかった）と告白している。Dirichlet は「極度に鋭敏な考察」とコメント。

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

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

〔注意〕　上記の命題の証明には、「合成数を法とする剰余」の理論（DA 105; VüZ §37）が必要――それは、奇素数べきを法とする剰余の理論（DA 100/101; VüZ §35）、2のべきを法とする剰余の理論（DA 103; VüZ §36）に依存する。それらについては、このメモではまだきちんと説明されていない。

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

〔解説〕　r² ≡ Q (mod M) なので r² − Q = Mの倍数、つまり Q = r² − Mの倍数。もしも r と M が互いに素でなく、2以上の公約数 g で割り切れるなら、Ｑ も g で割り切れる――これは「M と Q が互いに素」という上記事実に反する。

〔例2〕　例1の場合、M = 1⋅2⋅3⋅4⋅5 と r = ±7, ±13, ±17, or ±23 は互いに素。

r² ≡ Q (mod M) という事実を使って、r(Q − 1²)(Q − 2²)(Q − 3²)…(Q − m²) という積を考えると:
　　r(Q − 1²)(Q − 2²)(Q − 3²)…(Q − m²)
　　≡ r(r² − 1²)(r² − 2²)(r² − 3²)…(r² − m²)
　　≡ r[(r − 1)(r + 1)][(r − 2)(r + 2)][(r − 3)(r + 3)]…[(r − m)(r + m)] (mod M)
この右辺（A とする）は r − m から r + m までの全整数の積。並び替えると:
　　≡ (r − m)…(r − 3)(r − 2)(r − 1)r(r + 1)(r + 2)(r + 3)…(r + m)
つまり連続 2m+1 個の整数の積に等しいので、A は (2m+1)! つまり M で割り切れる。

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

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

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

まとめると、「2m+1 以下のどの奇素数を法としても Q は平方剰余」という条件が満たされるなら、上記 B は Q で割り切れて整数になる。逆に言えば（対偶）、もし B が Q で割り切れないなら、「2m+1 以下のどの奇素数を法としても Q は平方剰余」という条件は満たされていない。

〔例4〕　例3では B = (409−1²)(409−2²) = 165240 が M = 5! で割り切れる。

さて M = (2m+1)(2m)(2m−1)(2m−2)…3⋅2⋅1 の因子を並び替えると:
　　M = (m+1) [(m+2)(m)] [(m+3)(m−1)] [(m+4)(m−2)]…[(2m+1)(1)]

〔解説〕　仮に m = 3, 2m+1 = 7 として 7⋅6⋅5⋅4⋅3⋅2⋅1 の掛け算を真ん中の m+1 = 3+1 = 4 から始め、左・右、左・右…の順序で一つずつ端まで進めた場合、こうなる:
　　(4)[(5)(3)][(6)(2)][(7)(1)]　　← 右端の因子は [(2m+1)(1)]
　　= (3+1)[(3+2)(3)][(3+3)(3−1)][(3+4)(3−2)]　　← 右端の因子は [(2m+1)(1)]

便宜上 u = m+1 と置くと m+2 = m+1+1 = u+1, m = m+1−1 = u−1 等々となって:
　　M = (u) [(u+1)(u−1)] [(u+2)(u−2)] [(u+3)(u−3)]…[(u+m)(u−m)]
　　= (u) [u² − 1²] [u² − 2²] [u² − 3³]…[u² − m²]　　← m+1 因子
　　= (m+1) [(m+1)² − 1²] [(m+1)² − 2²] [(m+1)² − 3³]…[(m+1)² − m²]　　← m+1 因子

今、この M で、上記の…
　　B = (1)(Q − 1²)(Q − 2²)(Q − 3²)…(Q − m²)　　← m+1 因子
…を割り算して、長い分数の分子・分母を因子ごとに切り離して書くと:
　　B/M = {1/(m+1)} × {(Q−1²)/[(m+1)² − 1²]} × {(Q−2²)/[(m+1)² − 2²]}
　　× {(Q−3²)/[(m+1)² − 3³]} × … × {(Q−m²)/[(m+1)² − m²]}

〔例5〕　例3では B/M = (1/3)[(409−1²)/(3²−1²)][(409−2²)/(3²−2²)] = 1377。

B/M は必ず整数になるわけではない。もし m の値として、√Q の端数を切り捨てた整数を選ぶと:
　　m < √Q < m+1　従って　m² < Q < (m+1)²
すなわち、この m に関する限り、Q は (m+1)² より小さく、従って B/M の式の各 {} 内は（分子・分母が正で、分子が分母より小さいので） 1 未満の正の有理数: この場合、それらの積である B/M は 1 未満の正の数――整数ではない。

ところで √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 は整数にならない。ゆえに、この 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 の非剰余）。ちなみに:
7899² ≡ 3, 12086² ≡ 5, 3258² ≡ 7, 15239² ≡ 11, 4935² ≡ 13, 5043² ≡ 17, 10890² ≡ 19 (mod 53881)

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

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

どうして E(100/3⁴) で止まっていいのか？　E(100/3⁵) 以降は考えなくていいのか？

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

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

同様に考えると、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) 回、割り切れる―― p² > 100 なので、E(100/p²) = 0 以降は結果に影響しない。特に、50～100 の範囲での素数では、1 回しか割り切れない。結局:
　　100! = 2⁹⁷⋅3⁴⁸⋅5²⁴⋅7¹⁶
　　 × 11⁹⋅13⁷⋅17⁵⋅19⁵⋅23⁴⋅29³⋅31³⋅37²⋅41²⋅43²⋅47²
　　 × 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/p²) + E(12/p³) + …
一方、分母に含まれる p の個数は:
　　E(5/p) + E(5/p²) + E(5/p³) + …
　　+ E(7/p) + E(7/p²) + E(7/p³) + …

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

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

これを証明するには、項ごとに比較して
　　E(N/p) ≥ E(a/p) + E(b/p)
　　E(N/p²) ≥ E(a/p²) + E(b/p²)
　　E(N/p³) ≥ E(a/p³) + E(b/p³)
　　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 = 5¹ = 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 = 2² = 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 / 1! = 2 は
　　(x+y)² = x² + 2xy + y²
の係数として現れる。

3 × 2 / 2! = 3 は
　　(x+y)³ = x³ + 3x²y + 3xy² + y³
の係数として現れる。

4 × 3 × 2 / 3! = 4 と 4 × 3 / 2! = 6 は
　　(x+y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴
の係数として現れる。

5 × 4 × 3 × 2 / 4! = 5 と 5 × 4 × 3 / 3! = 10 は
　　(x+y)⁵ = x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵
の係数として現れる。

6 × 5 × 4 × 3 × 2 / 5! = 6 と 6 × 5 × 4 × 3 / 4! = 15 と 6 × 5 × 4 / 3! = 20 は
　　(x+y)⁶ = x⁶ + 6x⁵y + 15x⁴y² + 20x³y³ + 15x²y⁴ + 6xy⁵ + y⁶
の係数として現れる。

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

文献

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 に相当）。Arith- の th- は普通に t と発音。それ以外の /k, t/ は息を吐かずに抑えた感じで発音。

◆オリジナル（ラテン語） https://archive.org/details/disquisitionesa00gaus
　↑スキャンの品質は十分だが重い。ブックマークなし。DjVu版なし。
別のスキャン https://www.e-rara.ch/zut/content/titleinfo/1254642
　↑高品質スキャン。軽い。章単位・ページ単位のブックマークあり。
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 （私信。174ページ～）
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種以上、時代順にリストアップ。

---