$$p$$ is a odd prime,  then

1. there are infinite primes $$q$$ such that $$q$$ is a quadratic residue modulo $$p$$;
2. there are infinite primes $$q$$ such that $$q$$ is a quadratic nonresidue modulo $$p$$.

$a_0=q, a_1=q+p,a_2=q+pa_1,a_3=q+pa_1a_2,\dotsc, a_n=q+pa_1a_2\dotsb a_{n-1},\dotsc$

$\bigg(\dfrac{kq_1q_2q_3\dotsm q_n+1}p\bigg)=-1.$

$\bigg(\frac qp\bigg) = \bigg(\frac pq\bigg).$

$a_1 = 4^k – p,$
$a_2 = 4^ka_1^2 -p,$
$a_3 = 4^ka_1^2a_2^2 -p,$
$\dotsc$
$a_n = 4^ka_1^2a_2^2\dotsm a_{n-1}^2-p,$
$\dotsc$

$\bigg(\frac qp\bigg)=\bigg(\frac {-p}q\bigg).$

$a_1 = 4+p,$
$a_2 = 4a_1^2 + p,$
$a_3 = 4a_1^2a_2^2 + p,$
$a_4 = 4 a_1^2a_2^2 a_3^2 + p,$
$\dotsc$
$a_n = 4 a_1^2a_2^2\dotsm a_{n-1}^2+ p,$
$\dotsc$

Sey Y.Kim 的证明也收录在 Biscuits of Number Theory 一书.

If $$p,q$$ are distinct odd primes,  then

$\left( \frac pq\right) \left( \frac qp\right) = (-1)^{\frac{(p-1)(q-1)}4},$

where $$\left( \frac{}{}\right)$$ is the Legendre symbol. 这就是被 Gauss 称为”数论酵母” 的二次互反律.

• 简单是首要条件. 基于简单的想法, 能揭示问题的本质, 加深对事物的理解.
• 美. 构思巧妙, 论证精妙方能展现出深刻. 当然, 简单其实也是一种美.
• 自然. 方法能用在更广泛的地方, 解决更多的问题.

For any odd $$n \in\Bbb N$$, denote by $$N_n$$ the number of solutions in $$\left( \Bbb Z / (q)\right)^n$$ to the equation

$x_1^2-x_2^2+x_3^2-\dotsb + x_n^2 = 1.$

If we substitute $$x_1 \gets x_1+x_2$$, then we get

$x_1^2+x_3^2-\dotsb + x_n^2-1 = -2x_1x_2.$

For any non-zero $$x_1$$-value and any values of $$x_3,\dotsc,x_n$$, there is a unique corresponding $$x_2$$-value. If $$x_1=0$$, there are no solutions, except if $$x_3^2-\dotsb + x_n^2 = 1$$ (which happens in $$N_{n-2}$$ cases): then all possible values of $$x_2$$ do the job. We find that

$N_n = q^{n-2}(q-1)+qN_{n-2}.$

and hence $$N_n = q^{n-1}+q^{\frac{n-1}{2}}(N_1-1) = q^{n-1}+q^{\frac{n-1}{2}}.$$ In particular,

$$N_p\equiv1+\left(\frac qp\right) \pmod p.$$

Next, $$N_p$$ can be classically determined as

$\sum_{t_1+\dotsb + t_p = 1}N(x_1^2 = t_1)N(x_2^2 = -t_2)N(x_3^2=t_3)\dotsm N (x_p^2=t_p),$

where the $$t_i$$ are in $$\Bbb Z/(q)$$ and $$N(\cdots)$$ denotes the number of solutions to the corresponding univariate equation. This can be rewritten as

$\sum_{t_1+\dotsb+t_p=1}\left(1+\left(\frac{t_1}q\right)\right)\left( 1+\left( \frac{-t_2}q\right)\right)\left( 1+\left( \frac{t_3}q\right)\right)\dotsm \left( 1+\left( \frac{t_p}q\right)\right),$

When expanding out the product, only the terms $$1\cdot 1 \cdot 1 \cdots 1$$ and $$\left(\frac{t_1}q\right)\cdot\left(\frac{-t_2}q\right)\cdot\left( \frac{t_3}q\right)\cdots\left( \frac{t_p}q\right)$$ should be taken into consideration; the other terms disappear because Legendre symbols sum up to zero: $$\sum\limits_{t\in\Bbb Z/(q)}\left(\frac tq\right) = 0.$$ Therefore, the above expression simplifies to

