遊びの数論57　おばあちゃんとガウス和

他のメモへのリンク集。リンク集を飛ばして、このページの前書きへ。本文の目次へ。21、22などの数字は、メモの番号です。

---

『遊びの数論56』の続き。誤字脱字・間違いがあるかも。

---

• 目次。約7の項目があります。2026などの数字は、メモの日付です。
• 2026-03-13　おばあちゃんとガウス和（その2）
• 2026-03-18　おばあちゃんとガウス和（その3）
• 2026-03-19　おばあちゃんとガウス和（その4）
• 2026-03-20　奇数 1, 3, 5, ··· を 2 乗して
• 2026-03-22　4 個の解を持つ2次方程式　mod 2ⁿ
• 2026-03-24　49 を 32 で割ると 17 余ります。それでは···
• 2026-04-01　sin の積と（拡張された）ガウスの補題
• 目次の終わり。このページの最初の項目が続きます。

---

2026-03-13　おばあちゃんとガウス和（その2）

n = 2H + 1 を 3 以上の任意の奇数、 π = 180° を n 等分した角度を P とすると、次の値はいずれも ±√n に等しい:
　　∏ 2 sin kP, ∏ 2 sin (2k)P, ∏ 2 sin (4k)P, ∏ 2 sin (8k)P, etc.
　　∏ 2 sin (2k−1)P, ∏ 2 sin (4k−2)P, ∏ 2 sin (8k−4)P, etc.
積は k = 1, 2, ···, H にわたる。

n = 9 の場合（H = 4）、例えば:
　　∏ 2 sin kP = (2 sin 20°)(2 sin 40°)(2 sin 60°)(2 sin 80°) = √9 = 3,
　　∏ 2 sin (2k)P = (2 sin 40°)(2 sin 80°)(2 sin 120°)(2 sin 160°) = √9 = 3,
　　∏ 2 sin (4k−2)P = (2 sin 40°)(2 sin 120°)(2 sin 200°)(2 sin 280°) = √9 = 3

なかなかきれいなパターン。上記第一の例から因子 2 sin 60° = √3 を除外すると、
　　(2 sin 20°)(2 sin 40°)(2 sin 80°) = √3
　　∴　sin 20° × sin 40° × sin 80° = (√3)/8
となるが、それは Morrie の法則
　　cos 20° × cos 40° × cos 80° = 1/8
の sin 版とでもいうべきもので、どちらも眺めて楽しい。浅ましいことの多い世の中で、一服の清涼剤。前回、「ガウス和に関連する」という理由から天下り的に ∏ 2 sin (4k−2)P を話題とし、その符号を場当たり的に決定したが、その問題も、もう少し大きな絵の中のピースとして捉えると展望が利き、景色を楽しめる。

∏ 2 sin kP すなわち ∏{k=1 to H} 2 sin [k⋅(π/n)] が √n に等しいことは既知（命題3）。ここで n は 3 以上の奇数、 H = (n − 1)/2 は正の整数で、奇数 n の半分（端数切り捨て）。よって 2H = n − 1, n = 2H + 1。

∏ 2 sin (2k)P が同じ値 √n を持つことを確かめるのは、易しい（命題7）。それには、
　　甲　k = 1, 2, 3, ···, H　に対する　∏ 2 sin kP　（正の積）と
　　乙　2k = 2, 4, 6, ···, 2H　に対する　∏ 2 sin (2k)P　が等しい
ことを示せばいい。仮定により π = nP。任意の θ について sin θ = sin (π − θ) が成り立つので、 θ = kP と置けば:
　　sin kP = sin (nP − kP) = sin (n − k)P
つまり k が奇数のとき、 sin kP を sin (n − k)P に置き換えても値は変わらない（n は奇数だから n − k は偶数）。よって甲の k たちのうち各奇数を、 H が偶数なら〚あるいは奇数なら〛
　　n−1, n−3, n−5, ···, n−(H−1) 〚あるいは n−H〛
　　つまり　2H, 2H−2, 2H−4, ···, H+2 〚あるいは H+1〛
に置換していい。置換結果の上記偶数たちと、もともと甲に含まれる偶数たちを合わせれば、結果
　　{2, 4, 6, ···, H 〚あるいは H−1〛} ∪ {H+2 〚あるいは H+1〛, ···, 2H−4, 2H−2, 2H}
は、乙の 2k たちと一致。つまり甲と乙は、等しい値を持つ。同様に、甲に含まれる偶数を奇数に置換することで、 ∏ 2 sin (2k−1)P も等しい値を持つことが示される。

命題10　n = 2H + 1 が 3 以上の奇数なら（H = (n − 1)/2 は正の整数）:
　〘ⅰ〙　∏{k=1 to H} 2 sin [(2k)⋅2π/n] = ±√n
符号は n が 8 の倍数 + 1 or 7 ならプラス、 8 の倍数 + 3 or 5 ならマイナス。
　〘ⅱ〙　∏{k=1 to H} 2 sin [(2k − 1)⋅2π/n] = ±√n
符号は n が 8 の倍数 + 1 or 3 ならプラス、 8 の倍数 + 5 or 7 ならマイナス。

証明　Q = 2P と置くと Q は 2π = 360° の n 等分点。まず ∏ 2 sin (4k)P = ∏ 2 sin (2k)Q が乙と同じ絶対値 √n を持つこと、言い換えると
　　丙　k = 1, 2, 3, ···, H　に対する　∏ 2 sin kQ = ∏ 2 sin 2kP　（乙と同じ正の積）と
　　丁　2k = 2, 4, 6, ···, 2H　に対する　∏ 2 sin (2k)Q
が同じ絶対値を持つことを、示そう。仮定により 2π = nQ。恒等式 sin θ = −sin (−θ) = −sin (2π − θ) で θ = kP と置けば:
　　sin kQ = −sin (nQ − kQ) = −sin (n − k)Q　　⓺
つまり k が奇数のときの sin kQ を、 sin (n − k)Q に置き換えてもその sin の絶対値は変わらず、符号だけが反転する。よって丙の k たちのうち各奇数を、⓺により偶数 n − k に置き換えると、結果として生じる新しい積（丁）と丙の値（＝乙の値）は、絶対値が同じ。

よって問題は、「因子の符号反転が、最終結果にどう影響するか」。

〘ⅰ〙　新しい積（丁）の符号は、置き換えられる k が（言い換えれば、置き換えられる sin が）偶数個か奇数個かに応じて、もともとの積の ±1 倍。従って、丁の符号は、
　　数列　1, 2, 3, 4, ···, H　　（✽）
の中に奇数が幾つあるかによって決まる。

ケース1（H が偶数）　（✽）は、奇数と偶数を H/2 個ずつ含むので: もともとの積が −1 倍される ⇔ H/2 が奇数 ⇔ 2H が奇数の 4 倍 ⇔ n = 2H + 1 が (4 の奇数倍) + 1 ⇔ n が (8 の倍数 + 4) + 1。

ケース2（H が奇数）　（✽）は、奇数を (H + 1)/2 個、偶数を (H − 1)/2 個含むので: もともとの積が −1 倍される ⇔ (H + 1)/2 が奇数 ⇔ 2H + 2 が奇数の 4 倍 ⇔ n = 2H + 1 が (4 の奇数倍) − 1 ⇔ n が (8 の倍数 + 4) − 1。

要するに、丁の積は、奇数 n が 8 の倍数 + [3 or 5] なら負で、それ以外（8 の倍数 + [1 or 7] なら）正。

〘ⅱ〙　同様に ∏ 2 sin (4k−2)P = ∏ 2 sin (2k−1)Q は、乙の値の ±1 倍。符号は、（✽）の中に「奇数に置き換えられる偶数」が幾つあるかによって決まる。ケース1では、奇数も偶数も個数が同じなので、〘ⅰ〙と同じ議論がそのまま成り立つ。ケース2では、（✽）の中に偶数が (H − 1)/2 個含まれるので: もともとの積が −1 倍される ⇔ (H − 1)/2 が奇数 ⇔ 2H − 2 が奇数の 4 倍 ⇔ n = 2H + 1 が (4 の奇数倍) + 3 ⇔ n が (8 の倍数 + 4) + 3。

要するに、奇数 n が 8 の倍数 + [5 or 7] なら負で、それ以外（8 の倍数 + [1 or 3] なら）正。∎

上記〘ⅰ〙は新たな事実だが、〘ⅱ〙は、命題8・命題9の再々証明に過ぎない。ところで、符号反転の回数を毎回直接的にカウントすることは必須ではなく、次のように論じることもできる。

円周 n 等分点（1 + 0i を除く）のうち、偶数番の点の縦座標が〘ⅰ〙で、奇数番の点の縦座標が〘ⅱ〙なので、〘ⅰ〙と〘ⅱ〙の積 ±n は、それら全種類の正または負の sin の積。そのうち H 個が正（第1・第2象限の点）で、 H 個が負なので、 H が偶数か奇数かに応じて、この積は ±n に等しい。 H が偶数 2μ なら n = 2H + 1 = 4μ + 1 だし、 H が奇数 2μ+1 なら n = 2H + 1 = 4μ + 3 なので、〘ⅰ〙の符号か〘ⅱ〙の符号のどちらか一方が分かれば、他方は自動的に定まる。例えば前者を既知とすると、次の状況から、〘ⅱ〙の符号が順に + + − − であることは明白。

n = 8 の倍数 +	1	3	5	7
〘ⅰ〙の符号	+	−	−	+
〘ⅱ〙の符号	?	?	?	?
〘ⅰ〙×〘ⅱ〙	+n	−n	+n	−n

命題11　命題10と同じ条件において:
　〘ⅲ〙　∏{k=1 to H} 2 sin [(2k)⋅4π/n] = +√n
符号は常にプラス。
　〘ⅳ〙　∏{k=1 to H} 2 sin [(2k − 1)⋅4π/n] = (−1)^H⋅√n
符号は n が 4 の倍数 + 1 ならプラス、 4 の倍数 + 3 ならマイナス。

証明　R = 2Q と置くと R は 4π = 720° の n 等分点。〘ⅲ〙について。命題10〘ⅰ〙を基準に ∏ 2 sin (8k)P = ∏ 2 sin (4k)Q = ∏ 2 sin (2k)R を考えると、
　　k = 1, 2, 3, ···, H　に対する　∏ 2 sin kR　（丁と同じ積）
と比べて、もし k = 2, 4, 6, ··· , 2H なら同じ ∏ 2 sin kR の符号はどうなるか？を考えればいい。仮定により 4π = nR。恒等式 sin θ = −sin (−θ) = −sin (4π − θ) で θ = kR と置けば:
　　sin kR = −sin (nR − kR) = −sin (n − k)R
すなわち命題10と全く同様に、 k = 1, 2, 3, ··· , H に含まれる奇数を偶数に置き換えると、絶対値は変わらず、区間 [1, H] に奇数が奇数個含まれているときのみ、最終結果において、符号が反転する。命題10〘ⅰ〙から、この符号反転は n ≡ 3, 5 (mod 8) と同値であることが分かっている。もともとの符号は n ≡ 1, 3, 5, 7 に対応して + − − + なので（そして n ≡ 3, 5 のときだけ、符号が反転するのだから）、真ん中の二つの符号を反転させて、結果は + + + + つまり常に正。

〘ⅳ〙について。ここでも命題10〘ⅰ〙を基準に考えると、命題10〘ⅱ〙から、符号反転は n ≡ 5, 7 (mod 8) と同値。もともとの符号 + − − + の後ろの二つの符号を反転させて、結果は + − + − となる。つまり n ≡ 1, 5 (mod 8) なら正、 ≡ 3, 7 (mod 8) なら負。要するに n ≡ 1 (mod 4) なら正、 ≡ 3 (mod 4) なら負。∎

符号が常にプラスの ∏ 2 sin (2k)P を基準に ∏ 2 sin (4k)P と ∏ 2 sin (4k−2)P の符号をそれぞれ（n を mod 8 で分類して）決定し、さらに前者の符号を基準に ∏ 2 sin (8k)P と ∏ 2 sin (8k−4)P の符号をそれぞれ決定した。すると ∏ 2 sin (8k)P は、再び符号が常にプラスになった。もしそれを基準に ∏ 2 sin (16k)P と ∏ 2 sin (16k−8)P の符号を求め…と続けていくなら、同じパターンがループする。

明示的には扱っていない ∏ 2 sin (16k)P 以降も含めて、全てを一つにまとめると、次の通り。比較的シンプルな周期性がある。

命題12　n を 3 以上の任意の奇数、 h を 1 以上の任意の整数とするとき:
　〘ⅰ〙　∏{k=1 to (n−1)/2} 2 sin [(2^2h−1k)π/n] = √n
　〘ⅱ〙　∏{k=1 to (n−1)/2} 2 sin [(2^2hk)π/n] = (−1)^(nn−1)/8⋅√n
　　　符号は n ≡ 1, 3, 5, 7 (mod 8) に応じて + − − +
　〘ⅲ〙　∏{k=1 to (n−1)/2} 2 sin [(2^2hk − 2^2h−1)π/n] = (−1)^⌊n/4⌋⋅√n
　　　符号は n ≡ 1, 3, 5, 7 (mod 8) に応じて + + − −
　〘ⅳ〙　∏{k=1 to (n−1)/2} 2 sin [(2^2h+1k − 2^2h)π/n] = (−1)^(n−1)/2⋅√n
　　　符号は n ≡ 1, 3 (mod 4) に応じて + −
　〘ⅴ〙　n ≡ 1 (mod 8) なら〘ⅰ〙～〘ⅳ〙の符号は全てプラス。

天下り的に命題8ないし命題9（それは上記〘ⅲ〙で h = 1 の場合である）だけを提示するのは、若干せせこましかった。（下に続く）

---

2026-03-18　おばあちゃんとガウス和（その3）

