平方剰余の相互法則

$1\le k\le h$ について $ka$ の絶対値最小剰余を $\rho_k$ とおく。$p\nmid k$、$p\nmid a$ なので Euclidの補題 により $p\nmid ka$ であり、$\rho_k\neq0$、$1\le|\rho_k|\le h$ である。

1. $1\le k< l\le h$ で $|\rho_k|=|\rho_l|$ とすると、$\rho_k=\rho_l$ なら $ka\equiv la$、$\rho_k=-\rho_l$ なら $ka\equiv-la$ であり、いずれにしても $p\mid(l\mp k)a$ である。$p\nmid a$ なので $p\mid l\mp k$ であるが、$0< l-k< p$、$0< l+k\le2h=p-1$ なのでどちらも起こらない。よって $|\rho_1|,\dots,|\rho_h|$ は $1,\dots,h$ の中の相異なる $h$ 個であり、$1,\dots,h$ のすべてにちょうど 1 回ずつ一致する。
2. 1 により $\prod_{k=1}^h|\rho_k|=h!$ であり、$\rho_k=\pm|\rho_k|$ のうち負号は $\nu$ 個なので
   $$ \prod_{k=1}^h(ka)\equiv\prod_{k=1}^h\rho_k=(-1)^\nu h!\pmod p $$
   である。左辺は $a^hh!$ に等しい。$h!$ は $p$ より小さい正の整数の積なので $p$ と互いに素であり、両辺から約せる（合同式 の記事の定理「合同式の約分」）。よって $a^h\equiv(-1)^\nu\pmod p$ であり、Euler の規準 $a^h\equiv\left(\frac ap\right)$ と合わせて $\left(\frac ap\right)\equiv(-1)^\nu\pmod p$ を得る。両辺は $\pm1$ で、$p\ge3$ なので $1\not\equiv-1\pmod p$ であり、等式 $\left(\frac ap\right)=(-1)^\nu$ が従う。$\square$

thm-qr-supplementary の 2 を示す。lem-qr-gauss を $a=2$ に使う。$2k$（$1\le k\le h$）は $2\le2k\le p-1$ なので、その絶対値最小剰余は $2k\le h$ なら $2k$、$2k>h$ なら $2k-p<0$ である。$2k>h$ は $2k>\frac{p-1}2$、すなわち $k>\frac{p-1}4$ と同値であり、そのような $k\le h$ の個数は $\nu=h-\lfloor\frac{p-1}4\rfloor$ である（$\lfloor\cdot\rfloor$ は床関数）。$p$ を $8$ で割った余りで場合分けすると、$p=8m+r$ として
$$ \begin{array}{c|cccc} r&1&3&5&7\\\hline h&4m&4m+1&4m+2&4m+3\\ \lfloor\frac{p-1}4\rfloor&2m&2m&2m+1&2m+1\\ \nu&2m&2m+1&2m+1&2m+2 \end{array} $$
である。よって $\nu$ が偶数、すなわち $\left(\frac2p\right)=1$ となるのは $p\equiv\pm1\pmod8$ のときに限る。一方 $\frac{p^2-1}8$ は、$p=8m\pm1$ なら $8m^2\pm2m$ で偶数、$p=8m\pm3$ なら $8m^2\pm6m+1$ で奇数であり、$(-1)^{(p^2-1)/8}$ も同じ規則に従う。$\square$

$1\le x\le h$ について $ax=p\lfloor ax/p\rfloor+r_x$、$0< r_x< p$ とする（$p\nmid ax$）。$ax$ の絶対値最小剰余は、$r_x\le h$ なら $r_x$、$r_x>h$ なら $r_x-p$ である。前者の $r_x$ を $u_1,\dots,u_{h-\nu}$、後者について $v_j:=p-r_x$ とおいたものを $v_1,\dots,v_\nu$ とすると、$\nu$ は lem-qr-gauss の $\nu$ であり、同補題の 1 により $\{u_i\}\cup\{v_j\}=\{1,\dots,h\}$（重複なし）である。
$T:=\sum_{x=1}^hx=\sum_iu_i+\sum_jv_j$ とおく。$ax=p\lfloor ax/p\rfloor+r_x$ を $x=1,\dots,h$ について足すと
$$ aT=pS(a,p)+\sum_iu_i+\sum_j(p-v_j)=pS(a,p)+\nu p+\sum_iu_i-\sum_jv_j $$
である。$a$ と $p$ は奇数なので、両辺を $2$ を法として見ると $aT\equiv T$、$pS\equiv S$、$\nu p\equiv\nu$、$-\sum v_j\equiv\sum v_j$ であり
$$ T\equiv S(a,p)+\nu+\sum_iu_i+\sum_jv_j=S(a,p)+\nu+T\pmod2 $$
となる。よって $S(a,p)\equiv\nu\pmod2$ であり、lem-qr-gauss の 2 から $\left(\frac ap\right)=(-1)^\nu=(-1)^{S(a,p)}$ を得る。$\square$

