📂整数論

ガウスの二次互逆法則の証明

定理 ¹

相異なる二つの奇素数$p , q$について次が成り立つ。

• (1): $$ \left( {{ q } \over { p }} \right) = \begin{cases} \left( {{ p } \over { q }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ p } \over { q }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• (2): $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

(1)と(2)は表現が異なるだけで同じことを言っている。

二次剰余について実に整然とまとめられており、その有用性はさておいても数学的な美しさが逸品である。ガウスは初めて証明した後にもこの法則を非常に大切にし、生涯にわたって8通りの異なる証明を残したという。

証明

戦略: 本稿では少し長く洗練されてはいないが、難しい概念を使わない証明を紹介する。ガウスの驚くべきアイデアが核心であり、本格的な証明に先立って簡単に見ておこう。

ガウスのアイデア: 素数$p = 2n + 1$と$1 \le x, x ' \le n$について$ax \equiv e_{x} x ' \pmod{p}$を満たすように$e_{x} = \pm 1$とおくと $$ a^{{p-1} \over {2} } = a^{n} \equiv e_{1} e_{2} \cdots e_{n} \pmod{p} $$

例として$\pmod{11}$で二次剰余である$a = 3$の場合を見ると、$11 = 2n + 1 = 2 \cdot 5 +1$であるから$n=5$である。直接$3^{5} 5!$を計算してみよう。 $$ \begin{align*} 3^{5} 5! \equiv& (3 \cdot 1)(3 \cdot 2)(3 \cdot 3)(3 \cdot 4)(3 \cdot 1) \\ =& 3 \cdot 6 \cdot 9 \cdot 12 \cdot 15 \\ \equiv& 3 \cdot (-5) \cdot (-2) \cdot 1 \cdot 4 \pmod{11} \\ \equiv& (1 \cdot 3)(-1 \cdot 5)(-1 \cdot 2)(1 \cdot 1)(1 \cdot 4) \\ \equiv& (1 \cdot 1)(-1 \cdot 2)(1 \cdot 3)(1 \cdot 4)(-1 \cdot 5) \\ \equiv& (-1)^{2} 5! \pmod{11} \end{align*} $$ 両辺を$5!$で割ると$3^{5} \equiv (-1)^2 \equiv 1 \pmod{11}$を得る。このアイデアが驚異的なのは、$a$を累乗して$p$で割るという骨折り作業を$(-1)$を数える問題に変えられるからである。

オイラーの判定法: 素数$p \ne 2$について、$\displaystyle a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p}$

つまり、累乗を必要とするオイラーの判定法をより手軽に使えるということである。上の例では、 $$ 3^{{11- 1 } \over {2}} = 3^5 \equiv 1 \pmod{11} $$ 累乗して$p$で割って余りを求めるという骨折り作業が、あまりにも単純な問題になった。

---

二つの素数$p,q$を次のようにおこう。 $$ p := 2n +1 \\ q := 2m+1 $$ $1 \le x,x’ \le n$について$q x \equiv e_{x} x ' \pmod{p}$であり、合同の定義に従ってある$y \in \mathbb{Z}$について $$ qx = e_{x} x ' + py $$ のようにおくことができる。我々は$(-1)$を数えることに関心があるので、$e_{x } = -1$の場合だけ気にすればよい。もし$e_{x } = -1$ならば$qx = -x’ + py$であり、$y$について表すと $$ y = {{1} \over {p}} (qx + x ' ) >0 $$ そして$\le x,x’ \le n$かつ$2n < p$であるから $$ y = {{1} \over {p}} (qx + x ' ) \le {{(q+1)n} \over {p}} < {{q+1} \over {2}} = m+1 $$ したがって$1 \le y \le m$である。一方、仮定で$1 \le x , x ' \le n$であったから$1 \le x ' = py - qx \le n$である。言い換えると、$e_{x} = -1$ということは $$ 1 \le x \le n \\ 1 \le y \le m \\ 1 \le py - qx \le n $$ を満たす$y$が存在するということである。ここで次のような集合 $$ N : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le py - qx \le n \right\} $$ を考えてみると $$ \left( {{q} \over {p}} \right) \equiv q^{{p-1} \over {2}} = (-1 )^{|N|} \pmod{p} $$ ガウスのアイデアは累乗を$(-1)$を数える問題に変えたが、我々はそれすら数えるつもりはなく、ひとまず$|N|$とおいて進むことにする。上と同じ方式で $$ M : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , 1 \le qx - py \le m \right\} $$ とおくと $$ \left( {{p} \over {q}} \right) \equiv p^{{q-1} \over {2}} = (-1 )^{|M|} \pmod{q} $$ ここで $$ |N| + |M| = | \left\{ (x,y) \ | \ 1 \le x \le n , 1 \le y \le m , -n \le qx - py \le m \right\} | $$ であるから $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ が成り立つ。ここで$N$と同じ元を共有しない集合 $$ S = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , n < py - qx \right\} $$ $M$と同じ元を共有しない集合 $$ T : = \left\{ (x,y) \ | \ 1 \le x \le , 1 \le y \le m , m < qx - py \right\} $$ をとろう。$f : S \to T $を $$ f(x,y) = (x ' , y ' ) := (n + 1 - x , m + 1 -y) $$ と定義すると $$ \begin{align*} qx’ - py ' &= q(n + 1 - x) - p (m + 1 - y) \\ =& pn + q - qx - pm - p + py \\ =& (pn - pm ) + (p-q) - (qx - py) \end{align*} $$ ここで $$ qn - pm = (2m+1)n - (2n+1)m = n - m \\ q-p = 2m + 1 - (2n+1) = 2(m-n) $$ であるから $$ qx’ - py ' = n - m + 2m - 2n - (qx -py) =m-n-(qx - py) $$ したがって$qx’ - py ' -m = -(qx - py + n) > 0$すなわち$qx’ - py ' > m$であり、$f$は一対一対応であるから$|S| = |T|$である。これまで定義した$N , M , S, T$は互いに同じ元を共有しないので $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ ここで再び $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{|N| + |M|} $$ を計算してみよう。$|S| = |T|$であるから $$ (-1)^{|S| + |T|} = 1 \\ (-1)^{ |N| + |M| } = (-1)^{ |N| + |M| + |S| + |T| } $$ ここで $$ |N| + |M| + |S| + |T| = | \left\{ (x,y) | 1 \le x \le n , 1 \le y \le m \right\}| = nm $$ であるから $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{nm} $$ $p = 2n + 1$かつ$q = 2m + 1$であるから $$ \left( {{ p } \over { q }} \right) \left( {{ q } \over { p }} \right) = (-1)^{ { {p-1} \over {2} }{ {q-1} \over {2} } } $$

■

一方、二次互逆法則はヤコビ記号を用いることで次のように奇数について一般化できる。

一般化

相異なる二つの奇数$a , b$について

• [1]’: $$ \left( {{ b } \over { a }} \right) = \begin{cases} \left( {{ a } \over { b }} \right) & p \equiv 1 \pmod{4} \lor q \equiv 1 \pmod{4} \\ - \left( {{ a } \over { b }} \right) & p \equiv 3 \pmod{4} \land q \equiv 3 \pmod{4} \end{cases} $$
• [2]’: $$ \left( {{ a } \over { b }} \right) \left( {{ b } \over { a }} \right) = (-1)^{ { {a-1} \over {2} }{ {b-1} \over {2} } } $$