1796年のちょうど今ごろ（日記によると3月30日）。朝ベッドから起き上がろうとした19歳の少年ガウスの頭に、ふと「正17角形は、定規とコンパスだけで作図可能だぞ！」というアイデアがひらめいた。

円形のパイやケーキを4等分あるいは6等分することは難しくない。切る前の状態で、切り口になる外周の点を結べば、円に内接する正方形や正六角形が得られる。それと同様に、17等分も（理論的には）簡単にできる――と、ガウスは気付いたのだった。この発見をしたことで、ガウスは数学者になる決意をしたのだという。

もっとも、ガウスが本当に考えていたのは「正17角形は作図可能だろうか？」という具体的問題ではなく、「複素平面上で単位円の n 等分点に当たる数」の性質について。 n = 17 の場合の上記観察は、その副産物だった。

「ガウス和」（ガウスの和）というのは、 r が 1 の原始 n 乗根のときの、
　　r⁰² + r¹² + r²² + ··· + r⁽ⁿ⁻¹⁾²
という和（指数は 0, 1, 4, 9 などの平方数）。この和は、上記のような研究において重大な意味を持つばかりか、いろいろな深い事柄（特に、平方剰余の相互法則）とも密接に関連している。「正17角形の作図可能性」はクールな発見だが、その理論の土台ともいえる「ガウス和」には難しい部分があり、ガウスを4年以上にわたって悩ませることになる。

n が 3 以上の奇数のとき、ガウス和は、
　　r^0⋅0 + r^1⋅1 + r^2⋅2 + ··· + r^{(n−1)(n−1)} = (r¹ − r⁻¹)(r³ − r⁻³)(r⁵ − r⁻⁵)···(rⁿ⁻² − r⁻⁽ⁿ⁻²⁾)
という関係を満たす。ここで r は 1 の原始 n 乗根。左辺はガウス和の定義であり、その値を確定するには、右辺の積を決定すればいい。 ガウス和は r の選択に依存する。最もシンプルな選択肢として、
　　r = cos (2π/n) + i sin (2π/n)
として、それを仮に「基本のガウス和」と呼ぶなら、
　　r^k = cos (2πk/n) + i sin (2πk/n)
　　r^−k = cos (2πk/n) − i sin (2πk/n)
　　∴　r^k − r^−k = 2i sin (2πk/n)
であるから、決定すべき積は、
　　(2i sin (2π⋅1/n))(2i sin (2π⋅3/n))(2i sin (2π⋅5/n))···(2i sin (2π⋅(n−2)/n))
に等しい。コンパクトに表記すれば、
　　∏{k=1 to (n−1)/2} 2i sin [2π(2k − 1)/n] = i^(n−1)/2 × ∏{k=1 to (n−1)/2} 2 sin [2π(2k − 1)/n]
に等しい。

この最後の右辺の ∏ が n ≡ 1, 3, 5, 7 (mod 8) に応じて = +√n, +√n, −√n, −√n であることについては、「おばあちゃんの公式」との関連で、既に何度も証明した（命題8、命題9、命題10〘ⅱ〙）。 n ≡ 1, 3, 5, 7 (mod 8) に応じて i^(n−1)/2 が = 1, i, −1, −i であることは明白。よって両者の積は:
　　n ≡ 1, 3, 5, 7 (mod 8) に応じて　+√n, +i√n, +√n, +i√n

要するに n が奇数のときの「基本のガウス和」は、 n が 4μ + 1 の形なら √n で、 n が 4μ + 3 の形なら i√n = √−n である。定理10が再証明された。

この結論はシンプルだし、数値実験によって（証明前に）容易に予想がつく。証明のうち、上記の部分も易しい（もし sin 2θ の積に関する公式が事前に準備されていないとしても、その場で同じ結論を導くことは難しくない）。しかしながら、この議論の出発点となる等式――すなわち r に関連するガウス和は、積
　　(r¹ − r⁻¹)(r³ − r⁻³)(r⁵ − r⁻⁵)···(rⁿ⁻² − r⁻⁽ⁿ⁻²⁾)
に等しい、という事実（公式8）――を導くことは、単純ではない。一つ一つのステップは特に難解ではなく、むしろ「おっとりとした古典数論」とも感じられるのだが、論理の連鎖がトリッキーで、素朴な観点からは「どうしてこんな道筋で証明できるのか」「どうやってこんな証明法を思い付けるのか」という感じがする。

「おばあちゃんの cos の公式」と類似の sin の公式は、二つの異なる文脈において、ガウス和の計算に応用可能。その一つは上記の通りで、そのような公式を使うまでもない計算ではあるが、これはこれで面白い。もう一つの場面については、次回に。

ところで、これらの sin の公式のうち命題10の〘ⅰ〙は n ≡ 1, 3, 5, 7 (mod 8) に応じて + − − + となり、同〘ⅱ〙は + + − − となる。これらの ± の振る舞いは、相互法則の第二補充法則を連想させる。それもそのはずで、命題10などの証明の手法は、実質的に、相互法則の証明で使われる「ガウスの補題」を使っているのと同じこと。別の言い方をすると、命題10では見掛け上 sin に関する恒等式を証明しているけれど、本質的には、それは第二補充法則の証明でもある。逆に言うと、「第二補充法則の証明で使われる簡単化のテクニック」を命題10の証明に流用することもできる。（下に続く）

---

2026-03-19　おばあちゃんとガウス和（その4）

q が 3 以上の奇数のとき:
　　∏{k=1 to (q−1)/2} 2 sin [(2k − 1)⋅4π/q] = (−1)^(q−1)/2⋅√q
この性質を「n が偶数のときのガウス和」の議論に利用できる（Nagell [2], pp. 178–180）。

n を任意の正整数、 ℓ を n と互いに素な任意の整数として、一般のガウス和を
　　S(ℓ, n) = ∑{x=1 to n} exp (2πiℓx²/n)
と定義する（便宜上、総和の範囲を 0 から n−1 の代わりに 1 から n とする。§44の末尾と§45参照）。

n が 3 以上の奇数のとき、 S(1, n) = √n ないし = i√n であることは既知。奇数 n = 1 も同じ性質を満たす（定義により S(1, 1) = 1 = √1）。

n が（2 以上の）偶数だとどうなるか？　もし n が「4 で割り切れない偶数」なら S(1, n) = 0 が成り立つ（§23）。問題はそれ以外のケース―― n が 4 の倍数の場合の S(1, n) を決定したい。

一般に、正整数 a, b が互いに素なら、次が成り立つ:
　　S(1, ab) = ∑{x=1 to ab} exp (2πix²/(ab)) = ∑{y=1 to b} ∑{z=1 to a} exp [2πi(ay + bz)²/(ab)]
なぜなら、もし y たちが mod b の代表の一組^†で z たちが mod a の代表の一組なら、対応する ay + bz たちは mod ab の代表の一組。言い換えると、 y mod b または z mod a の少なくとも一方の選択が異なれば、 ay + bz mod ab も不合同。実際、 ay + bz ≡ ay′ + bz′ (mod ab) は ay ≡ ay′ (mod b) を――従って y ≡ y′ (mod b) を――含意し、同様に z ≡ z′ (mod a) を含意する（a, b は互いに素だから）。

†　剰余類は、単に類（クラス）とも呼ばれる。ちょうど M 個の元（要素）を持つ集合があって、その元たちが mod M の（計 M 個の）類を過不足なく代表するとき、その集合（あるいは、集合の元たち）は、 mod M の代表の一組、または剰余系と呼ばれる（a complete residue system; 別名 a complete set of residues）。「完全な代表の一組」「完全剰余系」「剰余の一組」などとも呼ばれる。ここで「ある類を代表する」というのは、単に「その類に属する」という意味。その類のメンバーでさえあれば「誰でも代表になれる」。例えば「その類に属する最小の負でない整数」といった条件は（最も素朴な代表元の選び方ではあるけれど）、必須ではない。

上記・右辺の (ay + bz)² を展開して生じる項のうち 2abyz は、 exp の値に影響しないので、無視してよい:
　　S(1, ab) = ∑{y=1 to b} ∑{z=1 to a} exp [2πi(a²y² + b²z²)/(ab)]
　　 = ∑{y=1 to b} ∑{z=1 to a} exp [2πi(ay²)/b + 2πi(bz²)/a]
　　 = ∑{y=1 to b} ∑{z=1 to a} [exp (2πiay²/b) ×  exp (2πibz²/a)]
　　 = ∑{y=1 to b} exp (2πiay²/b) × ∑{z=1 to a} exp (2πibz²/a) = S(a, b) S(b, a)

特に a = 2^t, b = q と置くと:

命題13　t が 2 以上の整数（2^t が 4 の倍数）で q が正の奇数なら:
　　S(1, 2^tq) = S(2^t, q) S(q, 2^t)

命題13の右辺・第1因子について。もし t = 2h が偶数なら:
　　S(2^t, q) = ∑{x=1 to q} exp (2πi⋅2^2hx²/q) = ∑{x=1 to q} exp [2πi⋅(2^hx)²/q]
x の値が mod q の各類をちょうど一度ずつ代表するとき、 y = 2^hx の値も同じ性質を持つから:
　　 = ∑{y=1 to q} exp (2πiy²/q) = S(1, q)
S(1, q) は q ≡ ±1 (mod 4) に応じて √±q に等しい。

一方、もし t = 2h + 1 が奇数なら:
　　S(2^t, q) = ∑{x=1 to q} exp (2πi⋅2^2h+1x²/q) = ∑{x=1 to q} exp [2πi⋅2(2^hx)²/q]
　　 = ∑{y=1 to q} exp (2πi⋅2y²/q) = S(2, q)
ガウス和 S(2, q) に関連する 1 の原始 q 乗根は、
　　r = exp (4πi/q) = cos (4π/q) + i sin (4π/q)
なので、公式8と命題11〘ⅳ〙を使うと:
　　S(2, q) = (r¹ − r⁻¹)(r³ − r⁻³)(r⁵ − r⁻⁵)···(r^2q−2 − r^−(2q−2))
　　 = ∏{k=1 to (q−1)/2} 2i sin [(2k − 1)⋅4π/q] = i^(q−1)/2⋅(−1)^(q−1)/2⋅√q = (−i)^(q−1)/2⋅√q

以上によって、任意の 4 の（正の）倍数 n = 2^tq について、命題13
　　S(1, 2^tq) = S(2^t, q) S(q, 2^t)
の右辺・第1因子の値が確定した:

命題14　t を 2 以上の整数、 2^t を 4 の倍数、 q を正の奇数とする。もし t が偶数で q ≡ 1 (mod 4) なら:
　　S(1, 2^tq) = √q × S(q, 2^t)
t が偶数で q ≡ −1 (mod 4) なら:
　　S(1, 2^tq) = i√q × S(q, 2^t)
一方、もし t が奇数なら:
　　S(1, 2^tq) = (−i)^(q−1)/2⋅√q × S(q, 2^t)

いずれの場合も、残る問題は S(q, 2^t) の値。そのうち t = 2, 3 のケース――S(q, 4) と S(q, 8)――は、容易に直接計算可能（定理38）。 t が 4 以上の場合の S(q, 2^t) を決定したい。その目的のため、 Nagell は漸化式 S(q, 2^t) = 2 S(q, 2^t−2) を導く。導出法は Hua バージョンほど簡潔ではないけれど、興味深い点もある。

m = 2^t と置いて（t ≥ 4）、 x の偶奇によって和を二つの部分和に分けると:
　　S(q, m) = ∑{x=1 to m} exp (2πiqx²/m)
　　 = ∑{y=1 to m/2} exp [2πiq(2y)²/m] + ∑{y=1 to m/2} exp [2πiq(2y − 1)²/m]　　（✽）

（✽）の右辺の一つ目の ∑ において、分母・分子を 4 で割り m/4 = 2^t−2 を μ と置くと:
　　∑{y=1 to 2μ} exp (2πiqy²/(m/4)) = ∑{y=1 to μ} exp (2πiqy²/μ) + ∑{y=μ+1 to 2μ} exp (2πiqy²/μ)
　　 = S(q, μ) + S(q, μ) = 2S(q, μ)

なぜなら集合 {1, 2, ···, μ} と集合 {μ+1, μ+2, ···, 2μ} は、どちらも mod μ の代表の一組。

（✽）の右辺の二つ目の ∑ は 0 に等しい（後述）。暫定的にそれを承認するなら、（✽）は上記 2S(q, μ) = 2S(q, 2^t−2) に等しく、漸化式
　　S(q, 2^t) = 2S(q, 2^t−2)
を得る。よって、
　　S(q, 2⁴) = 2S(q, 2²)
　　S(q, 2⁶) = 2S(q, 2⁴) = 2²S(q, 2²)
　　S(q, 2⁸) = 2S(q, 2⁶) = 2²S(q, 2⁴) = 2³S(q, 2²)
　　　︙
となり、一般に t = 2h が 4 以上の偶数なら:
　　S(q, 2^t) = S(q, 2^2h) = 2^h−1⋅S(q, 4) = 2^t/2−1⋅S(q, 4) = 2^(t−2)/2⋅S(q, 4)
この等式は、 t = 2 の場合にも、形式的に有効。同様に、
　　S(q, 2⁵) = 2S(q, 2³)
　　S(q, 2⁷) = 2S(q, 2⁵) = 2²S(q, 2³)
　　S(q, 2⁹) = 2S(q, 2⁷) = 2²S(q, 2⁵) = 2³S(q, 2³)
　　　︙
となり、一般に t = 2h + 1 が 5 以上の奇数なら:
　　S(q, 2^t) = S(q, 2^2h+1) = 2^h−1⋅S(q, 8) = 2^{(t−1)/2−1}⋅S(q, 8) = 2^(t−3)/2⋅S(q, 8)
この等式は、 t = 3 の場合にも、形式的に有効。

