Rousseauによる平方剰余の相互法則の短い証明
この記事ではRousseauによる平方剰余の相互法則の短い証明を紹介します．
素数$p$および$p$と互いに素な整数$n$に対して
$$
\left(\dfrac{n}{p}\right)=\begin{cases}
1&(\overline{n}\in (\mathbb{F}_p^\times)^2)\\
-1&(\overline{n}\not\in (\mathbb{F}_p^\times)^2)
\end{cases}
$$
と定めます．ただし$\overline{n}$は$n$の剰余類を表します．$\mathbb{F}_p^\times$は位数$p-1$の巡回群なので、$p$が奇素数ならば$(\mathbb{F}_p^\times)^2$は$\dfrac{p-1}{2}$乗写像$\mathbb{F}_p^\times\to \{1,-1\}$の核に一致します．したがって$p$が奇素数ならば
$$
\left(\dfrac{n}{p}\right)\equiv n^{\frac{p-1}{2}}\mod p
$$
が成り立ちます．これをEulerの規準といいます．平方剰余の相互法則とは次の定理のことです．
相異なる奇素数$p,q$に対して$\left(\dfrac{q}{p}\right)\left(\dfrac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot \frac{q-1}{2}}$が成り立つ．
奇数$m$に対して
$L_m=\left\{n\in \mathbb{Z}\,\middle|\, 1\leq n\leq \dfrac{m-1}{2},\,(n,m)=1\right\}$
と定める．$1$以上$pq$未満で$p,q$と互いに素な整数のうち
- $L_{pq}$に含まれるもの全体の積を$A$、
- mod $p$で$L_p$に含まれるもの全体の積を$B_p$、
- mod $q$で$L_q$に含まれるもの全体の積を$B_q$とする．
これらはいずれも、各$n\in L_{pq}$に対して$n$と$pq-n$のうち片方を選んで掛けたものになっている．したがってこれらの値はmod $pq$で$\pm 1$倍を除いて一致する．$A=\varepsilon_pB_p\mod pq$および$A=\varepsilon_qB_q\mod pq$を満たす$\varepsilon_p,\varepsilon_q\in \{1,-1\}$を取る．
$\varepsilon_p$を決定するためにmod $q$で考える．Eulerの規準を使うと
\begin{align*}
A&=\dfrac{\left(\frac{pq-1}{2}\right)!}{p\times 2p \times\cdots\times \frac{q-1}{2}p\times q\times 2q\times\dots\times \frac{p-1}{2}q}\\
&\equiv\dfrac{((q-1)!)^{\frac{p-1}{2}}\left(\frac{q-1}{2}\right)!}{p^{\frac{q-1}{2}}\left(\frac{q-1}{2}\right)!}\mod q\\
&\equiv \left(\dfrac{p}{q}\right)((q-1)!)^{\frac{p-1}{2}}\mod q,\\
B_p&\equiv ((q-1)!)^{\frac{p-1}{2}} \mod q
\end{align*}
となるので$\varepsilon_p=\left(\dfrac{p}{q}\right)$であることがわかる．同様に$\varepsilon_q=\left(\dfrac{q}{p}\right)$である．
一方で$B_q$は$B_p$を定める積に現れる数$n$のうち「mod $p$で$L_p$に含まれるがmod $q$で$L_q$に含まれないもの」を全て$pq-n$に置き換えたものである．そのような$n$は中国剰余定理より$\dfrac{p-1}{2}\cdot\dfrac{q-1}{2}$個あるので
$$
B_q=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}B_p\mod pq
$$
が成り立つ．よって$\varepsilon_p\varepsilon_q=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$である．