平面の格子点 $(x,y)$（$x,y$ は整数）で $1\le x\le h$、$1\le y\le k$ を満たすものの集合を $R$ とすると、$R$ はちょうど $hk$ 個の点からなる。$R$ の点で $py=qx$ となるものはない。実際 $py=qx$ なら $p\mid qx$ で、$p\nmid q$ なので $p\mid x$ となるが、$1\le x\le h< p$ である。したがって $R$ の点は $qx>py$（直線 $y=\frac qpx$ の下）か $qx< py$（上）のどちらか一方を満たす。
$x$ を固定すると、$qx>py$ を満たす $R$ の点 $(x,y)$ は $1\le y<\frac{qx}p$ かつ $y\le k$ のものである。$x\le h$ なら $\frac{qx}p\le\frac{q(p-1)}{2p}<\frac q2$ であり、$q$ は奇数なので $\frac q2$ より小さい整数は $k=\frac{q-1}2$ 以下である。よって条件 $y\le k$ は自動的に満たされ、そのような $y$ は $\lfloor qx/p\rfloor$ 個ある（$qx/p$ は整数でない）。$x=1,\dots,h$ について足すと、直線の下にある点は $\sum_{x=1}^h\lfloor qx/p\rfloor$ 個である。$p$ と $q$、$x$ と $y$ の役割を入れ替えた同じ議論で、直線の上にある点は $\sum_{y=1}^k\lfloor py/q\rfloor$ 個である。両者の和が $R$ の点の総数 $hk$ に等しい。$\square$

thm-qr-main を示す。$h=\frac{p-1}2$、$k=\frac{q-1}2$ とおく。$p,q$ は相異なる奇素数なので、$q$ は $p$ で割り切れない奇数であり、$p$ も $q$ で割り切れない奇数である。lem-qr-eisenstein を 2 回使うと
$$ \left(\frac qp\right)=(-1)^{\sum_{x=1}^h\lfloor qx/p\rfloor},\qquad\left(\frac pq\right)=(-1)^{\sum_{y=1}^k\lfloor py/q\rfloor} $$
であり、掛け合わせて lem-qr-lattice を使うと
$$ \left(\frac pq\right)\left(\frac qp\right)=(-1)^{hk}=(-1)^{\frac{p-1}2\cdot\frac{q-1}2} $$
を得る。$\square$

thm-qr-main を $q=3$ に使うと、符号は $(-1)^{\frac{p-1}2\cdot\frac{3-1}2}=(-1)^{(p-1)/2}$ なので $\left(\frac3p\right)=(-1)^{(p-1)/2}\left(\frac p3\right)$ である。$\left(\frac p3\right)$ は $p\equiv1\pmod3$ なら $1$、$p\equiv2\pmod3$ なら $-1$ であり、$(-1)^{(p-1)/2}$ は $p\equiv1\pmod4$ なら $1$、$p\equiv3\pmod4$ なら $-1$ である。$p\ge5$ は $2$ でも $3$ でも割り切れないので、$p$ を $12$ で割った余りは $1,5,7,11$ のどれかであり、それぞれ $(p\bmod3,\ p\bmod4)=(1,1),(2,1),(1,3),(2,3)$ に対応する。したがって $\left(\frac3p\right)$ は順に $1,-1,-1,1$ であり、主張を得る。$\square$

正の奇数 $m,n$ について
$$ \frac{mn-1}2-\frac{m-1}2-\frac{n-1}2=\frac{(m-1)(n-1)}2,\qquad\frac{m^2n^2-1}8-\frac{m^2-1}8-\frac{n^2-1}8=\frac{(m^2-1)(n^2-1)}8 $$
である。$m-1,n-1$ は偶数なので最初の右辺は偶数であり、$m^2-1=(m-1)(m+1)$ は $8$ で割り切れる（連続する 2 つの偶数の積）ので 2 番目の右辺も偶数である。したがって $\chi_1(n):=(-1)^{(n-1)/2}$、$\chi_2(n):=(-1)^{(n^2-1)/8}$ は正の奇数全体で乗法的（$\chi(mn)=\chi(m)\chi(n)$）である。同じ理由で $\epsilon(m,n):=(-1)^{\frac{m-1}2\cdot\frac{n-1}2}$ は各変数について乗法的である。実際 $\frac{m-1}2\cdot\frac{nn'-1}2\equiv\frac{m-1}2\bigl(\frac{n-1}2+\frac{n'-1}2\bigr)\pmod2$ である。

1. $n=p_1\cdots p_r$ とすると、thm-qr-supplementary により $\left(\frac{-1}n\right)=\prod_i\chi_1(p_i)=\chi_1(n)$、$\left(\frac2n\right)=\prod_i\chi_2(p_i)=\chi_2(n)$ である。
2. $m=p_1\cdots p_r$、$n=q_1\cdots q_s$（奇素数、重複を許す）とする。$m,n$ は互いに素なので $p_i\neq q_j$ である。Jacobi 記号は分子についても分母についても乗法的なので
   $$ \left(\frac mn\right)\left(\frac nm\right)=\prod_{i,j}\left(\frac{p_i}{q_j}\right)\left(\frac{q_j}{p_i}\right)=\prod_{i,j}\epsilon(p_i,q_j)=\epsilon(m,n) $$
   である。2 つ目の等号は thm-qr-main、3 つ目は $\epsilon$ の各変数についての乗法性による。$m=1$ または $n=1$ のときは両辺とも $1$ である。$\square$