上記の観察から、次の命題を得る。

命題15　t が 2 以上の偶数の場合、 q ≡ ±1 (mod 4) に応じて:
　　S(q, 2^t) = (1 ± i)⋅2^t/2
一方、 t が 3 以上の奇数の場合:
　　S(q, 2^t) = (1 + i)⋅i^(q−1)/2⋅2^t/2

証明　既に導いたように、 t が（2 以上の）偶数なら
　　S(q, 2^t) = 2^(t−2)/2⋅S(q, 4)
で、 t が（3 以上の）奇数なら
　　S(q, 2^t) = 2^(t−3)/2⋅S(q, 8)
だ。ところが S(q, 4) は q ≡ ±1 (mod 4) に応じて 2⋅(1 ± i) に等しい（定理38）。よって t が偶数なら:
　　S(q, 2^t) = 2^(t−2)/2⋅2^2/2⋅(1 ± i) = 2^t/2⋅(1 ± i)
一方、 S(q, 8) は (1 + i)⋅i^(q−1)/2⋅√8 に等しい（定理38の補足）。よって t が奇数なら:
　　S(q, 2^t) = 2^(t−3)/2⋅(1 + i)⋅i^(q−1)/2⋅2^3/2 = 2^t/2⋅(1 + i)⋅i^(q−1)/2　∎

命題14と命題15を組み合わせることで、次の結論に至る。 t が 2 以上の偶数の場合、もし q ≡ 1 (mod 4) なら
　　S(1, 2^tq) = √q × S(q, 2^t) = √q × (1 + i)⋅2^t/2
だし、もし q ≡ −1 (mod 4) なら
　　S(1, 2^tq) = i√q × S(q, 2^t) = i√q × (1 − i)⋅2^t/2 = √q × (1 + i)⋅2^t/2
で、どちらの場合も:
　　S(1, 2^tq) = (1 + i)⋅√(2^tq)
一方、 t が 3 以上の奇数の場合:
　　S(1, 2^tq) = (−i)^(q−1)/2⋅√q × S(q, 2^t) = (−i)^(q−1)/2⋅√q × (1 + i)⋅i^(q−1)/2⋅2^t/2
因子 (−i)^(q−1)/2 と因子 i^(q−1)/2 の積は 1 だから、この場合も:
　　S(1, 2^tq) = √q × (1 + i)⋅2^t/2 = (1 + i)⋅√(2^tq)

結局、 4 の任意の倍数 n = 2^tq について（q は正の奇数）、次が成り立つ:
　　S(1, n) = (1 + i)√n

この結論は、定理21と一致する。定理21は（ガウス自身がやったように）、多項式についての「第二の恒等式」（公式13）から、複雑なプロセスを経て導出された。 Hua が示唆し、 Nagell がここで行っているように、「第二の恒等式」を使わずに n が偶数の場合のガウス和を求めることもできる―― n が奇数の場合のガウス和についての知識と「n が合成数の場合の公式」「n = 4, 8 の場合のガウス和」を組み合わせることによって。

この議論を完成させるには、後回しにした一つの問題を解決する必要がある。それは、（✽）の右辺の二つ目の ∑ が 0 に等しいことの証明、つまり
　　∑{y=1 to m/2} exp [2πiq(2y − 1)²/m] = 0
の証明。この種の文脈で頻出する「消滅する部分和」の変種だが、 Nagell の論法は必ずしも分かりやすくない。その趣旨は次の通り。奇数 2y − 1 の平方は 8z + 1 の形の奇数（理由）。 mod m において（m = 2^t, t ≥ 4）、その形の数で代表される類はちょうど m/8 個ある（8 個に一つの割合で含まれるから）。 y が 1 から m/2 まで動くときの (2y − 1)² の m/2 種類の値は、上記 m/8 個の類をちょうど 4 回ずつ代表する（付録A参照）。つまり:
　　∑{y=1 to m/2} exp [2πiq(2y − 1)²/m] = 4 ∑{z=1 to m/8} exp [2πiq(8z + 1)/m]
　　 = 4 ∑{z=1 to m/8} [exp (2πiq⋅8z/m) exp (2πiq/m)]
ここで ∑ の内側の因子 exp (2πiq/m) の値は、変数 z に依存しない。この因子を ∑ の外側にくくり出し、残った因子に含まれる分数の分子・分母を 8 で割れば、その ∑ が m/8 種類の「1 の m/8 乗根」（原始 m/8 乗根に限らない。仮定により m/8 ≥ 2）の和だ、ということは明白。

「1 の m/8 乗根」たちの偏角はどれも q 倍されているが、全種類の「1 の m/8 乗根」が過不足なく現れることに変わりない。実際 q は奇数の定数なので、 z たちが（法 m/8 において）代表の一組なら、対応する qz たちも代表の一組。

従って、この総和は 0 に等しい。

「奇数 1, 3, 5, ··· をそれぞれ平方した値」の mod 2^t における挙動について、もう少しきちんと考えてみたい。（下へ続く）

---

2026-03-20　奇数 1, 3, 5, ··· を 2 乗して

奇数 1, 3, 5, 7, ··· の平方（つまり 1, 9, 25, 49, ···）は、どれも 8 で割ると 1 余る。たわいもないことだけど、最初に気付いたときには、それなりに面白く感じられる。慣れちゃうと「当たり前」としか思えないかもしれないけど。

証明は簡単。奇数は 2k + 1 の形の数なので（k は整数）、その平方をこう書くことができる。
　　(2k + 1)² = (2k)² + 2⋅2k⋅1 + 1² = 4k² + 4k + 1 = 4 × k(k + 1) + 1
ここで k と k + 1 は隣り合う二つの整数なので、その一方は偶数（k が偶数なら k + 1 は奇数だし、 k が奇数なら k + 1 は偶数）。だから、両者の積 k(k + 1) は必ず偶数。従って、
　　4 × k(k + 1) = 4 × 偶数 = 8 の倍数
　　∴　4 × k(k + 1) + 1 = 8 の倍数 + 1
なので、こいつを 8 で割ったら 1 余る。∎

では、奇数の平方を 16 で割った余り、 32 で割った余り、 64 で割った余り、等々は、どうなるのだろうか？

数値例の観察。ここでは奇数を 2k + 1 の形ではなく 2y − 1 の形で表し（本質的な違いはない）、最初の幾つかの正の奇数 a = 1, 3, 5, 7, 9, 11, ··· について、それぞれの平方を 16 で割った余り、 32 で割った余り、 64 で割った余りを一覧表にする。

【表1】 奇数 1, 3, 5, ···  の平方を 16, 32 などで割った余り

y →	1	2	3	4	5	6	7	8
N = 2y − 1	1	3	5	7	9	11	13	15
N2	1	9	25	49	81	121	169	225
N2 mod 16	1	9	9	1	1	9	9	1
N2 mod 32	1	9	25	17	17	25	9	1
N2 mod 64	1	9	25	49	17	57	41	33
y →	9	10	11	12	13	14	15	16
N = 2y − 1	17	19	21	23	25	27	29	31
N2	289	361	441	529	625	729	841	961
N2 mod 16	1	9	9	1	1	9	9	1
N2 mod 32	1	9	25	17	17	25	9	1
N2 mod 64	33	41	57	17	49	25	9	1

16 で割った余りを見ると、周期 4 で「1, 9; 9, 1」がループ。各周期内の前半「1, 9」と後半「9, 1」は同じ数たちが逆順で並んでいる。

32 で割った余りを見ると、周期 8 で「1, 9, 25, 17; 17, 25, 9, 1」がループ。各周期内の前半・後半には、同様の「鏡像」関係がある。このパターンが踏襲されるとすれば、 64 で割った余りは、周期 16 で循環するであろう（ここではサンプルが 16 個しかないので、具体例を観察できないが）。周期内の前半・後半の「鏡像」関係は、 64 で割った余りについても、確認される。

一般に m = 2^t で割った余り（t ≥ 4）は周期 m/4 で循環して、各周期内の前半の m/8 個の数と後半の m/8 個の数は、同じ数たちが逆順で並んでいる――と予想される。

予想が正しいか、順を追って検証してみる。

命題16（周期 m/4 での循環）　y = 1, 2, 3, ··· のとき、小さい順で「y 番目の（正の）奇数」は 2y − 1 だ。このとき:
　　〘ⅰ〙　16 で割った余りについて。 y + 4 番目の奇数の平方 (2(y + 4) − 1)² と y 番目の奇数の平方 (2y − 1)² は、どちらも 16 で割った余りが同じ。
　　〘ⅱ〙　一般に、 t を 4 以上の任意の整数として、 m = 2^t で割った余りを考える（t の値に応じて m = 16, 32, 64 など）。 y + m/4 番目の奇数の平方 (2(y + m/4) − 1)² と y 番目の奇数の平方 (2y − 1)² は、どちらも m で割った余りが同じ。

〔例〕　3 番目の奇数 5 の平方 25 と、 (3 + 16/4) 番目の奇数 13 の平方 169 は、どちらも 16 で割ると 9 余る。

証明　〘ⅰ〙　2(y + 4) − 1 = 2y + 8 − 1 を B とすると、それは 2y − 1 より 8 大きい。 2y − 1 を N と置くなら、 B = N + 8 だ。その平方
　　B² = N² + 16N + 64
を 16 で割ったときの余りは、 N² を 16 で割ったときの余りと一致（なぜなら、上の式の右辺の N² 以外の項 16N + 64 = 16(N + 4) は 16 でちょうど割り切れ、余りに関係しない）。結局、 B² を 16 で割ったときの余りと、 N² を 16 で割ったときの余りは、同じ。

〘ⅱ〙　2(y + m/4) − 1 = 2y + m/2 − 1 を A とすると、それは 2y − 1 より m/2 大きい。 2y − 1 を N と置くなら、 A = N + m/2 だ。その平方
　　A² = N² + Nm + m²/4
を m で割ったときの余りは、 N² を m で割ったときの余りと一致。なぜなら、上の式の右辺の N² 以外の項は m で割り切れるので、 m で割ったときの余りに影響しない。

実際 Nm は m で割り切れるし、 m = 2^t なので m²/4 = (2^t)²/4 = 2^2t−2 = 2^t⋅2^t−2 も m = 2^t で割り切れる（仮定により t ≥ 4 だから 2^t−2 ≥ 4）。

すなわち A² を m で割ったときの余りと、 N² を m で割ったときの余りは、同じ。∎

「周期 m/4 で、余りの数がループすること」が、確定した。一方、周期内の前半・後半の「鏡像」関係は、次のちょっと面白い性質と関連する。

【表2】 N = 8 を軸とする「鏡像関係」（左右対称）

	a	b	c	d	d′	c′	b′	a′
N2	1	9	25	49	81	121	169	225
N2 mod 32	1	9	25	17	17	25	9	1
N	1	3	5	7	9	11	13	15

mod 32 の例。 N² の値について、 d′ − d = 81 − 49 = 32 は 32 の倍数（1 倍）なので、一方の数（例えば 81）が「32 の倍数 + 一定の余り」のとき、他方の数（例えば 32）も「32 の倍数 + 同じ余り」でなければならない。 32 で割って r 余る数に 32 の倍数を加減しても、加減された倍数は 32 で割り切れるので余りには影響せず、結果の数を 32 で割った余りは依然 r だから。

同様に c′ − c = 121 − 25 = 96 も 32 の倍数。 b′ − b = 169 − 9 = 160 も 32 の倍数（5 倍）。 a′ − a = 225 − 1 = 224 も 32 の倍数（7 倍）。このように「鏡像」の位置にある 2 種類の N² は値の差が 32 の倍数なので、 32 で割った余りは、どちらも同じ。このちょっと不思議な（？）性質は、次のようにして生じる。例えば d′ − d の場合:
　　81 − 49 = 9² − 7² = (9 + 7)(9 − 7) = 16 × 2
あるいは c′ − c の場合:
　　121 − 25 = 11² − 5² = (11 + 5)(11 − 5) = 16 × 6
b′ − b の場合には:
　　169 − 9 = 12² − 3² = (13 + 3)(13 − 3) = 16 × 10
等々。

このように N = 8 を「対称軸」として、二つの平方数の差は、
　　(8 + ℓ)² − (8 − ℓ)² = 16 × 2ℓ
の形になり、この ℓ は奇数なので、結果の 16 × 2ℓ は 32 の奇数倍に等しい。

同様のことは、 32 で割る場合に限らない。例えば mod 64 では周期の長さが 16 なので、 N = 16 を「対称軸」として、対称の位置の二つの N² の値は:
　　(16 + ℓ)² − (16 − ℓ)² = 32 × 2ℓ = 64 の奇数倍
従って、どちらも 64 で割った余りは等しい。具体例として 17² − 15² = 289 − 225 = 64 も 19² − 13² = 361 − 169 = 192 = 32 × 6 も、 64 の奇数倍。

この観察から、容易に次の結論に至るだろう。

命題17（周期内の回文性）　1, 3, 5, ··· をそれぞれ平方して m = 2^t で割った余りを考える（t ≥ 4）。出現する余りを並べた数列は、周期 m/4 で同じパターンの繰り返しになるが（命題16）、一つの周期内においては、前半の m/8 個の余りと、後半の m/8 個の余りは、両端から二つずつ等しい。よって、余りが並ぶ順序を無視すると、周期 m/8 で同じ余りが（順序は違うかもしれないが）反復される。

〔例〕　m = 32 の場合、「1, 9, 25, 17; 17, 25, 9, 1」の八つの余りが循環する（周期 32/4 = 8）。しかし余りが並ぶ順序にこだわらないなら、四つごとに {1, 9, 17, 25} の 4 種類の余りが反復される（周期 32/8 = 4）。

