平方剰余の相互法則

\(p\) を素数とし、\(a\not\equiv 0\pmod p\) とする。このとき \(p\nmid a\) なので \(\gcd(a,p)=1\) です。Euclid の互除法から Bézout の等式が成り立ち、ある整数 \(u,v\) が存在して \[ au+pv=1 \] となります。両辺を \(p\) で見れば \[ au\equiv 1\pmod p \] です。したがって \(u\) は \(a\) の逆元です。非零元すべてに逆元があるので、\(\Z/p\Z\) は体です。

体を \(K\) とし、非零多項式 \(f(X)\in K[X]\) の次数を \(d\) とします。 \(\alpha\in K\) が根、つまり \(f(\alpha)=0\) なら、因数定理により \[ f(X)=(X-\alpha)g(X) \] と書けます。このとき \(\deg g=d-1\) です。 根が \(r\) 個あるとして、相異なる根 \(\alpha_1,\ldots,\alpha_r\) を一つずつ取り出すと、 \[ f(X)=(X-\alpha_1)(X-\alpha_2)\cdots(X-\alpha_r)h(X) \] となります。右辺の次数は少なくとも \(r\) なので、\(r\le d\) です。

\(1,2,\ldots,p-1\) を \(a\) 倍した数 \[ a,2a,3a,\ldots,(p-1)a \] を \(p\) を法として考えます。もし \(ia\equiv ja\pmod p\) なら \[ a(i-j)\equiv 0\pmod p. \] \(p\nmid a\) なので \(a\) は逆元を持ち、両辺に \(a^{-1}\) を掛けて \[ i-j\equiv 0\pmod p \] です。しかし \(1\le i,j\le p-1\) だから、これは \(i=j\) を意味します。 したがって \(a,2a,\ldots,(p-1)a\) の剰余は、\(1,2,\ldots,p-1\) の順序を並べ替えたものです。 よって積を取ると \[ a\cdot 2a\cdot 3a\cdots (p-1)a \equiv 1\cdot 2\cdot 3\cdots (p-1) \pmod p. \] 左辺は \(a^{p-1}(p-1)!\) なので、 \[ a^{p-1}(p-1)!\equiv (p-1)!\pmod p. \] \((p-1)!\) は \(p\) で割れないため逆元を持ち、両辺からキャンセルして \[ a^{p-1}\equiv 1\pmod p. \]

\(\F{p}^{\times}=\{1,2,\ldots,p-1\}\) を \(p\) を法とした非零剰余類の集合とします。 写像 \[ \varphi:\F{p}^{\times}\to \F{p}^{\times},\qquad x\mapsto x^2 \] を考えます。\(x^2=y^2\) なら \[ x^2-y^2=(x-y)(x+y)\equiv 0\pmod p. \] \(\F{p}\) は体なので積が \(0\) なら一方が \(0\) です。したがって \[ x-y\equiv 0\pmod p \quad\text{または}\quad x+y\equiv 0\pmod p, \] すなわち \[ x\equiv y\pmod p \quad\text{または}\quad x\equiv -y\pmod p. \] \(p\) は奇素数なので \(y\not\equiv -y\pmod p\) です。なぜなら \(y\equiv -y\) なら \(2y\equiv0\)、\(2\) は逆元を持つので \(y\equiv0\) となり、非零性に反するからです。 よって各非零平方剰余は、ちょうど二つの平方根 \(x\) と \(-x\) から生じます。 \(\F{p}^{\times}\) の元は \(p-1\) 個で、二つずつ同じ平方に写るので、像の大きさは \[ \frac{p-1}{2} \] です。これが非零平方剰余の個数です。

まず \(p\mid a\) の場合、\(a^{(p-1)/2}\equiv0\pmod p\) であり、定義より \(\Leg{a}{p}=0\) なので成立します。以下 \(p\nmid a\) とします。

\(m=(p-1)/2\) とおきます。\(a\) が平方剰余なら、ある \(b\not\equiv0\pmod p\) が存在して \[ a\equiv b^2\pmod p \] です。したがって Fermat の小定理より \[ a^m\equiv (b^2)^m=b^{2m}=b^{p-1}\equiv1\pmod p. \]

次に、非零平方剰余はちょうど \(m\) 個あり、それらはすべて多項式 \[ X^m-1 \] の根です。次数は \(m\) ですから、体 \(\F{p}\) 上の根は高々 \(m\) 個です。 よって \(X^m-1\) の根は、非零平方剰余だけです。 したがって \(a\) が平方非剰余なら \[ a^m\not\equiv 1\pmod p. \]

一方 Fermat の小定理から \[ a^{p-1}=a^{2m}\equiv1\pmod p \] です。つまり \(y=a^m\) とおくと \[ y^2\equiv1\pmod p, \] すなわち \[ (y-1)(y+1)\equiv0\pmod p. \] \(\F{p}\) は体なので \(y\equiv1\) または \(y\equiv-1\) です。 非剰余の場合は \(y\not\equiv1\) なので \[ a^m\equiv -1\pmod p. \] これで Euler 判定法が示されました。

