📂整数論

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

統括 ¹

異なる２つの奇数素数 $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$ で割り、余りを求めるという面倒な作業が、とても単純な問題になった。

一般化

異なる２つの奇数 $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} } }$$