平方剰余

$(a/p)=1$ のとき
$$x^2\equiv g^k\equiv a\Mod{p}$$
となる $x$ が存在する。
$$g^{k(p-1)/2}\equiv x^{k(p-1)}\equiv 1\Mod{p}$$
であるが、$g$ は原始根なので $k/2$ は整数、すなわち $k$ は偶数となる。

逆に $k=2m$ が偶数のとき
$$(g^m)^2\equiv g^k\equiv a\Mod{p}$$
となるから $(a/p)=1$ である。

$p$ と互に素な整数 $a$ について、$g$ を底とする $a$ の指数を $k$ とおく。
$(a/p)=1$ のとき 定理1 より $k$ は偶数であるから
$$a^{(p-1)/2}\equiv g^{k(p-1)/2}\equiv 1\Mod{p}$$
となる。また $(a/p)=-1$ のとき $k$ は奇数であるから
$$a^{(p-1)/2}\equiv g^{k(p-1)/2}\equiv g^{(p-1)/2}\equiv -1\Mod{p}$$
となる。$(a/p)=0$ のときは
$$\left(\frac{a}{p}\right)\equiv 0\equiv a^{(p-1)/2}\Mod{p}$$
となる。

$p\mid (ab)$ ならば両辺ともに $0$ となるので、$\gcd(a, p)=\gcd(b, p)=1$ としてよい。さらにこのとき
$p=2$ ならば両辺ともに $1$ となるので、$p$ は奇数としてよい。
このとき 定理2 より
$$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\equiv a^{(p-1)/2}b^{(p-1)/2}\equiv (ab)^{(p-1)/2}\equiv \left(\frac{ab}{p}\right)\Mod{p}$$
がすぐにわかるが、$p>2$ なので
$$\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)$$
となる。

$$s_k=\left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ p-r_k & (r_k\geq (p-1)/2)\end{array}\right.$$
とおく。
$k=1, 2, \ldots, (p-1)/2$ に対して $p$ は $ak$ を割り切らないから $r_k\neq 0$ なので $s_k\neq 0$ となる。
よって $1\leq s_k\leq (p-1)/2$ がつねに成り立つ。

一方、$s_k=s_\ell$ ならば $k=\ell$ となる。実際このとき
$r_k=r_\ell$ または $r_k=p-r_\ell$ となるが、$2\leq k+\ell\leq p-1$ より
$$r_k+r_\ell\equiv a(k+\ell)\not\equiv 0\Mod{p}$$
となるので、$r_k=r_\ell$ つまり
$$r_k-r_\ell\equiv a(k-\ell)\equiv 0\Mod{p}$$
となり、$\abs{k-\ell}< p$ より $k=\ell$ でなければならない。

よって、$s_k (k=1, 2, \ldots, (p-1)/2)$ は $1, 2, \ldots, (p-1)/2$ を$1$回ずつとるので
$$\prod_{k=1}^{(p-1)/2} s_k\equiv \left[\frac{p-1}{2}\right]!\Mod{p}$$
となる。また
$$\prod_{k=1}^{(p-1)/2} r_k\equiv \prod_{k=1}^{(p-1)/2} (ak)\equiv a^{(p-1)/2} \left[\frac{p-1}{2}\right]!\equiv \left(\frac{a}{p}\right)\left[\frac{p-1}{2}\right]!\Mod{p}$$
となる。一方
$$s_k\equiv \left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ -r_k & (r_k\geq (p-1)/2)\end{array}\right. \Mod{p}$$
となるから
$$\prod_{k=1}^{(p-1)/2} s_k\equiv (-1)^\mu \prod_{k=1}^{(p-1)/2} r_k \Mod{p}$$
が成り立つ。よって
$$1\equiv (-1)^\mu \left(\frac{a}{p}\right)\Mod{p}$$
つまり
$$\left(\frac{a}{p}\right)\equiv (-1)^{-\mu}\equiv (-1)^\mu \Mod{p}$$
が成り立つ。

Gaussの補題 より
$$2, 4, \ldots, p-1$$
のうち、$p/2$ より大きいものの個数を $\mu$ とおくと
$$\left(\frac{2}{p}\right)=(-1)^\mu$$
となる。

