2.5.2 平方剰余の相互法則

いよいよ初等整数論の華である、平方剰余の相互法則にはいります。まずは、証明なしに平方剰余の相互法則を見ていきましょう。

定理 2.5.6 (平方剰余の相互法則)
$p,q$を2つの奇素数とすると、

$${q\overwithdelims () p}{p\overwithdelims () q}= (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$$

が成り立つ。

平方剰余の相互法則を最初に完全な証明を与えたのはガウスです。ガウスは平方剰余の相互法則に対し生涯で7つの本質的に異なる証明を与えています。ガウスが最初に証明したのは、1796年4月8日（ガウス日誌）ですのでガウスがまだ19歳のときです。ガウスはこの法則を基本定理とよんでいます。

ここでは、平方剰余の相互法則の意味を考えてみます。平方剰余の相互法則は、どんなに考えても不思議な法則です。

${q\overwithdelims () p}$は$\mod{p}$において$q$が平方剰余か否かを問題にしており、 ${p\overwithdelims () q}$は$\mod{q}$において$p$が平方剰余か否かを問題にしています。これまで、一次方程式を考えてきましたが、$\mod{p}$の世界と$\mod{q}$の世界はなんらの関係もなく独立していました。しかし、2次方程式を考えると何らかの関係があることが分かります。そして、その関係を表しているのが平方剰余の相互法則です。定理2.5.6の式は両辺ともに$p,q$で対象であり単純で極めて美しい法則であるといえます。

このように極めて美しい形をしているだけではありません。平方剰余の相互法則と、第一補充法則、第二補充法則を用いることにより，あらゆる場合の平方剰余/非剰余を判定することができます。

平方剰余の相互法則の意味については、初等整数論（入門編）も参照してください。

具体的な事例でみてみましょう。

例 2.5.7

$${3 \overwithdelims () 17} = (-1)^{\frac{3-1}{2}\frac{17-1}{2}}{17\overwithdelims () 3}$$

$$= {2\overwithdelims () 3}$$

$$= (-1)^{\frac{3^2-1}{8}}$$

$$= -1$$

実際、$\mod{17}$の原始根の1つは6であり、例2.4.28より、 $6^{15}\equiv 3 \pmod{17}$であり、原始根の奇数乗となっているため、平方非剰余であることが分かります。

例 2.5.8

$${5 \overwithdelims () 17} = (-1)^{\frac{5-1}{2}\frac{17-1}{2}}{17\overwithdelims () 5}$$

$$= {2\overwithdelims () 5}$$

$$= (-1)^{\frac{5^2-1}{8}}$$

$$= -1$$

実際、例2.4.28より、 $6^{11}\equiv 5 \pmod{17}$であり、原始根の奇数乗となっているため、平方非剰余であることが分かります。