\(p\mid a\) または \(p\mid b\) のときは、両辺とも \(0\) なので成立します。 以下 \(p\nmid a,b\) とします。Euler 判定法により \[ \Leg{ab}{p}\equiv (ab)^{\frac{p-1}{2} } =a^{\frac{p-1}{2}}b^{\frac{p-1}{2}} \equiv \Leg{a}{p}\Leg{b}{p} \pmod p. \] 両辺は \(1\) または \(-1\) です。奇素数 \(p\) について \(1\not\equiv -1\pmod p\) なので、 合同であることは整数として等しいことを意味します。したがって \[ \Leg{ab}{p}=\Leg{a}{p}\Leg{b}{p}. \]

\(m=(p-1)/2\) とおきます。各 \(r_k\) に対して、\(r_k\le m\) なら \(b_k=r_k\)、 \(r_k>m\) なら \(b_k=p-r_k\) と定めます。\(p\) は奇数なので \(p/2=m+1/2\) であり、 \(r_k>p/2\) は整数条件では \(r_k\ge m+1\) と同じです。 したがって常に \[ 1\le b_k\le m \] です。また符号 \(\varepsilon_k\) を \[ \varepsilon_k= \begin{cases} 1 & (r_k\le m),\\ -1 & (r_k>m) \end{cases} \] とおけば \[ ak\equiv r_k\equiv \varepsilon_k b_k\pmod p \] です。