さて、 0 以上 16 未満の 16 個の（負でない）整数の中には 8z + 1 の形の数（8 の倍数より 1 大きい）が 2 個ある（1 と 9）。 32 未満の 32 個の整数の中には 8z + 1 の形の数 が 4 個ある（1, 9, 17, 25）。一般に m = 2^t 未満の m 個の数の中にこの型の数が m/8 個あることは、明らかだろう。だって 0, 1, 2, ···, 2^t の m 個の数の中に 8z の形の数（0, 8, 16, ···）は、ちょうど 8 個に一つの割合で含まれているから、その総数は m/8 = 2^t−3 で、それらに 1 を足したものが 8z + 1 型の数なのだから、その形の数も 8z 型の数とちょうど同数（m/8 個）あるはず。

奇数の平方を m = 2^t で割ったときに生じる余りはどれも 8z + 1 型であり、そのような数は 0 以上 m 未満の範囲にはちょうど m/8 個ある。それらがどのように並ぶのか、全体的なパターン性も分かっている（命題16・命題17）。

しかし次の問いの答えは、直ちに明らかとはいえない。

問題　正の整数を m = 2^t で割ると、割り切れるか（余り 0）、もしくは 1 以上 m−1 以下の、何らかの余りが生じる（t ≥ 4）。余りの中には、上記のように 8z + 1 型の数が m/8 種類ある。それでは、奇数の平方 1, 9, 25, 49, ··· を順々に m で割ったとき、余りとして上記 m/8 種の 8z + 1 型の数が必ず全種類現れる、と断言できるか？

前記の数値例の検討では、 m = 16 のとき 8z + 1 型の余り（1, 9）は全種類（それも均等な割合で）生じたし、 m = 32 のときも 8z + 1 型の余り（1, 9, 17, 25）が全種類、均等に生じた。これらの観察から m = 64, 128, 256, 512, ··· などでも、たぶん同様だろうと予想される。直観的には「どの余りも役割は対称なので、均等に出現するはず」と思えるのだが、具体的にはどう説明すればいいのだろう…

この問題は、次のように考えると、比較的容易に解決する。

まず y = 1, 2 に対して N² = (2y − 1)² が mod 16 において不合同であること（具体的には ≡ 1, 9 であること）については、論はない（直接確認できる）。

さて y = 1, 2, 3, 4 に対して、 N² を 16 で割ったときの余りが「1, 9; 9, 1」と鏡像的になるメカニズムは、 y = 1, 4 に対しても、 y = 2, 3 に対しても、 N² の値の差が 16 の奇数倍になるからだった（前述）。

mod 32 の立場では、どんな数 X に対してであれ、そこに 16 の奇数倍が加算されれば、結果は X + 16 と合同であり（16 の奇数倍は 16 と合同なので）、 X + 16 は、もともとの X とは不合同。すなわち y = 1, 2 のときの N² ≡ 1, 9 は mod 16 で既に不合同なのだから、より詳細な分類である mod 32 では、もちろん不合同だし、そればかりか y = 3, 4 に対する N² も―― mod 16 の立場では y = 2, 1 の場合の N² とそれぞれ合同なのだが―― mod 32 の立場では、合同性が維持されない: mod 32 では 9 ≢ 9 + 16 ≡ 25 であり 1 ≢ 1 + 16 ≡ 17 である！

【表3】 不合同な類の個数が倍々に増えていく

y →	1	2	3	4	5	6	7	8
N = 2y − 1	1	3	5	7	9	11	13	15
N2	1	9	25	49	81	121	169	225
N2 mod 16	1	9	9	1	1	9	9	1
N2 mod 32	1	9	25	17	17	25	9	1
N2 mod 64	1	9	25	49	17	57	41	33

この議論は、再帰的に適用可能。今、 y = 1, 2, 3, 4 に対する 4 種類の N² が mod 32 でどれも不合同であることが確立したので、それら四つの N² はもとより mod 64 でも不合同だし、しかも y = 8, 7, 6, 5 に対する 4 種類の N² は、今述べた四つの N² にそれぞれ 32 の奇数倍を足したものなので、 mod 64 では、先行する四つの N² のどれとも不合同な「新しい」剰余類に属する。言い換えると、 mod 64 では、 N² として、互いに不合同な八つの値が出現する。

さらに、 9 ≤ y ≤ 16 の範囲において、 mod 64 では（64 の奇数倍の加算の結果として）今述べた八つの類の代表元が逆順に並ぶだけだが、 mod 128 では―― 64 の奇数倍が加算されれば、どの数も別の類の代表元に変わるので――、「新しい」八つの種類の数が追加される。

このようにして、一般に、 mod m では計 m/8 種類の（8z + 1 型の）剰余が N² として出現する。ところが mod 8 では 8z + 1 型の類は、ちょうど m/8 個しかないのだから、 8z + 1 型の各類の代表元は、どれも出現しなければならない。出現には前述の循環性（と鏡像性）があるので、「ある類の代表元が出現しやすい・出現しにくい」といった偏りは生じない（考えている区間が、周期の長さの整数倍に当たる限りにおいて）。

特に、 y が 1 から m まで〚m/2 まで〛動くとき、 (2y − 1)² の値は、 mod m における 8z + 1 の形の m/8 個の類を、ちょうど 8 回ずつ〚4 回ずつ〛代表する。

〔付記〕　(2y − 1)² が取り得る任意の一つの値を D とすると、 D は 8z + 1 型の奇数。今 x = 2y − 1 と置く。 y が 1 から m/2 まで動くとき、 x は 1 から m − 1 までの奇数値を取り、ちょうど 4 回 x² = (2y − 1)² ≡ D (mod m) を満たす。 D は奇数なので、偶数 x は x² ≡ D を満たさない。ゆえに 0 ≤ x ≤ m − 1 の範囲に x² ≡ D (mod m) を満たす x がちょうど 4 個存在し、言い換えると x² ≡ D (mod 2^t) の解はちょうど 4 種類ある（t ≥ 4。ただし、同じことは t = 3 についても真）。奇数 D と 3 以上の整数 t について、 x² ≡ D (mod 2^t) が解を持つための必要十分条件は D ≡ 1 (mod 8) であり、解があるなら必ず 4 種類の解がある。

次回、この件をもっと体系的に扱う。（下に続く）

---

2026-03-22　4 個の解を持つ2次方程式　mod 2ⁿ

問題1　1 から 128 までの数の中に、「2 乗して 128 で割ると 17 余るような数」は何個あるか？

128 個の平方数 1², 2², 3², ··· , 128² を計算し、それぞれ 128 で割ってみて、余りが 17 になるケースを（もしあれば）抜き出せば、全部で何個あるか数えることは、原理的には易しい。でもそのアプローチは、あまりに面倒くさい…

さて、2次方程式には、普通、解がちょうど二つある（例えば x² = 9 の解は x = ±3）。
　　x² ≡ 9 (mod 11)
のような方程式（等号を合同記号に置き換えた）でも、解があるとすれば二つある（x ≡ ±3 つまり x ≡ 3, 8）。この場合の「二つ」というのは、合同な（同じ種類の）解を「一つ」と数えて「不合同な解が 2 種類ある」という意味。第一の解は −8 ≡ 3 ≡ 14 ≡ 25 など「11 の倍数 + 3」のタイプ、第二の解は −3 ≡ 8 ≡ 19 ≡ 30 など「11 の倍数 + 8」のタイプ。「11 の倍数 + 3」という性質を持つ整数は無限個あるけど、「11 で割った余りで分類」という観点では、それら全部をまとめて同じ一つの類（クラス）と見なす。「11 の倍数 + 8」も同様。

一方、どんな奇数も平方すれば「8 の倍数 + 1」になるのだから、
　　x² ≡ 1 (mod 8)
には四つの解 x ≡ 1, 3, 5, 7 がある。前回見たように、
　　x² ≡ 1 (mod 16)
にも四つの解 x ≡ 1, 7, 9, 15 があるし、
　　x² ≡ 9 (mod 16)
にも四つの解 x ≡ 3, 5, 11, 13 がある。ここで
　　A ≡ B (mod m)
というのは「A と B の差は m の倍数」という意味。 B が 0 以上 m 未満のときは、「A を m で割ったら余りは B」と言ってもいい。例えば 5² を 16 で割った余り（つまり 25 を 16 で割った余り）は 9 なので、
　　5² ≡ 9 (mod 16)
となって、 x ≡ 5 は x² ≡ 9 (mod 16) の一つの解だよっ、と。

実は 8 の倍数より 1 大きい（任意の）数 D が与えられたとき、 8, 16, 32, 64, ·· · のどれかを m とすると x² ≡ D (mod m) は 4 個の解を持つ。2次方程式なのに解が 4 個もあるってのは、ちょっぴり変てこだけど、この事実を利用すれば、何一つ計算するまでもなく、問題1の答えは「4 個」！

問題1では「何個あるか？」と尋ねてるだけで、具体的にどの数が条件を満たすのかを尋ねていない。実はこのような合同式では、「解の有無（個数）を判定すること」と「実際に解を求めること」は別問題で、概して後者は前者より難しい（というか、計算量的にコストが大きい）。参考までに具体的な 4 種類の解（平方して 128 で割ると 17 余る数）を記すと:
　　x ≡ ±23, ±41 (mod 128)　言い換えれば
　　x ≡ 23, 41, 128 − 41, 128 − 23 ≡ 23, 41, 87, 105
後に問題3として、具体的な一つの解を求める方法を記す（そして命題23から、四つの解が得られる）。

実際 ±23 と ±41 の平方は 128 の倍数より 17 大きい:
　　(±23)² = 529 = 512 + 17 = 128 × 4 + 17
　　(±41)² = 1681 = 1664 + 17 = 128 × 13 + 17

一般に x ≡ n が x² ≡ D を満たすなら、もちろん x ≡ −n も同じ関係を満たす（n も −n も平方すれば結果は同じなので）。

D が 8 の倍数 + 1 で n が 3 以上なら、 x² ≡ D (mod 2ⁿ) は 4 個の解を持つ。前回、そのことを一応証明した――具体例の観察に基づく素朴で散漫な議論によって。もう少し体系的に、きっちり論証してみたい。

例えば x² ≡ 17 (mod 64) を満たす x が（一つ以上）存在するとすれば、そのような x は 0, 1, 2, ···, 63 の中にある。実は、これら 64 個の数を小さい順に [0, 15], [16, 31], [32, 47], [48, 63] の四つの区間に等分すると、必ず最初の区間の中に一つの解がある（小さい順で上位 4 分の 1 に属する「小さい解」）。のみならず、四つの区間のそれぞれに、一つずつ解がある。同様のことが、一般的に成り立つ。

これは基本的な事柄で、いろいろな教科書に証明が記されているが、そのアプローチはさまざま。以下では、本家本元・巨匠ガウスによる簡潔な証明を紹介する。

【1/4】　次の補助命題が大活躍する。

命題18（Gauß, D.A., §103, № 1^†）　二つの整数 a, b の和または差が 2ⁿ⁻¹ の倍数なら（n ≥ 3）:
　　a² ≡ b² (mod 2ⁿ)

† https://www.e-rara.ch/zut/content/zoom/1254768

〔例〕　a = 7, b = 5 のとき a + b = 12 は 2³⁻¹ = 4 の倍数。このとき 7² ≡ 5² (mod 2³)。実際 7² = 49 と 5² = 25 の差 24 は 2³ = 8 の倍数。

証明　a ± b = 2ⁿ⁻¹⋅h とする（右辺は 2ⁿ⁻¹ の倍数: 整数 h は倍率）。このとき ±b = 2ⁿ⁻¹⋅h − a なので、その両辺を平方すると:
　　(±b)² = (2ⁿ⁻¹⋅h − a)²
つまり:
　　b² = (2ⁿ⁻¹⋅h)² − 2⋅(2ⁿ⁻¹⋅h)⋅a + a²
　　 = 2²ⁿ⁻²⋅h² − 2ⁿ⋅ah + a² = 2ⁿ(2ⁿ⁻²⋅h² − ah) + a²
この等式を mod 2ⁿ で考えると、最右辺・第1項は 2ⁿ の倍数なので ≡ 0 であり、無いのと同じ。すなわち:
　　b² ≡ a² (mod 2ⁿ)　∎

【2/4】　実際に解があるかどうかはさておき、もし解があるのなら「小さい解」がある――ということを示そう。

命題19（「小さい解」の存在: D.A., §103, № 2）　任意の奇数 D について、もし
　　x² ≡ D (mod 2ⁿ)　　（✽）
を満たす解 x が一つ以上あるなら（n ≥ 3）、必ず 1 以上 2ⁿ⁻² 以下の範囲に（✽）の解がある（それ以外の範囲にも、解があるかもしれないが）。

〔例〕　n = 6 なら 2⁶ = 64, 2⁶⁻² = 16。もし x² ≡ 17 (mod 64) に解があるなら、 1 ≤ x ≤ 16 の範囲に（も）解がある。実際、 x = 9 は x² = 81 ≡ 17 (mod 64) を満たすので、 9 はその範囲の解。

証明　仮に（✽）が解 a を持つとする。すなわち:
　　a² ≡ D (mod 2ⁿ)

一般性を失うことなく 1 ≤ a ≤ 2ⁿ と仮定できる（mod 2ⁿ には 2ⁿ 種類の数しかないから）。

もし 1 ≤ a ≤ 2ⁿ⁻¹ なら b = a と置き、もし 2ⁿ⁻¹ < a ≤ 2ⁿ なら b = a − 2ⁿ⁻¹ と置く。すると b は 1 以上 2ⁿ⁻¹ 以下。しかも a と b の差は 0 または 2ⁿ⁻¹ だから、命題18 により a² ≡ b² (mod 2ⁿ) であり、 x = b は（✽）の解。

