平方剰余

「ある $x$ の平方が $a$ になるか」という存在問題を、単一のべき乗のmod計算に置き換える。これによりルジャンドル記号が計算可能かつ乗法的になる。

$(\mathbb{Z}/p\mathbb{Z})^{*}$ は位数 $p-1$ の巡回群である(素数を法とする標準的な事実)ので、原始根 $g$ を一つ固定し $a \equiv g^k \pmod p$($0 \le k \le p-2$)と書く。$p$ を法とする平方剰余はちょうど $g$ の偶数乗である:$a=g^{2m}$ なら $x=g^m$ が $x^2\equiv a$ を満たし、逆にすべての平方 $x^2=(g^j)^2=g^{2j}$ は偶数乗である。したがって $a$ が平方剰余であることは $k$ が偶数であることと同値である。

次に $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$ を計算する。$k$ が偶数のとき $k=2m$ と書けば、フェルマーの小定理より $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ となり、剰余の場合と一致する。

$k$ が奇数のとき、$g^{k(p-1)/2}$ は $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$ の平方根なので $a^{(p-1)/2}\equiv \pm 1$ である。これが $1$ になることはない:もしそうなら $g$ の位数が $k(p-1)/2$ を割り切る必要があるが、$\operatorname{ord}(g)=p-1$ であり $k$ が奇数だと $(p-1)/2$ 自体が倍数でない限り $k(p-1)/2$ は $p-1$ の倍数にならず、$g$ が正確に位数 $p-1$ の原始根であることに矛盾する。よって $k$ が奇数のときちょうど $a^{(p-1)/2}\equiv -1\pmod p$、すなわち $a$ が非剰余のときちょうどこれが成り立つ。

両方の場合をまとめると:$a^{(p-1)/2}\equiv 1\pmod p$ であることは $a$ が平方剰余であることと同値であり、そうでなければ $\equiv -1$ となる。これはまさに $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$ の主張である。

$p$ が $q$ を法として平方数かどうかと、$q$ が $p$ を法として平方数かどうかは、$p,q$ を $4$ で割った余りだけに依存する符号を除いて「同じ」問いであることを述べている——難しく見える二変数の問題を一行の規則に変える。

踏み台としてガウスの補題を用いる:奇素数 $p$ と $\gcd(a,p)=1$ に対し、$a, 2a, \dots, \frac{p-1}{2}a$ の $p$ を法とする最小正剰余を見て、そのうち $p/2$ を超えるものの個数を $\mu$ とする。ガウスの補題は $\left(\dfrac{a}{p}\right)=(-1)^{\mu}$ を主張する。これは「大きい」剰余 $r$ を $p-r\le p/2$ と対にし、$\frac{p-1}{2}$ 個の数を二通りの方法で掛け合わせたときの符号を追うことで従う。

アイゼンシュタインの精密化は $\mu$ を格子点の個数として表す:$a=q$ が奇数のとき、$\lfloor kq/p\rfloor$($kq$ 未満の $p$ の倍数の個数)と $kq \bmod p$ が $p/2$ からどれだけ離れているかを比較することで $\mu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor \pmod 2$ が示される。同じ計数論法を対称的に適用すると $\left(\frac{q}{p}\right)=(-1)^{S(q,p)}$ と $\left(\frac{p}{q}\right)=(-1)^{S(p,q)}$ が得られる。ここで $S(q,p)=\sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor$、$S(p,q)=\sum_{k=1}^{(q-1)/2}\left\lfloor \frac{kp}{q}\right\rfloor$ である。

幾何学的には、$S(q,p)+S(p,q)$ は $1\le x\le \frac{p-1}{2}$、$1\le y\le \frac{q-1}{2}$ を満たす格子点 $(x,y)$ のうち、直線 $qx=py$ の厳密に下側にあるもの($S(q,p)$ 個)と厳密に上側にあるもの($p,q$ の対称的な役割により $S(p,q)$ 個)の合計を数える。$\gcd(p,q)=1$ かつ $x<p$ より直線上に格子点はちょうど存在しないため、この二つの個数を合わせると $\frac{p-1}{2}\cdot\frac{q-1}{2}$ 個の格子点をすべて尽くす。

したがって $S(q,p)+S(p,q) = \frac{p-1}{2}\cdot\frac{q-1}{2}$ であり、二つのルジャンドル記号の式を掛け合わせると $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{S(p,q)+S(q,p)}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ となり、これはまさに $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ である。