$$\mu=\frac{p-1}{2}-\floor{\frac{p}{4}}$$
であるから、
$$\left(\frac{2}{p}\right)=(-1)^{\frac{p-1}{2}-\floor{\frac{p}{4}}}$$
となる。
$p\equiv 1\Mod{4}$ のとき
$$\frac{p-1}{2}-\floor{\frac{p}{4}}=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$$
となる。$p\equiv 1\Mod{8}$ のとき、右辺は偶数だから $(2/p)=1$ となる,
$p\equiv 5\Mod{8}$ のとき、右辺は奇数だから $(2/p)=-1$ となる。
$p\equiv 3\Mod{4}$ のとき
$$\frac{p-1}{2}-\floor{\frac{p}{4}}=\frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}$$
となる。$p\equiv 7\Mod{8}$ のとき、右辺は偶数だから $(2/p)=1$,
$p\equiv 3\Mod{8}$ のとき、右辺は奇数だから $(2/p)=-1$ となる。
これによって $(2/p)$ は決定される。

定理3 より
$$\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)$$
となるから、 第1補充法則 とあわせて $p\equiv 1, 3$ のとき $(-2/p)=1$,
$p\equiv 5, 7$ のとき $(-2/p)=-1$ となる。

$$V=\{(x, y)\in\Z^2|1\leq x\leq (p-1)/2, 1\leq y\leq (q/p)x\},$$
$$W=\{(x, y)\in\Z^2|1\leq y\leq (q-1)/2, 1\leq x\leq (p/q)y\}$$
とおくと
$$\frac{sq}{p}=\#\{y\in\Z| 1\leq y\leq sq/p\}=\#\{(s, y)\in\Z^2|1\leq y\leq sq/p\}$$
より
$$S(q, p)=\# V$$
が成り立つ。同様に
$$S(p, q)=\# W$$
となる。
$$U=\Z^2\cap ([1, (p-1)/2]\times [1, (q-1)/2])=\{(x, y)\in\Z^2|1\leq x\leq (p-1)/2, 1\leq y\leq (q-1)/2\}$$
とおくと $V, W$ は $U$ の部分集合で
$$U=V\cup W, V\cap W=\emptyset$$
が成り立つ。実際、$U$ 上の点は $1\leq y\leq (q/p)x$ のとき $V$ に属し
$(q/p)x\leq y\leq (q-1)/2$ のとき $x\leq (p/q)y$ となるから $W$ に属する。
また $1\leq x\leq (p-1)/2$ のとき $p$ は $qx$ を割り切らないから $V$ 上の点では $y=(q/p)x$ は成り立たないので
$V, W$ は共通部分をもたない。よって
$$S(q, p)+S(p, q)=\#V +\#W =\#U = \frac{(p-1)(q-1)}{4}$$
が成り立つ。

$kq (k=1, 2, \ldots, (p-1)/2)$ を $p$ で割った余りを $r_k$ とし
$r_k>p/2$ となる $k$ の個数を $\mu$ とおく。また
$$s_k=\left\{\begin{array}{cl}r_k & (r_k\leq (p-1)/2)\\ p-r_k & (r_k\geq (p-1)/2)\end{array}\right.$$
とおく。 Gaussの補題 の証明と同様にして、$s_k$ は $1, 2, \ldots, (p-1)/2$ を1回ずつとるから
$$\sum_{k=1}^{(p-1)/2} s_k=\sum_{k=1}^{(p-1)/2} k=\frac{1}{2}\times\frac{p-1}{2}\times\frac{p+1}{2}=\frac{p^2-1}{8}$$
となる。
一方
$$\sum_{k=1}^{(p-1)/2} s_k=\sum_{s_k=r_k} s_k+\sum_{s_k=p-r_k} s_k =\sum_{s_k=r_k} r_k+\sum_{s_k=p-r_k} (p-r_k)=\sum_{s_k=r_k} r_k+ \mu p-\sum_{s_k=p-r_k} r_k$$
だから
$$ \sum_{s_k=r_k} r_k+ \mu p-\sum_{s_k=p-r_k} r_k=\frac{p^2-1}{8} \label{eq1}\tag{1} $$
が成り立つ。

定義から
$$kq=p\floor{\frac{kq}{p}}+r_k$$
であるから
$$q\frac{p^2-1}{8}=pS(q, p)+\sum_{k=1}^{(p-1)/2} r_k$$
となるので \eqref{eq1} より
$$\frac{(q-1)(p^2-1)}{8}=pS(q, p)-\mu p+2\sum_{s_k=p-r_k} r_k$$
が成り立つ。$p, q$ はともに奇数なので $8\mid (p^2-1)$ より、左辺は偶数であるから
$$S(q, p)\equiv \mu\Mod{2}$$
つまり
$$(-1)^\mu=(-1)^{S(q, p)}$$
が成り立つ。よって Gaussの補題 より
$$\left(\frac{q}{p}\right)=(-1)^\mu=(-1)^{S(q, p)}$$
が成り立つ。