よって、もし b が 2ⁿ⁻² 以下なら、命題19は正しい。残る問題はそれ以外のケース。「b は 2ⁿ⁻² より大きく 2ⁿ⁻¹ 以下」と仮定し、その場合でも 1 以上 2ⁿ⁻² 以下 の範囲に（✽）の解があることを示そう。

c = 2ⁿ⁻¹ − b と置くと、 b についての仮定から、 c は 0 以上 2ⁿ⁻² 未満。のみならず c + b = 2ⁿ⁻¹ は 2ⁿ⁻¹ の倍数なので c² ≡ b² (mod 2ⁿ) が成り立ち（命題18）、従って x = c も（✽）の解（x = 0 は（✽）の解ではないので c ≠ 0 であり、 c は 1 以上）。∎

偶数の平方は偶数で、奇数 D と合同になり得ないので、偶数 x = 2ⁿ⁻² は（✽）の解ではない。よって、解の範囲指定が「2ⁿ⁻² 未満」でも「2ⁿ⁻² 以下」でも、実質的な違いはない。「0 以上」か「1 以上」かについても同様。

命題19は「（✽）にもし解があるとしたら、少なくとも一つの解は小さい」と言っているだけで、「全部の解が小さい」とは言っていないし、そもそも「必ず解がある」とも言っていない。

【3/4】　区間ごとの解の分布は「均等」で、「特定の平方数ばかりがやたらと出現する」といったことはない。平方数になり得る全部の奇数は、公平に、ちょうど一度ずつ出現する。

命題20（区間内の奇数の平方は不合同: D.A., §103, № 3）　1 以上 2ⁿ⁻² 未満の各奇数をそれぞれ平方したものは、どの二つも mod 2ⁿ において不合同（n ≥ 3）。

〔例〕　1 以上 2⁵⁻² = 8 未満の奇数 1, 3, 5, 7 をそれぞれ平方すると 1, 9, 25, 49。この四つの平方数の中には、 2⁵ = 32 で割った余りが等しいものはない。つまり mod 2⁵ においてどれも不合同。

証明　仮に命題20に反する二つの奇数が存在したとして、そのうち大きい方を r、小さい方を s としよう。すなわち、 1 以上 2ⁿ⁻² 未満の相異なる二つの奇数 r, s が
　　r² ≡ s² (mod 2ⁿ)　つまり　r² − s² ≡ 0 (mod 2ⁿ)
を満たしたとしよう（r > s）。そのとき r² − s² = (r + s)(r − s) は 2ⁿ の倍数。

さて r + s と r − s は、奇数の和・差なので偶数だが、そのうち一方は、明らかに 4 = 2² の倍数ではない。

実際、もし奇数 r, s がどちらも 4k + 1 型か、または、どちらも 4k − 1 型なら、 r + s は 4k ± 2 型の偶数だし（それは 4 の倍数ではない）、もし奇数 r, s の一方が 4k + 1 型で他方が 4k − 1 型なら、 r − s は 4k ± 2 型の偶数（それは 4 の倍数ではない）。

言い換えると、 r + s と r − s の一方は、素因子 2 を 1 個しか持たない。よって、他方が素因子 2 を n − 1 個以上持たない限り、 (r + s)(r − s) は 2ⁿ の倍数になり得ない。すなわち、上記のような r, s が存在するためには、 r + s と r − s のどちらかが 2^n-1 の倍数になることが必要。しかし、この必要条件は決して満たされない。なぜなら、命題の仮定により r, s は 2ⁿ⁻² 未満の正の数だから r + s は 2ⁿ⁻¹ 未満の正の数で、従って 2ⁿ⁻¹ の倍数になり得ないし、同じ理由から r − s も 2ⁿ⁻¹ の倍数になり得ない。∎

【4/4】　以上のことから、次の結論に至る。

命題21（mod 2ⁿ の平方剰余: D.A., §103, № 4）　奇数 D について x² ≡ D (mod 2ⁿ) が解を持つためには、 D が 8k + 1 の形であることが必要、そしてそれで十分（n ≥ 3）。この必要十分条件が満たされるとき、 x² ≡ D はちょうど 4 種類の解を持つ。

〔注〕　「何らかの整数」の平方と合同な数を「平方剰余」と呼ぶ。例えば 7² = 49 ≡ 17 (mod 32) なので、 mod 32 において 17 は 7² と合同であり、従って 17 は mod 32 の平方剰余。

証明　任意の奇数 x = 4k ± 1 について、その平方 x² = 16k² ± 8k + 1 は、 8 の倍数より 1 大きい。ゆえに D が 8k + 1 型であることの必要性は明白。さて、 1 から 2ⁿ までの 2ⁿ 個の整数の中に、この必要条件を満たすもの（つまり 8k + 1 型の数）は、ちょうど 2ⁿ/8 = 2ⁿ⁻³ 個ある（8 個に一つの割合なので）。

これら 2ⁿ⁻³ 種類の奇数は、どれも mod 2ⁿ において平方剰余となる可能性を秘めている（少なくとも、一つの必要条件を満たしている）。けれど「平方剰余になるために必要な、全条件を満たしているか？」「実際に平方剰余になるか？」は、直ちに明らかではない。

他方において、 1 から 2ⁿ⁻² までの 2ⁿ⁻² 個の整数の中に、奇数は 2ⁿ⁻³ 個ある。これら 2ⁿ⁻³ 個の各奇数を平方したものは、 mod 2ⁿ においてどれも不合同だから（命題20）、 1 から 2ⁿ までの整数の中に、「何らかの奇数」の平方と合同な数（それ自身も奇数）は、ちょうど 2ⁿ⁻³ 種類ある。

つまり mod 2ⁿ においては、 2ⁿ⁻³ 種類の奇数が平方剰余。ところが、最初に述べたように、 mod 2ⁿ において平方剰余となる可能性を秘めた奇数（つまり 8k + 1 型の数）は全部で 2ⁿ⁻³ 種類しかないので、結局、 8k + 1 型の任意の数 D は全種類、平方剰余となる。

言い換えると、 8k + 1 型の D が一つ与えられたとき、 x² ≡ D (mod 2ⁿ) は必ず解を持つ。解の中には、 0 以上 2ⁿ⁻² 未満のものが、一つだけ存在する（命題19により「存在」が保証される。命題20によりその範囲の奇数の平方はどれも不合同だから、特定の D と合同な x² は、あるとしても 1 個だけ）。今、この範囲にある「小さい解」を x = a とすると、 b = 2ⁿ⁻¹ − a も（別の種類の）解。なぜなら a + b は 2ⁿ⁻¹ の倍数（命題18参照）。結局、任意の一つの小さい解 a に対応して、 4 種類の解 x ≡ ±a, ±b が存在する。

4 種類の解の存在は確定したが、「5 種類以上の解は存在し得ない」と言い切れるか？

1 から 2ⁿ までの整数の中には、奇数は 2ⁿ⁻¹ 個しかない。 mod 2ⁿ において、それらの奇数はどの二つも不合同。しかるに、同じ範囲の 8k + 1 型の奇数（計 2ⁿ⁻³ 個）の一つ一つに対して「x² ≡ その奇数」という関係の奇数 x が 4 種類ずつ存在するのだから、（2ⁿ⁻³ 種類ある 8k + 1 型の数 D のそれぞれに対して）四つ一組の解が存在し、通算すれば「何らかの解となる奇数」の総数は 2ⁿ⁻³ × 4 = 2ⁿ⁻¹ 個。

これで「全種類の奇数は、過不足なく使用済み」。特定の奇数 x に対して x² は特定の値なので、同じ x の値が同時に x² ≡ D と x² ≡ D′ (≢ D) を満たすことはない。

つまり 1 から 2ⁿ までの範囲の 2ⁿ⁻¹ 個の奇数たちは、どれも 1 回ずつ、 2ⁿ⁻³ 種類のどれかの D に対して、 x² ≡ D の x の立場となり、一つ一つの D の値に対して、 x² ≡ D は、ちょうど 4 個ずつ解を持つ。∎

Gauß の議論は明晰（めいせき）でエレガント。抽象的・非構成的な存在証明だ。次回、構成的な別証明を記す。（下へ続く）

付録A　命題21の応用例

m = 2^t, t ≥ 4 とする。 y が 1 から m/2 まで動くとき、 2y − 1 は、「mod m の代表の一組」のうちの奇数（ちょうど m/2 個）の値を 1 回ずつ取る。このとき (2y − 1)² の m/2 個の値は、「mod m の代表の一組」のうちの 8z + 1 型の数（ちょうど m/8 個）の値を 4 回ずつ取る。ゆえに:
　　∑{y=1 to m/2} exp [2πiq(2y − 1)²/m] = 4 ∑{z=1 to m/8} exp [2πiq(8z + 1)/m]

ガウス和についての Nagell の議論では、 n が 4 の倍数のケースにおいて、この論法が使われる。上の等式自体は t = 3 (m = 8) でも成立するが、式の値が 0 になるためには t ≥ 4 であることを要する。

---

2026-03-24　49 を 32 で割ると 17 余ります。それでは···

問題2　7 の自乗（つまり 49）を 2⁵ = 32 で割ると 17 余る。では、何の自乗を 2⁶ = 64 で割ると 17 余るか。「x² を 64 で割ると 17 余る」という性質を持つ整数 x を一つでいいから見つけたい。

解　a² を m = 2ⁿ で割った余りが奇数 D だと分かっているときに、 2m で割ると D 余るような x² を見つける方法は、次の通り。

《x = a 自身が条件を満たせば、それが一つの答え。さもなければ a + m/2 が一つの答え。》

この問題では m = 32, a = 7 だが、 7² = 49 を 2m = 64 で割っても、余りは 17 ではない。よって 7 + 32/2 = 23 が一つの答え。∎

〔検算〕　23 の自乗（つまり 529）を 64 で割ると、確かに 17 余る（23² = 529 = 512 + 17 = 64 × 8 + 17）。

《　》内の主張を証明することは難しくない。一見あまり役立たない事柄のようだが、この考え方を使うと、 16, 32, 64, 128 などを法として、「任意の奇数」のモジュラー平方根を（もし存在するなら）求めることができる。

【1/4】　奇数の平方を 8 で割ると、必ず 1 余る。なぜなら奇数は 4k ± 1 の形の数（つまり 4 の倍数 ± 1）で、その平方
　　(4k ± 1)² = 16k² ± 8k + 1 = 8 × (2k² ± k) + 1
は 8 の倍数より 1 大きい。さて、 8 で割って 1 余る数は、 16 で割ると 1 余るか、または 9 余る。というのも、「8 で割って 1 余る数」は 8h + 1 の形で（h は何らかの整数）、もし h が = 偶数 2k なら
　　8h + 1 = 8(2k) + 1 = 16k + 1
だし、もし h が = 奇数 2k + 1 なら
　　8h + 1 = 8(2k + 1) + 1 = 16k + 9
だ。よって 16 の倍数より 1 大きいか、または 9 大きい。

そうすると、奇数 N の平方を 8 で割った余りと 16 で割った余りは、「どちらも 1」になるか、さもなければ「前者は 1 で後者は 9」になる。

【表4】 奇数の平方を 8 で割った余りと 16 で割った余り

N	1	3	5	7	9	11	13	15
N2	1	9	25	49	81	121	169	225
mod 8	1	1	1	1	1	1	1	1
mod 16	1	9	9	1	1	9	9	1

注目すべき事実として、「N² を 8 で割った余り」と「16 で割った余り」が一致しない場合でも、 N の値を 4 増やせば（あるいは 4 減らせば）、両者が一致するようになる――例えば N = 3 の場合、二つの余りは一致しないが、 N = 3 + 4 なら、どちらも余り 1 になる。

第2の例。ある数を 16 で割って 1 余るとき、その数を 32 で割れば、再び 1 余るか、または 17 余る。実際、 16h + 1 型の数は h が偶数 2k なら 32k + 1 の形を持ち、 h が奇数 2k + 1 なら 32k + 17 の形を持つ。同様に、ある数を 16 で割って 9 余るとき、その数を 32 で割れば、再び 9 余るか、または 25 余る。 16h + 9 型の数は h が偶数 2k か奇数 2k + 1 かに応じて 32k + 9 または 32k + 25 の形になるから。

【表5】 奇数の平方を 16 で割った余りと 32 で割った余り

N	1	3	5	7	9	11	13	15
N2	1	9	25	49	81	121	169	225
mod 16	1	9	9	1	1	9	9	1
mod 32	1	9	25	17	17	25	9	1

よって「奇数 N の平方を 16 で割った余り」と「32 で割った余り」は、「どちらも 1」または「どちらも 9」となって一致することもあるし、「前者が 1 で後者が 17」または「前者が 9 で後者が 25」となって一致しないこともある。しかし一致しない場合でも、 N の値を 8 増やせば（あるいは 8 減らせば）一致するようになる――例えば N = 5 のとき前者は 9、後者は 25 で一致しないが、 N = 5 + 8 = 13 とすれば、前者は 9 のまま後者も 9 になって、両者は一致する。

N² を 16 で割った余りが D のとき、もし N² を 32 で割った余りも D ならそれでいいとして、そうならない場合、 N² の代わりに (N + 8)² を考えれば、 32 で割った余りを D に一致させられる――少なくとも表5の数値例では、そうなっている。

もう一つだけ具体例。「奇数 N の平方を 32 で割った余り」と「64 で割った余り」は、一致することも多い（表6）。一致しない場合でも、N の値を 16 増やせば（または 16 減らせば）、両者は一致するようになる。

【表6】 奇数の平方を 32 で割った余りと 64 で割った余り

N	1	3	5	7	9	11	13	15
N2	1	9	25	49	81	121	169	225
mod 32	1	9	25	17	17	25	9	1
mod 64	1	9	25	49	17	57	41	33
N	17	19	21	23	25	27	29	31
N2	289	361	441	529	625	729	841	961
mod 32	1	9	25	17	17	25	9	1
mod 64	33	41	57	17	49	25	9	1

