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

が成り立つ。つまり
は
が奇数となるものの個数と一致する。
証明
aq を p で割った余りが
より大きい
が奇数が成り立つことを示せばよい。
実際

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

より
のとき
より
となり、
一方
のとき
より
となる。
相互法則の証明[編集]
まず、次の補題を証明する。
補題

証明
q は奇数だから

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

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

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

より、
に一致する。
ガウスの補題の変形において、和を
に分割し、後者に対して先程の補題を用いると

となる。

かつ
は奇数であるから、上記の和は

に一致する。ここから

が成り立つ。同様に、

が成り立つ。
ここで、

は

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

は

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

および

より、
は

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

が成り立つ。これにより

が証明された。