次に、\(b_1,b_2,\ldots,b_m\) は \(1,2,\ldots,m\) の並べ替えであることを示します。 もし \(b_i=b_j\) なら、\(r_i\) と \(r_j\) は符号まで同じなので \[ ai\equiv aj\pmod p \quad\text{または}\quad ai\equiv -aj\pmod p \] が成り立ちます。前者なら \[ a(i-j)\equiv0\pmod p. \] \(p\nmid a\) なので \(i-j\equiv0\pmod p\) です。 しかし \(1\le i,j\le m

いま全ての合同式 \(ak\equiv\varepsilon_k b_k\pmod p\) を掛け合わせると \[ a^m(1\cdot2\cdots m) \equiv (\varepsilon_1\varepsilon_2\cdots\varepsilon_m)(b_1b_2\cdots b_m) \pmod p. \] \(b_1,\ldots,b_m\) は \(1,\ldots,m\) の並べ替えなので \[ b_1b_2\cdots b_m = 1\cdot2\cdots m=m!. \] また \(\varepsilon_k=-1\) となる個数は \(n\) なので \[ \varepsilon_1\varepsilon_2\cdots\varepsilon_m=(-1)^n. \] したがって \[ a^m m!\equiv (-1)^n m!\pmod p. \] \(m!\) は \(p\) で割れないため逆元を持ち、キャンセルして \[ a^m\equiv (-1)^n\pmod p. \] Euler 判定法により \(a^m\equiv\Leg{a}{p}\pmod p\) です。 両辺は \(\pm1\) なので、 \[ \Leg{a}{p}=(-1)^n. \]

\(m=(p-1)/2\) とおき、\(a=-1\) に Gauss の補題を適用します。 \(k=1,2,\ldots,m\) について \[ (-1)k\equiv p-k\pmod p. \] 最小正剰余は \(p-k\) です。ここで \[ p-k\ge p-m=p-\frac{p-1}{2}=\frac{p+1}{2}>\frac p2 \] なので、すべての \(k\) で上半分に入ります。 よって \(n=m\) です。Gauss の補題より \[ \Leg{-1}{p}=(-1)^m=(-1)^{\frac{p-1}{2}}. \]

\(m=(p-1)/2\) とおき、\(a=2\) に Gauss の補題を適用します。 \(k=1,2,\ldots,m\) について、\(2k\) は \[ 2,4,6,\ldots,2m=p-1 \] なので、すでに \(p\) を法とする最小正剰余です。 上半分に入る条件は \[ 2k>\frac p2. \] \(p=2m+1\) だから \(p/2=m+1/2\) であり、整数 \(2k\) についてこれは \[ 2k\ge m+1 \] と同値です。したがって上半分に入る \(k\) の個数は \[ n=\#\{k:1\le k\le m,\, k>m/2\}=m-\left\lfloor\frac m2\right\rfloor=\left\lceil\frac m2\right\rceil. \] ここで \(p\) を \(8\) で分類します。

よって \(\Leg{2}{p}=1\) は \(p\equiv1,7\pmod8\) のとき、 \(\Leg{2}{p}=-1\) は \(p\equiv3,5\pmod8\) のときです。 この符号は \[ (-1)^{\frac{p^2-1}{8}} \] と一致します。実際、\((p^2-1)/8\) の偶奇は \(p\pmod8\) だけで決まり、 \(p\equiv1,7\pmod8\) で偶数、\(p\equiv3,5\pmod8\) で奇数です。

Gauss の補題の記号を使います。各 \(k=1,\ldots,m\) について \[ ak=p t_k+r_k, \qquad t_k=\left\lfloor\frac{ak}{p}\right\rfloor, \qquad 1\le r_k\le p-1 \] と書きます。\(p\nmid a\) なので \(ak\not\equiv0\pmod p\) であり、したがって \(r_k\ne0\) です。

\(r_k\le m\) のとき \(b_k=r_k\)、\(r_k>m\) のとき \(b_k=p-r_k\) とします。 \(r_k>m\) となる個数を \(n\) とすると、Gauss の補題により \[ \Leg{a}{p}=(-1)^n. \] したがって示すべきことは \[ n\equiv \sum_{k=1}^{m}t_k\pmod2 \] です。

\(b_1,\ldots,b_m\) は \(1,\ldots,m\) の並べ替えなので \[ \sum_{k=1}^{m}b_k=\sum_{k=1}^{m}k. \] これを \(2\) を法として見ます。\(r_k>m\) のとき \(b_k=p-r_k\) であり、 \[ (p-r_k)-r_k=p-2r_k\equiv1\pmod2 \] です。\(r_k\le m\) のときは \(b_k-r_k=0\) です。したがって \[ \sum_{k=1}^{m}b_k\equiv \sum_{k=1}^{m}r_k+n\pmod2. \] また \(r_k=ak-pt_k\) なので、\(a,p\) がともに奇数であることから \[ r_k\equiv k-t_k\equiv k+t_k\pmod2. \] よって \[ \sum_{k=1}^{m}r_k \equiv \sum_{k=1}^{m}k+\sum_{k=1}^{m}t_k \pmod2. \] 以上を合わせると \[ \sum_{k=1}^{m}k =\sum_{k=1}^{m}b_k \equiv \sum_{k=1}^{m}k+\sum_{k=1}^{m}t_k+n \pmod2. \] 両辺から \(\sum k\) を消して \[ \sum_{k=1}^{m}t_k+n\equiv0\pmod2. \] したがって \[ n\equiv\sum_{k=1}^{m}t_k\pmod2 \] です。これを Gauss の補題に代入して \[ \Leg{a}{p}=(-1)^n=(-1)^{\sum_{k=1}^{m}\lfloor ak/p\rfloor}. \]

もし \((x,y)\in R\) が直線上にあれば \[ y=\frac qp x \] ですから \[ py=qx. \] \(p\) は素数で、\(p\ne q\) なので \(p\nmid q\) です。 \(py=qx\) から \(p\mid qx\)、したがって \(p\mid x\) です。 しかし \(1\le x\le m=(p-1)/2

固定した \(x\in\{1,\ldots,m\}\) について、直線の下側にある点は \[ 1\le y<\frac qp x \] を満たす整数 \(y\) です。直線は格子点を通らないので \(qx/p\) は整数ではありません。 よってその個数は \[ \left\lfloor\frac{qx}{p}\right\rfloor \] です。なお \(x\le(p-1)/2\) なので \[ \frac{qx}{p}\le\frac{q(p-1)}{2p}<\frac q2=\frac{q-1}{2}+\frac12=n+\frac12, \] したがって床は高々 \(n\) で、長方形の外側を数えていません。 したがって下側の点数は \[ S_{q,p}=\sum_{x=1}^{m}\left\lfloor\frac{qx}{p}\right\rfloor. \]

固定した \(y\in\{1,\ldots,n\}\) について、直線の上側にある点は \[ y>\frac qp x \] つまり \[ x<\frac pq y \] を満たす整数 \(x\) です。同様に \(py/q\) は整数ではないので、その個数は \[ \left\lfloor\frac{py}{q}\right\rfloor \] です。したがって上側の点数は \[ S_{p,q}=\sum_{y=1}^{n}\left\lfloor\frac{py}{q}\right\rfloor. \]

直線は格子点を通らないので、\(R\) の各点は下側または上側のどちらか一方に属します。 よって \[ S_{q,p}+S_{p,q}=mn. \]

Eisenstein の補題を \((a,p)=(q,p)\) に適用すると、\(q\) は奇数なので \[ \Leg{q}{p}=(-1)^{S_{q,p}} =(-1)^{\sum_{x=1}^{(p-1)/2}\left\lfloor\frac{qx}{p}\right\rfloor}. \] 同じく \((a,p)=(p,q)\) に適用すると \[ \Leg{p}{q}=(-1)^{S_{p,q}} =(-1)^{\sum_{y=1}^{(q-1)/2}\left\lfloor\frac{py}{q}\right\rfloor}. \] したがって \[ \Leg{q}{p}\Leg{p}{q} =(-1)^{S_{q,p}}(-1)^{S_{p,q}} =(-1)^{S_{q,p}+S_{p,q}}. \] 格子点の分割から \[ S_{q,p}+S_{p,q}=mn=\frac{p-1}{2}\frac{q-1}{2} \] なので \[ \Leg{q}{p}\Leg{p}{q} =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}. \] これは平方剰余の相互法則そのものです。