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

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

ガウスの補題の変形

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

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

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

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

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

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

$2aq=2bp+2r$

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

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

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

相互法則の証明

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

補題

$\lfloor \frac{2aq}{p}\rfloor \equiv \lfloor \frac{(p-2a)q}{p}\rfloor (\mathrm{mod}2).$

証明
q は奇数だから

$\lfloor \frac{2aq}{p}\rfloor \equiv q-1-\lfloor \frac{2aq}{p}\rfloor (\mathrm{mod}2)$

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

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

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

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

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

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

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

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

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

となる。

$\frac{p}{4}<a\le \frac{p-1}{2}⟺0\le p-2a<\frac{p}{2}$

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

$\sum _{0\le b\le \frac{p-1}{2},2|b}\lfloor \frac{bq}{p}\rfloor +\sum _{0\le b\le \frac{p-1}{2},b:\text{odd}}\lfloor \frac{bq}{p}\rfloor =\sum _{0\le b\le \frac{p-1}{2}}\lfloor \frac{bq}{p}\rfloor$

に一致する。ここから

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

が成り立つ。同様に、

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

が成り立つ。

ここで、

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

は

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

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

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

は

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

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

$0\le x\le \frac{yp}{q}⟺x\ge 0,y\ge \frac{xq}{p}$

および

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

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

$\frac{xq}{p}\le y<\frac{q}{2},0\le x<\frac{p}{2}\cdots (\mathrm{♭})$

となる整数の組 (x , y ) の個数に一致する。ところで p, q は相異なる素数なので $x<p$ のとき $\frac{xq}{p}$ は整数ではありえない。よって $(\mathrm{\#})$ の範囲にある整数の組と $(\mathrm{♭})$ の範囲にある整数の組を合わせると、重複することなく $0\le x<\frac{p}{2},0\le 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}}$

が証明された。