例えば、上段の N = 7 の場合、 32 で割った余り 17 は、 64 で割った余り（49）と一致しない。しかし N = 7 + 16 = 23 なら（対応する下段のカラム）、 32 で割った余りは 17 のままで、しかも 64 で割った余りも 17 になる。

上段の N = 11 のときも、 32 で割った余り 25 は、 64 で割った余り（57）と一致しない。しかし N = 11 + 16 = 27 なら（対応する下段のカラム）、 32 で割った余りは 25 のままで、しかも 64 で割った余りも 25 になる。

N = 13, 15 のケースも同様で、そのままでは N² mod 32 と N² mod 64 の最小剰余（32 ないし 64 で割った余りのこと）が一致しないが、 N に 16 を足して対応する下段のカラムに移れば、 mod 32 での最小剰余を変更せずに、 mod 64 での最小剰余がそれと同じになるようにできる。

【2/4】　以上の観察から、次の命題が成り立つのでは、と思われる（そしてこの命題が正しいことの証明は、難しくない）。

命題22　m = 2ⁿ を 8, 16, 32 などの「2 のべき」とする（n ≥ 3）。与えられた奇数 D について、もし
　　a² ≡ D (mod m)
という関係を満たす整数 a が存在するなら、
　　x² ≡ D (mod 2m)
を満たす整数 x も存在する。具体的には x = a がこの条件を満たすか、さもなければ x = a + m/2 がこの条件を満たす。

〔注〕　それ以外にも条件を満たす x は存在するが（後述）、ここではとりあえず「条件を満たす x が、少なくとも一つある」ことを示す。

証明　a² ≡ D (mod m) の意味は、 a² が m の倍数より D 大きいこと――つまり
　　《ア》　a² = h⋅m + D　　（h は何らかの整数）
が成り立つ、ということ。この a は、明らかに奇数。

なぜなら仮定により m は偶数、 D は奇数なので、《ア》の右辺 = 偶数 + 奇数 = 奇数。もしも a が偶数だったら a² は偶数になってしまい、《ア》の等式は成り立ち得ない。

h が偶数 2k であるか奇数 2k + 1 であるかに応じて、《ア》は
　　a² = 2k⋅m + D = k⋅2m + D　あるいは
　　a² = (2k + 1)⋅m + D = k⋅2m + (D + m)
になる。つまり a² は 2m の倍数より D 大きいか、または 2m の倍数より D + m 大きい。従って、
　　《イ》　a² ≡ D (mod 2m)
　　《ウ》　a² ≡ D + m (mod 2m)
のどちらかが成り立つ。もし《イ》が成り立つなら、もちろん x² ≡ D (mod 2m) は解 x = a を持ち、命題22は正しい。《イ》ではなく《ウ》が成り立つと仮定して、その場合でも x² ≡ D (mod 2m) が解を持つことを示そう。

既述のように、数値例の観察によると、「a² ≡ D が mod m では成り立つけど mod 2m だと駄目（成り立たない）という場合、 a を a + m/2 に置き換えれば、 mod m でも mod 2m でも a² ≡ D が成り立つ」ように思われる（命題22も、そう主張している）。これを検証するため、実際に x = a + m/2 と置いてみると:
　　x² = (a + m/2)² = a² + am + m²/4
右辺の a² に《ウ》を代入して:
　　《エ》　x² = D + m + am + m²/4 = D + m(1 + a + m/4)
ここで右端の ( ) 内の和は、偶数。

なぜなら a は奇数なので（前述）、 1 + a は偶数だし、仮定により m は 8 以上の「2 のべき」（つまり m = 2ⁿ, n ≥ 3）なので、 m/4 = 2ⁿ⁻² も偶数。

そこで ( ) 内の和 1 + a + m/4 を = 2ℓ と置くと（ℓ は何らかの整数）、《エ》はこうなる:
　　x² = D + m(2ℓ) = ℓ⋅2m + D
すなわち x² は、 2m の倍数より D 大きい。言い換えると、
　　x² ≡ D (mod 2m)
が成り立つ。《イ》が成り立たない場合の x = a + m/2 について、命題22の主張が証明された。∎

命題22は、理論的にも実践的にもかなりの優れ物。その威力を示す例として、次の問題を考えてみる。

問題3　「平方して 128 で割ると 17 余る」ような整数を一つ見つけたい。言い換えると、
　　x² ≡ 17 (mod 128)
を満たす x を一つ見つけたい。

ブルートフォース（全数検索による試行錯誤）で「条件を満たす x」を見つけることは可能だろうが、計算量的によろしくない。「銃を乱射すれば、そのうちラッキーヒットで的に当たるだろう」というのは「うまい方法が浮かばない場合」の窮余の策、ないしは手抜き。できることなら、繊細に、精密に、ターゲットを狙い撃ちしたい。次のように、命題22を活用できる。

解　1² = 1 ≡ 17 (mod 8) は明白（1 と 17 は 8 で割った余りが同じ）。つまり a² ≡ 17 (mod 8) を満たす a は、分かっている（a ≡ 1）。さて、同じ a は、
　　x² ≡ 17 (mod 16)
を満たすであろうか。しかり。明らかに 1² = 1 ≡ 17 (mod 16) だ（1 と 17 は 16 で割った余りが同じ）。では同じ a は、さらに
　　x² ≡ 17 (mod 32)
を満たすであろうか。否、 1 と 17 は 32 で割った余りが異なる。だからといって、行き止まりではない。「a² ≡ 17 が mod 16 では成り立つが mod 32 では駄目、という状況では、 a を a + 16/2 で置き換えればOK」という命題22の教えに従って、 a の値を = 1 + 16/2 = 9 に更新すると:
　　a² = 9² = 81 = 2 × 32 + 17 ≡ 17 (mod 32)
思惑通りに ≡ 17 が復活！

では、この新しい a = 9 は、 a² ≡ 17 (mod 64) も満たしてくれるか。しかり、
　　9² = 81 = 64 + 17 ≡ 17 (mod 64)
が成り立つ。それでは a² ≡ 17 (mod 128) もいけるか？　否、 81 ÷ 64 と 81 ÷ 128 は余りが異なる。でも「a² ≡ 17 が mod 64 では成り立つが mod 128 では駄目、という状況では、 a を a + 64/2 で置き換えればOK」ということから、 a = 9 + 64/2 = 41 が求める一つの解。∎

〔検算〕　41² = 1681 = 1664 + 17 = 128 × 13 + 17 を 128 で割ると 17 余る。

実は 41 は、問題3の最小の（正の）解ではない。より小さい x = 23 も、条件を満たす。実際、 23² = 529 = 512 + 17 = 128 × 4 + 17。しかし解が一つ見つかりさえすれば、芋づる式に全種類の解を得ることができるので（後述）、最小解でなくても構わない。

【3/4】　命題22は、理論面でも活躍する！

問題4　D を奇数、 n を 3 以上の整数とする。
　　x² ≡ D (mod 2ⁿ)　　（✽）
が解を持つための必要十分条件は D ≡ 1 (mod 8) であることを証明したい。

Gauß による4ステップの存在証明は、エレガントで非構成的（命題18 ～ 命題21）。一方、命題22を使うと、実直で構成的な証明が成り立つ（具体的過ぎて「幼稚」とさえ思える）。このアイデアは Dirichlet–Dedekind, §36 に基づく:
https://gdz.sub.uni-goettingen.de/id/PPN30976923X?tify=%7B%22pages%22%3A%5B100%5D%2C%22view%22%3A%22%22%7D

解　偶数の平方は奇数ではないし、 mod が偶数なら、偶数が奇数と合同になることもないので、（✽）が解を持つためには、少なくとも D が奇数であることが必要。しかし奇数の平方は 8k + 1 の形にしかならないので「D が奇数」というだけでは不十分で、 D が 8k + 1 型であること、言い換えると条件 D ≡ 1 (mod 8) が成り立つことも必要。この条件が満たされるなら、 x² ≡ D ≡ 1 (mod 8) には、もちろん解がある――例えば x ≡ 1 は一つの（自明な）解。その解を a としよう。

ところが、命題22によると x² ≡ D (mod 8) に解 x ≡ a があれば、 x² ≡ D (mod 16) にも解がある（x ≡ a と x ≡ a + 8/2 のどちらかが一つの解）。その解をあらためて a としよう。

再び命題22によって、 x² ≡ D (mod 16) に解 x ≡ a があれば、 x² ≡ D (mod 32) にも解がある（x ≡ a と x ≡ a + 16/2 のどちらかが一つの解）。その解をあらためて a としよう。

もう一度、命題22を使うと x² ≡ D (mod 32) に解 x ≡ a があれば、 x² ≡ D (mod 64) にも解がある（x ≡ a と x ≡ a + 32/2 のどちらかが一つの解）。その解をあらためて a としよう。

　︙

この議論はいくらでも続けることができるので、 D が 8k + 1 型である限りにおいて、 8, 16, 32, 64, 128, ··· のどれを mod としても、必ず x² ≡ D には解があるし、具体的な一つの解 a を構成できる。∎

この「解を構成する方法」は、「奇素数を法とするモジュラー平方根」の Tonelli のアルゴリズムとやや似ているが、はるかにシンプルで、特に「補助的な平方非剰余」が必要ない。法が「2 のべき」、という特殊な条件が、有利に働いている。普通の数の世界において x² = D の解は D の平方根と呼ばれる。ここでは「普通の整数」そのものを考えるのではなく、一定の基準（m の倍数よりいくつ大きいか）で整数たちをいくつかの類（クラス）に分けて考え、「平方すると、類 D と合同になるような類 x」を問題にしている。分類の基準となる m は modulus と呼ばれるので、 x² ≡ D (mod m) を満たす x を「モジュラー平方根」（a modular square root）と呼ぶことができる。

【4/4】　実際には解がちょうど 4 種類あるのに（命題21）、上記の手順では一つの解しか得られない。残りの三つの解は、いかにして得られるか？

命題23　D を 8k + 1 型の奇数、 n を 3 以上の整数として、 m = 2ⁿ と置く。
　　x² ≡ D (mod m)
は四つの解を持つ。一つの解が x ≡ a なら x ≡ ±a, ±(a + m/2) の四つが解。

証明　b = a + m/2 と置くと明らかに a ≢ b (mod m)。このとき a と b の差は m/2 = 2ⁿ⁻¹ なので、命題18 から a² ≡ b² (mod m) が成り立つ。ゆえに b も x² ≡ D の一つの解（仮定により a² ≡ D だから）。 −a, −b も、もちろん解。 mod m では y ≡ −y が成り立ち得るが、それには y ≡ m/2 であることが（従って y が偶数であることが）必要。われわれの a, b は奇数なので ±a, ±b の四つは、どの二つも不合同。∎

a が解なら −a も解なのは当然として、 b = a + m/2 も解だというのは、天下り的な主張に思えるかもしれない。でも「a² ≡ D が mod m では成り立つけど mod 2m では駄目、という場合には、 a を a + m/2 に置き換えれば両方の mod でその式が成り立つようになる」ってことは、数値的な観察を経て、命題22として検証済み。mod m に関して「a が一つの解なら a + m/2 も解であること」は、命題22の系に過ぎない。

実用上、次のように整理すると、便利かもしれない。

命題23の補足　一つの解 x = a が与えられたとする（問題の性質上、a は必ず奇数）。必要ならそれを m で割った余りで置き換えることにより、この a は 0 以上 m 未満、と仮定できる。もし a が m/2 より大きければ a − m/2 をあらためて a と置く。ここでもし a が m/4 未満なら a は（正の）最小解で b = m/2 − a が「2番目に小さい解」。一方、もし a が m/4 より大きければ a は「2番目に小さい解」で m/2 − a が最小解。

〔例〕　問題3において、 x² ≡ 17 (mod 128) の一つの解 x ≡ 41 を得た。 41 は 128/2 = 64 より小さいが、 128/4 = 32 より大きいので「2番目に小さい解」。最小解は 64 − 41 = 23。よって四つの解は x ≡ ±23, ±41（あるいは、同じことだが x ≡ 23, 41, 87, 105。ここで 87 = 128 − 41, 105 = 128 − 23）。

命題23同様、「命題23の補足」も命題18を根拠とする。 mod m に関して a² ≡ D と仮定すると、 a′ = a − m/2 の平方は ≡ a² であり、従って ≡ D。 b = a + m/2 の平方、ないし b = m/2 − a の平方もまたしかり。

剰余類としての a (mod m) と、その類の代表元としての整数 a を混同することは、厳密に言えば間違いだし、場合によってはバグの原因になる。でも、両者をあまりうるさく区別せず、類 a と整数 a を同じ記号 a で表して、同じような感覚で扱うと、むしろ便利なことも多い。例えば、剰余類の足し算・引き算・掛け算と、整数の足し算・引き算・掛け算は、ほとんど同じ（割り算は微妙に違うけど）。整数演算で 1 + 2 = 3 とか 4 × 5 = 20 が成り立つように、 mod m でも 1 + 2 ≡ 3 とか 4 × 5 ≡ 20 が成り立つ。

とはいえ、剰余類そのものは「整数」ではないし、狭い意味での「余りの整数」とも限らない。

例えば 31 を 8 で割れば 7 余る。それを
　　31 ≡ 7 (mod 8)
と表現するのは、もちろん正しい。けど、それだけじゃなく、例えば、
　　31 ≡ 15 (mod 8)
も正しいし、
　　31 ≡ −1 (mod 8)
も正しい。これら三つの合同式は、どれも「両辺は、 8 で割った余りに関して同類」（具体的には、両辺とも 8k + 7 型）って意味。早い話が「左辺と右辺の差は 8 の倍数だよっ」と解釈できる。

