初等整数論/平方剰余の相互法則の証明

平方剰余の相互法則の証明は様々なものが知られているが、初等的な証明として、アイゼンシュタインによる、ガウスの補題の変形と、幾何的な考えを用いた証明が知られている。 まず、ガウスの補題の変形から始める。

ガウスの補題の変形

p, q が相異なる奇素数のとき

$\left({\frac {q}{p}}\right)=(-1)^{\sum _{a=0}^{\frac {p-1}{2}}\left\lfloor {\frac {2aq}{p}}\right\rfloor }$

が成り立つ。つまり $\left({\frac {q}{p}}\right)$ は $\left\lfloor {\frac {2aq}{p}}\right\rfloor (a=0,1,\ldots ,(p-1)/2)$ が奇数となるものの個数と一致する。

証明
aq を p で割った余りが ${\frac {p}{2}}$ より大きい $\iff \left\lfloor {\frac {2aq}{p}}\right\rfloor$ が奇数が成り立つことを示せばよい。 実際

$aq=bp+r,0\leq r\leq p-1$

となるように整数 b , r を定めると

$2aq=2bp+2r$

より $r<{\frac {p}{2}}$ のとき $0\leq 2r<p$ より $\left\lfloor {\frac {2aq}{p}}\right\rfloor =2b$ となり、 一方 $r>{\frac {p}{2}}$ のとき

$2aq=(2b+1)p+(2r-p),0<2r-p<p$ より

$\left\lfloor {\frac {2aq}{p}}\right\rfloor =2b+1$ となる。

相互法則の証明

まず、次の補題を証明する。

補題

$\left\lfloor {\frac {2aq}{p}}\right\rfloor \equiv \left\lfloor {\frac {(p-2a)q}{p}}\right\rfloor {\pmod {2}}.$

証明
q は奇数だから

$\left\lfloor {\frac {2aq}{p}}\right\rfloor \equiv q-1-\left\lfloor {\frac {2aq}{p}}\right\rfloor {\pmod {2}}$

が成り立つ。ところでこの左辺は

$x\leq {\frac {2aq}{p}}$

が成り立つ正の整数 x の個数であるのに対し、右辺は

${\frac {2aq}{p}}<x\leq q-1$

が成り立つ整数 x の個数である。これは

${\frac {2aq}{p}}<x\leq q-1\iff 1\leq x<q-{\frac {2aq}{p}}={\frac {(p-2a)q}{p}}$

より、$\left\lfloor {\frac {(p-2a)q}{p}}\right\rfloor$ に一致する。

ガウスの補題の変形において、和を$a<{\frac {p}{4}},a>{\frac {p}{4}}$ に分割し、後者に対して先程の補題を用いると

$\sum _{a=0}^{\frac {p-1}{2}}\left\lfloor {\frac {2aq}{p}}\right\rfloor =\sum _{0\leq a<{\frac {p}{4}}}\left\lfloor {\frac {2aq}{p}}\right\rfloor +\sum _{{\frac {p}{4}}<a\leq {\frac {p-1}{2}}}\left\lfloor {\frac {2aq}{p}}\right\rfloor =\sum _{0\leq a<{\frac {p}{4}}}\left\lfloor {\frac {2aq}{p}}\right\rfloor +\sum _{{\frac {p}{4}}<a\leq {\frac {p-1}{2}}}\left\lfloor {\frac {(p-2a)q}{p}}\right\rfloor$

となる。

${\frac {p}{4}}<a\leq {\frac {p-1}{2}}\iff 0\leq p-2a<{\frac {p}{2}}$

かつ $p-2a$ は奇数であるから、上記の和は

$\sum _{0\leq b\leq {\frac {p-1}{2}},2|b}\left\lfloor {\frac {bq}{p}}\right\rfloor +\sum _{0\leq b\leq {\frac {p-1}{2}},b:{\textrm {odd}}}\left\lfloor {\frac {bq}{p}}\right\rfloor =\sum _{0\leq b\leq {\frac {p-1}{2}}}\left\lfloor {\frac {bq}{p}}\right\rfloor$

に一致する。ここから

$\left({\frac {q}{p}}\right)=(-1)^{\sum _{b=0}^{\frac {p-1}{2}}\left\lfloor {\frac {bq}{p}}\right\rfloor }$

が成り立つ。同様に、

$\left({\frac {p}{q}}\right)=(-1)^{\sum _{b=0}^{\frac {q-1}{2}}\left\lfloor {\frac {bp}{q}}\right\rfloor }$

が成り立つ。

ここで、

$S(p,q)=\sum _{b=0}^{\frac {p-1}{2}}\left\lfloor {\frac {bq}{p}}\right\rfloor$

は

$0\leq x<{\frac {p}{2}},0\leq y\leq {\frac {xq}{p}}\cdots (\#)$

となる整数の組 (x , y ) の個数に一致する。 同様に

$S(q,p)=\sum _{b=0}^{\frac {q-1}{2}}\left\lfloor {\frac {bp}{q}}\right\rfloor$

は

$0\leq y<{\frac {q}{2}},0\leq x\leq {\frac {yp}{q}}$

となる整数の組 (x , y ) の個数に一致する。 ここで

$0\leq x\leq {\frac {yp}{q}}\iff x\geq 0,y\geq {\frac {xq}{p}}$

および

$y<{\frac {q}{2}},x\leq {\frac {yp}{q}}\Rightarrow x<{\frac {p}{2}}$

より、 $S(q,p)$ は

${\frac {xq}{p}}\leq y<{\frac {q}{2}},0\leq x<{\frac {p}{2}}\cdots (\flat )$

となる整数の組 (x , y ) の個数に一致する。ところで p, q は相異なる素数なので $x<p$ のとき ${\frac {xq}{p}}$ は整数ではありえない。よって $(\#)$ の範囲にある整数の組と $(\flat )$ の範囲にある整数の組を合わせると、重複することなく $0\leq x<{\frac {p}{2}},0\leq x<{\frac {q}{2}}$ の範囲にある整数の組全体と一致する。したがって

$S(p,q)+S(q,p)={\frac {p-1}{2}}\cdot {\frac {q-1}{2}}$

が成り立つ。これにより

$\left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{S(p,q)+S(q,p)}=(-1)^{\frac {(p-1)(q-1)}{4}}$

が証明された。