$q^{p-1}+\left( \frac{(-1)^{\frac{p-1}2}}q\right)\sum_{t_1+\dotsb+t_p = 1}\left(\frac{t_1t_2t_3\dotsm t_p}q\right).$

Modulo $$p$$, the latter sum almost completely vanishes, since the tuples $$(t_1,\dotsc,t_p)$$ satisfying $$t_1+\dotsb + t_p = 1$$ with not all $$t_i$$ equal to $$p^{-1}$$ can be collected in groups of size $$p$$ by cyclic permutation. Note that $$p$$ is indeed a multiplicative unit in $$\Bbb Z/(q)$$. We thus obtain

$$N_p\equiv1+\left( \frac{(-1)^{\frac{p-1}2}}q\right) \left( \frac{p^{-p}}q\right) \equiv1+(-1)^{\frac{p-1}2\frac{q-1}2}\left( \frac pq\right) \pmod p.$$

The last congruence follows from Euler’s criterion $$\left(\frac aq\right) \equiv a^{\frac{q-1}2} \pmod q$$ and the observation that $$p^{-p}$$ is a square in $$\Bbb Z/(q)$$ if and only if $$p$$ is a square in $$\Bbb Z/(q)$$.

Comparing $$(1)$$ and $$(2)$$, the reciprocitylaw follows. $$\Box$$

Let $$p = 2m+1$$ and $$q$$ be distinct odd primes and let $$N$$ denote the number of solutions of the equation

$x_1^2 + \ldots + x_p^2 = 1$

in the finite field $$\Bbb F_q$$.

The group $$\Bbb Z/p\Bbb Z$$ acts on the solution space $$X$$ by shifting indices: if $$(x_1, \ldots, x_p) \in X$$, then so is $$(x_a,x_{a+1}, \dotsc)$$ for each $$a \in {\mathbb Z}/p{\mathbb Z}$$, where the indices have to be read modulo $$p$$. Each orbit has exactly $$p$$ elements except if there is an $$x$$ with $$(x,x,\ldots,x) \in X$$: the orbit of this element has $$1$$ element. Now $$(x,x,\ldots,x) \in X$$ if and only if $$px^2 = 1$$ is solvable in $$\Bbb F_q$$, hence

$$N \equiv \Big( \frac pq \Big) + 1 \pmod p.$$

We make a change of variables to transform the diagonal equation into an equation where counting the number of solutions is easier. To this end, consider the matrix

$A = \left( \begin{matrix} 0 & 1 & & & & & & \\ 1 & 0 & & & & & & \\ & & 0 & 1 & & & & \\ & & 1 & 0 & & & & \\ & & & & \ddots & & & \\ & & & & & 0 & 1 & \\& & & & & 1 & 0 & \\& & & & & & & a\end{matrix} \right)$

with $$a = (-1)^{\frac{p-1}2}$$. Since $$\det A = 1$$, this matrix is congruent to the unit matrix, hence $$X$$ and the solution spaces $$X^\prime$$ of the equation $$x^T A x = 1$$,i.e.,recall that $$p=2m+1$$, of

$2(y_1z_1+\dotsb+y_mz_m)+ax_p^2=1$

are isomorphic.

For counting the number of solutions of $$X^\prime$$, observe that if $$(y_1, \dotsc, y_m) = 0$$, we have $$q^m(1+a^{\frac{q-1}2})$$ possibilities for choosing $$z_1, \dotsc, z_m$$ and $$x_p$$.

If $$y = (y_1, \dotsc, y_m) \ne 0$$, on the other hand, then for each choice of $$y$$ and $$x_p$$ we have to count the number of points on a hyperplane of dimension $$m$$; there are $$q^{m-1}$$ points on such a hyperplane, and the number of overall possibilities in this case is $$(q^m-1) \cdot q \cdot q^{m-1} = q^m(q^m-1)$$.

Thus we find

$$\begin{split} N & = q^m (1+a^{\frac{q-1}2})+q^m(q^m-1) \\&=q^m(q^m+(-1)^{\frac{p-1}2\frac{q-1}2})\\ & \equiv\Big(\frac qp\Big)\bigg(\Big(\frac qp\Big)+(-1)^{\frac{p-1}2\frac{q-1}2}\bigg)\\&\equiv1+(-1)^{\frac{p-1}2\frac{q-1}2}\Big(\frac qp\Big)\pmod p.\end{split}$$

Comparing $$(3)$$ and $$(4)$$, gives the quadratic reciprocity law. $$\Box$$