---

2026-04-01　sin の積と（拡張された）ガウスの補題

次の sin の積は「おばあちゃんの公式」の変種だが、見掛け以上に深い問題と関係している。
　　2 sin (4π/3) = −√3
　　2 sin (4π/5) × 2 sin (8π/5) = −√5
　　2 sin (4π/7) × 2 sin (8π/7) × 2 sin (12π/7) = +√7
　　2 sin (4π/9) × 2 sin (8π/9) × 2 sin (12π/9) × 2 sin (16π/9) = +√9
　　　︙

一般に m が 3 以上の奇数のとき、 2 sin (4π/m), 2 sin (8π/m), 2 sin (12π/m), ··· の形の因子を上記のように (m − 1)/2 個掛け算すると、積は ±√m に等しい。符号は m が 8 の倍数 ± 1 ならプラス、さもなければマイナス。――この符号の振る舞いは、簡単に直接証明されるし、もし m が素数ならガウスの補題からも容易に派生する。 m が素数でない場合（m = 9, 15, 21 など）にも符号が同じ挙動を示すのだから、「ガウスの補題は、ヤコビ記号へも拡張可能」ということが暗示される。

ガウス和との関連で「おばあちゃんの公式」の一般化のような遊びをしているうち、自然とそのことに気付いた。主観的には「発見」だが、まさか「ガウスの補題の Jacobi バージョン」をこれまで誰も考えなかった、ということはないだろう。文献調査の結果、この拡張は Morgan Jenkins^† によって1867年に発見されていたと判明。 Jenkins も「ガウス和」「第四証明」の文脈で、この観察に至ったらしい。 Lemmermeyer^‡ も Gauss’s Lemma […] was generalized to composite values of m by Jenkins と記している。

とはいえ、一般的にはほとんど知られていないようだ。例えば、テキサス大学の Stephen McAdam^¶ は先行研究に気付かず、同じことを独立に再発見して We also prove that the Jacobi symbol always satisfies Gauss’s Lemma, a fact which we have never seen mentioned. と述べている。

眺めてきれいな sin の積と、ガウスの補題の関係。初等的な古典数論の範囲にも、意外と「秘密の細道」があるものだ！

† Morgan Jenkins (1867). “Proof of an Arithmetical Theorem leading, by means of Gauss’s Fourth Demonstration of Legendre’s Law of Reciprocity, to the extension of that Law”, Proceedings of the London Mathematical Society, Volume s1-2, Issue 1 (1866), pp. 29–31

‡ Franz Lemmermeyer (2000). Reciprocity laws from Euler to Eisenstein, p. 23
cf. Oswald Baumgart (2015). The Quadratic Reciprocity Law (Edited and translated by Franz Lemmermeyer), p. 142
cf. Henry John Stephen Smith. Report of the Theory of Number, Art. 19 (footnote)
https://gdz.sub.uni-goettingen.de/id/PPN588764140?tify=%7B%22pages%22%3A%5B159%5D%2C%22view%22%3A%22%22%7D
cf. Heng Huat Chan & Song Heng Chan (2023). “An Amazing Identity of Gauss and Jenkins’ Lemma”, Bulletin of the Australian Mathematical Society, Vol. 108, No. 1, pp. 86–98
https://mrc.sdu.edu.cn/ziliao/87.pdf [Provisional, 2022]

¶ Stephen McAdam. Quadratic reciprocity and the Jacobi symbol
https://www.ma.utexas.edu/users/mcadam/monographs/QuadRec.pdf

出発点は次の事実。 m が 3 以上の奇数なら次が成り立つ:
　　∏{k=1 to m−1} (2 sin (kπ/m)) = m
単純できれいな式なのに、証明（指数関数バージョン・三角関数バージョン）があまり簡単ではないのが遺憾だが、この式を承認するなら、以降の議論は比較的易しい。

上の積で因子として含まれる m − 1 個（偶数個）の sin たちは、第1・第2象限の角に対応するからいずれも正で、両端から二つずつ値が等しい（なぜなら sin x = sin (π − x) なので）。すなわち、
　　ƒ(m) = 2 sin (kπ/m)
と置くと:
　　ƒ(1) = ƒ(m − 1)
　　ƒ(3) = ƒ(m − 3)
　　ƒ(5) = ƒ(m − 5)
　　　︙
上記 (m − 1)/2 個の等式のそれぞれにおいて、左辺には ƒ(奇数) が、右辺には ƒ(偶数) がある。左辺同士・右辺同士を全部掛け合わせると:
　　ƒ(1) ƒ(3) ƒ(5)⋅⋅⋅ƒ(m − 2) = ƒ(2) ƒ(4) ƒ(6)⋅⋅⋅ƒ(m − 1)
この等式の「左辺全体」と「右辺全体」の積は m だから、左辺も右辺も √m に等しい。特に:
　　ƒ(2) ƒ(4) ƒ(6)⋅⋅⋅ƒ(m − 1) = ∏{k=1 to (m−1)/2} (2 sin (2kπ/m)) = √m

要するに、
　　《サ》　k = 1, 2, 3, ··· , (m − 1)/2
に対応する因子 2 sin (k⋅2π/m) の積は、 √m に等しい。

そして野ウサギしか通らない細道へ…

問題5　それでは、
　　《シ》　k = 2, 4, 6, ··· , m − 1
に対応する同様の積は、いかなる値を持つか？

一般論として、 sin の引数（ひきすう）（つまり入力。 y = sin x の x のこと）に 2π の倍数の違いがあっても、 sin の値は変わらないので、例えば y = 2 sin (3⋅2π/m) の分子にある「3」を (m + 3) や (m − 3) に置き換えても y の値は変わらない。よって問題5では、
　　k = 2, 4, 6, ··· , m − 5, m − 3, m − 1
の代わりに、
　　k = 2, 4, 6, ··· , −5, −3, −1
を使っても差し支えない。言い換えると（絶対値の小さい順に並び替えて）、
　　k = −1, 2, −3, 4, −5, 6, ···
を使ってもいいわけである。つまり、《サ》の k たちのうち、（偶数をそのままにして）奇数の符号を全部逆にすれば、《シ》の k たちを使ったのと同じことになる。ところが sin (−x) = −sin x なので、 k の符号を反転させれば
　　因子　2 sin (k⋅2π/m)
の値も −1 倍される。値が −1 倍される因子が偶数個あるなら、トータルでは積に影響しないが、値が −1 倍される因子が奇数個あるなら、トータルでは積が −1 倍される。結局、
　　《サ》の中に奇数が「偶数個」あるか「奇数個」あるかに応じて、問題5の答えは ±√m
となる（偶数個ならプラス）。

〔例〕　m = 9 なら (m − 1)/2 = 4 なので、《サ》の数は 1, 2, 3, 4。その中に奇数は 2 個あるので m = 9 の場合の答えは +√9 = 3。

かくして問題5の答えは、次の「算数」によって決まる。

問題6　m が 3 以上の奇数のとき、
　　1　から　(m − 1)/2　までの整数
の中に含まれる奇数の個数を N とする。どのような m に対して N は偶数になるか、あるいは奇数になるか？

素朴な解法　1, 2, 3, 4, ···, (m − 1)/2 という列では、奇数と偶数が交互に並んでいる。もし末尾の (m − 1)/2 が偶数なら（言い換えれば、数列が偶数個の整数から成るとしたら）、そこに含まれる奇数と偶数の個数は明らかに半々で、 (m − 1)/4 個ずつ。ゆえに N = (m − 1)/4。この場合、 N が偶数（それを 2a とする）になるとしたら、
　　(m − 1)/4 = 2a
が成り立つ。両辺を 4 倍して:
　　m − 1 = 8a　つまり　m = 8a + 1
すなわち m が 8 の倍数より 1 大きいなら N は偶数。

一方、もし (m − 1)/2 が奇数なら、数列 1, 2, 3, 4, ···, (m − 1)/2 は奇数に始まり奇数で終わるのだから、奇数と偶数の個数は、半々ではない（奇数の方が 1 個多い）。そこに含まれる奇数の個数 N は
　　(m − 1)/2 ÷ 2 = (m − 1)/4　　［割り切れない］
の端数を切り上げたもの（+ 0.5）、つまり:
　　N = (m − 1)/4 + 1/2 = (m + 1)/4
この場合、 N が偶数（2a とする）だとしたら:
　　(m + 1)/4 = 2a
両辺を 4 倍して:
　　m + 1 = 8a　つまり　m = 8a − 1
すなわち m が 8 の倍数より 1 小さいなら N は偶数。

まとめると、もし m が 8 の倍数 ± 1 なら N は偶数。そうでなければ（つまり m が 8 の倍数 ± 3 なら）、 N は奇数。∎

よって、問題5の答えは:
　　∏{k=1 to (m−1)/2} (2 sin (4kπ/m)) = ±√m
符号は m が 8 の倍数 ± 1 ならプラス、 8 の倍数 ± 3 ならマイナス（冒頭の具体例参照）。

この積の符号決定は、ガウスの補題（下記）を経由する第二補充法則の証明と酷似している。

命題24（ガウスの補題）　p を 3 以上の素数、 D を p の倍数以外の（正または負の）整数とする。もし (p − 1)/2 個の整数
　　《ス》　1⋅D, 2⋅D, 3⋅D, ··· , (p − 1)/2⋅D
をそれぞれ p で割ったとき、余りが p/2 を超えるものの個数が N なら:
　　(D/p) = (−1)^N
最後の式の左辺は Legendre 記号で、簡略に (D/p) と記されることもある。

〔例〕　p = 11 なら (p − 1)/2 = 5。例えば D = 3 なら、《ス》の数列は:
　　3, 6, 9, 12, 15
このうち 11 で割った余りが 11/2 を超えるのは 6, 9 の二つなので N = 2。ゆえに (3/11) = (−1)² = +1 であり、 3 は mod 11 の平方剰余。つまり x² ≡ 3 (mod 11) は解を持つ（実際 x = 5 の平方を 11 で割ると 3 余る）。一方、例えば D = 2 なら、《ス》の数列は:
　　2, 4, 6, 8, 10
このうち 11 で割った余りが 11/2 を超えるのは 6, 8, 10 の三つなので N = 3。ゆえに (2/11) = (−1)³ = −1 であり、 2 は mod 11 の平方非剰余。つまり x² ≡ 2 (mod 11) は解を持たない。実際 ±1, ±2, ±3, ±4, ±5 を平方すると 1, 4, 9, 16, 25、それぞれ 11 で割った余りは 1, 4, 9, 5, 3 で、決して ≡ 2 にならない。

証明　《ス》の各数を p で割ったときの最小絶対剰余^†は、
　　±1, ±2, ±3, ··· , ±(p − 1)/2 (mod p)
のいずれか。《ス》の各数は mod p において不合同なので、《ス》の各数の最小絶対剰余は、どれも絶対値が異なり^‡、仮定によって、そのうち N 個が負。よって、《ス》の数の最小絶対剰余たちの積は、
　　(−1)^N⋅1⋅2⋅3··· (p − 1)/2 = (−1)^N⋅((p − 1)/2)!
に等しい。ゆえに《ス》の各数の積（下記の左辺）は、
　　(1⋅D)(2⋅D)(3⋅D)···((p − 1)/2⋅D) ≡ (−1)^N⋅((p − 1)/2)! (mod p)
を満たす。両辺を ((p − 1)/2)! で割ると:
　　D^(p−1)/2 ≡ (−1)^N (mod p)
この左辺は Euler の基準により (D/p) に等しく、右辺は 1 または −1 に等しい（p ≠ 2 なので 1 ≢ −1）。∎

†　（p の倍数以外の）ある整数 A を p で割ったとき、もし余り r が p/2 より小なら r をそのまま剰余として使い、もし r が p/2 より大なら r の代わりに（それと合同な）負の剰余 r − p を使うことにすると、 A と合同な「絶対値 (p − 1)/2 以下の、正または負の剰余」が得られる（最小絶対剰余と呼ばれる）。

‡　《ス》の各数は mod p において不合同なので、《ス》の中の（相異なる）二つの数が、同じ最小絶対剰余を持つことはない。のみならず、「絶対値が等しく、符号だけが違う剰余」を持つこともない。実際、もしも x⋅D, y⋅D の剰余がそれぞれ ℓ, −ℓ (mod p) だったとしたら、 0 ≡ ℓ + (−ℓ) ≡ xD + yD ≡ (x + y)D が成り立ち x + y ≡ 0 でなければならない、つまり「x + y は p の倍数」でなければならない。しかし、それは不可能。なぜなら x, y は (p − 1)/2 以下の正の数なので、 x + y は p − 1 以下の正の数。 p の倍数になりようがない。

命題25（Legendre 記号の第二補充法則）　p が 3 以上の素数なら:
　　(2/p) = (−1)^(p2−1)/8

〔注〕　この右辺の表記は伝統的なものだが、一見、真意が分かりにくい。その実質的意味は、「もし p が 8 の倍数 ± 1 なら左辺は +1 に等しく、もし p が 8 の倍数 ± 3 なら左辺は −1 に等しい」。実際、前者の場合 p = 8k ± 1 と置くと p² − 1 = (64k² ± 2⋅8k + 1) − 1 は 16 の倍数（つまり 8 の偶数倍）なので、 (−1) の肩の指数 (p² − 1)/8 は偶数。後者の場合 p = 8k ± 3 と置くと p² − 1 = (64k² ± 2⋅8⋅3k + 9) − 1 は 16 の倍数より 8 大きいので（つまり 8 の奇数倍なので）、指数 (p² − 1)/8 は奇数。

証明　ガウスの補題によると、問題は、
　　《セ》　2, 4, 6, ···, p − 5, p − 3, p − 1
の各数を p で割ったとき、余りが p/2 を超えるものの個数 N が偶数か奇数か、に帰する。それぞれの割り算の商は 0 なので、単に《セ》の中に p/2 より大きい数がいくつあるか調べればいい。その一つの方法は、《セ》を右から逆順に見て、
　　p − x の x が p/2 より小さいものがいくつあるか
を数えること。言い換えると、奇数 1, 3, 5, ··· の中に p/2 より小さいものがいくつあるか？

(p + 1)/2 は明らかに大き過ぎて条件を満たさない。 p/2 自身は奇数でない（整数ですらない）ので、やはり条件を満たさない。結局、
　　1　から　(p − 1)/2　の範囲に奇数がいくつあるか？
という問題になる。これは sin の積に関連する問題6と全く同じ質問だ！

問題6の「3 以上の奇数 m」がここでは「3 以上の素数 p」に置き換わるけど、そのことは結果に影響しない。 m が素数か否かという区別は、問題6の解法と無関係だから。

問題6は解決済みだが、ここで興味深い別解（少しトリッキーだが）を紹介したい。問題の核心は「N の具体的な値」ではなく「N が偶数か奇数か」なので、 mod 2 で考えよう。その際、奇数が一つあるごとにカウントを 1 増やしてもいいのだが、「奇数か偶数か」の情報さえ保たれればいいのだから、例えば奇数が一つあるごとにカウントを 3（あるいは任意の奇数）増やしても、結論は変わらない（mod 2 では任意の奇数は ≡ 1 なので）。他方において、もしそうしたければ、勝手にカウントを 2（あるいは任意の偶数）増やしても、トータルの和が「奇数か偶数か」に影響しない（mod 2 では任意の偶数は ≡ 0 なので）。

以上を踏まえると、 1 から (p − 1)/2 までの範囲にある奇数の個数 N は、 mod 2 において、
　　《ソ》　N ≡ 1 + 3 + 5 + ··· + (p − 1)/2　　←　(p − 1)/2 が奇数の場合
もしくは
　　《ゾ》　N ≡ 1 + 3 + 5 + ··· + (p − 3)/2　　←　(p − 1)/2 が偶数で (p − 3) が奇数の場合
を満たす。しかも、この足し算に 2, 4, 6 などの偶数を勝手に追加しても、結論に影響しないのだから:
　　《タ》　N ≡ 1 + 2 + 3 + 4 + 5 + 6 + ··· + (p − 3)/2 + (p − 1)/2 (mod 2)
が成り立つ。この最後の右辺は、
　　(1 + (p − 1)/2) × (p − 1)/4 = (p + 1)/2 × (p − 1)/4 = (p² − 1)/8
に等しい。ゆえに
　　N ≡ (p² − 1)/8 (mod 2)
となる。∎

この計算法は、高木の『初等整数論』§13による（偶数を任意に足していいのだから、本来《ソ・ゾ》の区別は必要なく、最初から《タ》を考えれば十分。高木自身もそうしているのだが、ロジックの明確化のため、上記ではあえて場合分けした）。伝統的な指数表現 (p² − 1)/8 が自然に出てくるところが良い。トリックも面白い。半面、（問題6などでやっているように）実直に場合分けした方が、平明で分かりやすいと思われる。参考までに Hardy & Wright 版の別証明を付録として追加しておく。

sin の積についての問題5の符号決定と、ガウスの補題による D = 2 のケースの（Legendre 記号の）符号決定が、本質的にほとんど同じ処理であることが感じられる。ただし sin の積では奇数 m が合成数でも構わないが、ガウスの補題（の上記の証明法）では奇数 p は素数でなければならない。アルゴリズム的に後者（ガウスの補題）が前者（sin の積）に包含されることから、（証明法を工夫すれば）ガウスの補題を拡張して任意の奇数 p に対して有効にできるということが、示唆される。

そのこと自体は、意外ではない。第一に、 Legendre 記号と Jacobi 記号はほとんど同じ性質を持ち、特に Jacobi 記号版の第二補充法則が成り立つことは基本的。第二に、「ガウス和と Legendre 記号の関係」が、一定の条件で「ガウス和と Jacobi 記号の関係」に拡張されることも、よく知られている。

「ガウスの補題の N のカウント」を「sin の積の負の因子のカウント」で置き換えることができる、という観点からは、問題6の素朴な解法は、事実上、拡張された（Jacobi 記号バージョンの）第二補充法則の証明になっている。今、余計なトリックを排して、「負の因子」の個数を数えると…

問題7　3 以上の奇数 m が与えられたとき、 k = 1, 2, 3, ···, (m − 1)/2 に対する因子
　　2 sin (2k⋅2π/m) = 2 sin (4kπ/m)
の中で、値が負のものの個数を N とする。どのような m に対して N は偶数になるか、あるいは奇数になるか？

〔注〕　上記の因子は ℓ = 4, 8, 12, ···, 2m − 2 に対する 2 sin (ℓπ/m) と同じ意味。既述のように、これらの因子の積は ±√m に等しく、符号がどうなるかも既知だが、以下ではある種の別解を検討する。

解　4k は最大でも 2m − 2 なので、 sin (4kπ/m) の引数は 2π を超えない―― k が大きくなって 4kπ/m の 4k が m を超えると sin の値は負になるが（第3・第4象限の角度）、一周して第1象限（sin の値は正）に戻ることはない。よって、指定範囲の k の中に 4k > m を満たすものがいくつあるか調べるだけでいい。この不等式は
　　k > m/4
と同値なので、求めるものは:
　　N = (m − 1)/2 − ⌊m/4⌋
（命題9の説明参照。）もし奇数 m が 4a + 1 型なら、
　　N = [(4a + 1) − 1]/2 − a = 2a − a = a
なので、 N の偶奇は a の偶奇と一致。つまり a が偶数 2b で m = 4(2b) + 1 = 8b + 1 の形なら N は偶数、 a が奇数 2b + 1 で m = 4(2b + 1) + 1 = 8b + 5 の形なら N は奇数。一方、もし m が 4a + 3 型なら、
　　N = [(4a + 3) − 1]/2 − a = (2a + 1) − a = a + 1
なので、 N の偶奇は a の偶奇と逆。つまり a が偶数 2b で m = 4(2b) + 3 = 8b + 3 の形なら N は奇数、 a が奇数 2b + 1 で m = 4(2b + 1) + 3 = 8b + 7 の形なら N は偶数。

まとめると、 m が 8 の倍数 + [1 or 7] なら N は偶数。 m が 8 の倍数 + [3 or 5] なら N は奇数。前者なら問題7の積は正、後者なら問題7の積は負。∎

この別解は、問題6と本質的に同じだけれど、「端数切り捨て」（floor 関数）を使った引き算によって、「負の因子の個数」を機械的に（特別な工夫なく）決定できる。

応用例として、ガウスの補題で D = 3 の場合（「第三補充法則」）について、 sin の積の問題として考えてみる。

問題8　3 より大きく 3 で割り切れない奇数 m が与えられたとき、 k = 1, 2, 3, ···, (m − 1)/2 に対する因子
　　2 sin (3k⋅2π/m) = 2 sin (6kπ/m)
の中で、値が負のものの個数を N とする。どのような m に対して N は偶数になるか、あるいは奇数になるか？

この問題の趣旨は、次のような積の ± の決定にある:
　　2 sin (6π/5) × 2 sin (12π/5) = −√5
　　2 sin (6π/7) × 2 sin (12π/7) × 2 sin (18π/7) = −√7
　　2 sin (6π/11) × 2 sin (12π/11) × 2 sin (18π/11) × 2 sin (24π/11) × 2 sin (30π/11) = +√11

キーポイントは、この ± が Jacobi 記号 (3/m) と一致すること。

m が 3 の倍数でも積の計算は可能だが、そのとき sin の引数は 2π の倍数なので、因子は全部 0 で 積は 0。

積が 0 になる除外例は、数値的には自明だが、 Jacobi 記号との関連性という点では、 m が 3 の倍数のときの (3/m) = 0 と一致する。

解　sin の引数 6kπ/m を θ とする。 6k の最大値は 3m − 3 なので、 k が増加するにつれ角度 θ は、第1～第4象限を経て再び第1～第2象限に入るが、第3象限を再訪することはない。つまり sin θ の値は、正→負→正と変化。そのうち「負」の sin の個数をカウントすればいい。

π < θ < 2π のとき sin θ は負。よって k が m/6 を超えた瞬間に sin θ は負になり、その後 m/3 を超えた瞬間に sin θ は正に戻る。従って、求めるものは:
　　N = ⌊m/3⌋ − ⌊m/6⌋
仮定により奇数 m は 3 の倍数ではないので、 6a + 1 の形か、または 6a + 5 の形を持つ。もし m が 6a + 1 型なら、
　　N = 2a − a = a
なので N の偶奇は a の偶奇と一致。 a = 2b が偶数なら、つまり m が 6(2b) + 1 = 12b + 1 の形なら、 N は偶数。 a = 2b + 1 が奇数なら、つまり m が 6(2b + 1) + 1 = 12b + 7 の形なら、 N は奇数。

一方、もし m が 6a + 5 型なら、
　　N = (2a + 1) − a = a + 1
なので N の偶奇は a の偶奇と逆。 a = 2b が偶数なら、つまり m が 6(2b) + 5 = 12b + 5 の形なら、 N は奇数。 a = 2b + 1 が奇数なら、つまり m が 6(2b + 1) + 5 = 12b + 11 の形なら、 N は偶数。

まとめると、 m が 12 の倍数 + [1 or 11] なら N は偶数、 m が 12 の倍数 + [5 or 7] なら N は奇数。この区別に応じて、問題8の積は正あるいは負。∎

例えば m = 11 のとき、ガウスの補題を使うなら: k = 1, 2, 3, 4, 5 に対して「3k を 11 で割った余り」が 11/2 を超える回数が N。上記と同様のロジックにより k が 11/6 を超えた瞬間（つまり k が 1 を超えると）余りは 11/2 を超えるが、 k が 11/3 を超えた瞬間（つまり k が 3 を超えると）余りは 11/2 未満に戻る。ゆえに N = 3 − 1 = 2。

問題8は D = 3 の場合のガウスの補題を包含しつつ、その拡張となっている。つまり、奇数の合成数 m = 25, 35, 49, 55 などに対しても Jacobi 記号の正しい値を返す（Jacobi 記号の値が 0 になるケースを含めるなら m が 3 の倍数でも構わない）。

まだほんの入り口だけど、探索の余地が多いにあることが感じられる。

付録B　第二補充法則の別表現・平明な別証明。

命題26（Hardy–Wright, §6.11, Theorem 93）　p が 3 以上の素数なら:
　　(2/p) = (−1)^{⌊(p+1)/4⌋}

p ≡ 1, 3, 5, 7 ≡ 1, 3, −3, −1 (mod 8) に応じて (2/p) が +1, −1, −1, +1 であること、それが伝統的に (−1)^(p2−1)/8 と表現されることは既知。よって p ≡ 1, 3, 5, 7 (mod 8) に対して (−1)^{⌊(p+1)/4⌋} = ±1 も同じ符号を持つことを確かめるだけで、論理的には十分。けれど、ガウスの補題にさかのぼって、妙なトリックのない実直な証明を行いたい。すなわち、
　　(2/p) = (−1)^N
の N が ⌊(p + 1)/4⌋ に等しいことを示そう。

証明　ガウスの補題によると、この場合の N は、数列 2, 4, 6, ··· , p − 1 に含まれる p/2 より大きい数の個数。この数列は (p − 1)/2 個の偶数から成るのだから、そのうち p/2 より小さい偶数の個数を ℓ とすると、
　　N = (p − 1)/2 − ℓ　　《チ》
が成り立つ。

さて 1 以上 p/2 未満の範囲の整数（すなわち 1 から ⌊p/2⌋ までの整数）に含まれる偶数の個数 ℓ は:
　　p が 4a + 1 型なら　⌊p/2⌋ = 2a　で　ℓ = a = (p − 1)/4　《ツ》
　　p が 4a + 3 型なら　⌊p/2⌋ = 2a + 1　で　ℓ = a = (p − 3)/4　《テ》
なぜなら、《ツ》の場合、上記範囲内には 2a 個の整数
　　1, 2, 3, ··· , ⌊p/2⌋ (= 2a)
があって、奇数に始まり偶数に終わるので、その中には、奇数と偶数が a 個ずつある。《テ》の場合、同様に定められる範囲内には 2a + 1 個の整数
　　1, 2, 3, ··· , ⌊p/2⌋ (= 2a + 1)
があって、奇数に始まり奇数に終わるので、その中には奇数が a + 1 個あるが偶数は a 個しかない。

《ツ》《テ》の ℓ の値をそれぞれ《チ》に代入して:
　　p が 4a + 1 型なら　N = (p − 1)/2 − (p − 1)/4 = (p − 1)/4
　　p が 4a + 3 型なら　N = (p − 1)/2 − (p − 3)/4 = (p + 1)/4
前者の場合、整数 N にあえて 1/2 を足し、端数（今足した 1/2）を切り捨てるなら、結果はもちろん N に戻る:
　　N = ⌊N + p/2⌋ = ⌊(p − 1)/4 + p/2⌋ = ⌊(p + 1)/4⌋
後者の場合、もともと N = (p + 1)/4 がちょうど整数なので、そこに端数切り捨ての記号を付けても、値は変化しない。結局、どちらの場合も、
　　N = ⌊(p + 1)/4⌋
と表現できる。∎

(−1) の指数となる上記 N の書き方は、伝統的な表現 (p² − 1)/8 とは異なるが、表す内容は同じ。この別表現を使うと、第二補充法則と「負の第二補充法則」を次のようにきれいに対比させることができる:
　　(2/p) = (−1)^{⌊(p+1)/4⌋}
　　(−2/p) = (−1)^⌊p/4⌋

---