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$$

book on the Riemann hypothesis

ISBN: 978-7-302-29324-8

Euclidean algorithm, 也就是常说的辗转相除法, 通过有限步骤来找出两个整数 $$a,b$$ 的最大公约数 $$(a,b)$$.

$r_0=q_1r_1+r_2,\quad 0<r_2<r_1, q_1=\left[\frac{r_0}{r_1}\right];$

$r_1=q_2r_2+r_3,\quad 0<r_3<r_2, q_2=\left[\frac{r_1}{r_2}\right];$

$\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$

$r_{n-1}=q_nr_n,\quad q_n=\left[\frac{r_{n-1}}{r_n}\right].$

$$\left[x\right]$$ 表示不超过 $$x$$ 的最大整数. $$r_n=(a,b).$$

$$r_i=s_ia+t_ib( i=0,1,2,\dotsc,n).$$

$$\{s_i\},\{t_i\}$$ 可由下面的递推关系定出:

$$s_0=1,s_1=0,s_{i+1}=s_{i-1}-q_is_i,$$

$$t_0=0,t_1=1,t_{i+1}=t_{i-1}-q_it_i,$$

$$i=1,2,\dotsc,n.$$ 注意, 我们这里特意根据需要把 $$\{s_i\},\{t_i\}$$ 往下都多算了一项 $$s_{n+1}, t_{n+1}$$. 记 $$r_{n+1}=0$$.

$$t_ib\equiv r_i\pmod a$$

1.  如果 $$a>b,$$ 则 $$q_i\geqslant1(i=1,2,\dotsc,n), q_n\geqslant2;$$
2.  $$\{s_i\},\{t_i\}$$ 是交错的, 正负相间, 即 $$s_i=(-1)^i|s_i|,t_i=(-1)^{i+1}|t_i|,i=1,2,\dotsc,n+1;$$
3.  $$0=|s_1|<1=|s_2|<|s_3|<\dotsb<|s_{n+1}|;$$
4.  $$1=|t_1|\leqslant |t_2|<|t_3|<\dotsb<|t_{n+1}|;$$
5.  $$|s_{i+1}|=|s_{i-1}|+q_i|s_i|,|t_{i+1}|=|t_{i-1}|+q_i|t_i|,i=1,2,\dotsc,n;$$
6.  $$a=r_{i-1}|t_i|+r_i|t_{i-1}|, i=1,2,\dotsc,n+1;$$
7.  $$s_{n+1}=\dfrac{(-1)^{n+1}b}{(a,b)},t_{n+1}=\dfrac{(-1)^na}{(a,b)};$$
8.   如果 $$(a,b)=1,$$ 那么 $$|s_n|\leqslant \frac b2,|t_n|\leqslant \frac a2.$$

$$\begin{split}a & =r_{i-1}|t_i|+r_i|t_{i-1}|\\& =(q_ir_i+r_{i+1})|t_i|+r_i|t_{i-1}|\\& =r_i(q_i|t_i|+|t_{i-1}|)+r_{i+1}|t_i|\\& =r_i|t_{i+1}|+r_{i+1}|t_i|,\end{split}$$

$a=r_n|t_{n+1}|+r_{n+1}|t_n|=|t_{n+1}|d,$

$|s_{n+1}| =|s_{n-1}|+q_n|s_n|\geqslant q_n|s_n|\geqslant 2|s_n|,$

$$bx\equiv y\pmod a,$$

$$r_{k-1}>\sqrt a\geqslant r_k,$$

$a=r_{k-1}|t_k|+r_k|t_{k-1}|\geqslant r_{k-1}|t_k|>\sqrt a|t_k|,$

$bt_k\equiv r_k\pmod a,$

$r_k\equiv ut_k\pmod p, 1\leqslant |t_k|<\sqrt p.$

9.   $$n$$ 是偶数;
10.  数列 $$\{|t_i|:i=n+1,n,\dotsc,1\}$$ 与 $$r$$-数列相同, 即 $$|t_{n+1-i}|=r_i(i=0,1,2,\dotsc, n+1);$$
11.  $$q$$-数列是对称的, 即 $$q_i=q_{n+1-i}(i=1,2,\dotsc, n);$$
12.   $$p\bigm|(r_i^2+t_i^2)(i=0,1,2,\dotsc,n+1);$$
13.   $$r_{\frac n2-1}>\sqrt p>r_{\frac n2}.$$

$p\bigm|(r_k^2+t_k^2),\quad |t_k|=r_{k+1},\quad r_{k-1}>\sqrt p>r_k>r_{k+1}.$

$t_nu\equiv 1\pmod p.$

$t_n\equiv -u\pmod p,$

$|t_n+u|\leqslant |t_n|+|u|<p,$

$t_{n+1}=(-1)^n|t_{n+1}|=p.$

$(t_iu)^2\equiv r_i^2\pmod p,$

$p=r_k|t_{k+1}|+r_{k+1}|t_k|=r_k^2+r_{k+1}^2,$

$r_{k-1}=q_kr_k+r_{k+1}\geqslant r_k+r_{k+1}$

$r_{k-1}^2>r_k^2+r_{k+1}^2=p,$

Euler 公式  假定 $$(a,b)=1,a=q_1b+r_2.$$ 采用归纳法, 假设已有 $$b=f(q_2,q_3,\dotsc,q_n),$$$$r_2=f(q_3,q_4,\dotsc,q_n),$$ 来指出有一个函数 $$f,$$ 使得 $$a=f(q_1,q_2,\dotsc,q_n).$$ 函数 $$f$$ 是一些乘积的和: $$q_1,q_2,q_3,\dotsc,q_n$$ 的积; 去掉 $$q_1,q_2,\dotsc,q_n$$ 的任意连续两项后得到的积; 再去掉 $$q_1,q_2,\dotsc,q_n$$ 的任意两个不同的连续两项后得到的积, 依次类推. 比如, $$n=5$$ 时, 有

$f(q_1,q_2,\dotsc,q_5)=q_1q_2q_3q_4q_5+q_3q_4q_5+q_1q_4q_5+q_1q_2q_5+q_1q_2q_3+q_5+q_3+q_1.$

$$n$$ 为偶数时, 把 $$q_1,q_2,\dotsc,q_n$$ 全部去掉时, 约定积是 $$1$$.

1. 存在 $$x,y\in\Bbb Q,$$ 使得 $$n=x^2+y^2$$;
2. 存在 $$x,y\in\Bbb N,$$ 使得 $$n=x^2+y^2$$.

$q^2n=a^2+b^2,$

$l^2<n<(l+1)^2.$

$au+bv\equiv au^\prime+bv^\prime\pmod n,$

$n\bigm|(ax+by),$

$n\bigm|(ax+by)(ax-by)=a^2x^2-b^2y^2.$

$n\bigm|(a^2+b^2)y^2=a^2y^2+b^2y^2,$

$n\bigm|((a^2x^2-b^2y^2)+(a^2y^2+b^2y^2))=a^2(x^2+y^2).$

$$a\equiv\frac12{2n\choose n}\pmod p,$$

$$a\equiv\frac12{2n\choose n}\pmod p,\quad a<\frac{|p|}2$$

$$b\equiv a(2n)!\pmod p,\quad b<\frac{|p|}2$$

Zagier 的一句话证明(1990)

$f:S\rightarrow S,\quad (x,y,z)\mapsto\begin{cases}(x+2z,z,y-x-z)\quad x<y-z;\$$2y-x,y,x-y+z)\quad y-z<x<2y;\\(x-2y,x-y+z,y)\quad 2y<x,\end{cases}$ 恰有一个不动点 \((1,1,\frac{p-1}4)$$, 这意味着 $$|S|$$ 为奇数, 从而 $$S$$ 的另一个对合

$g:S\rightarrow S,\quad(x,y,z)\mapsto(x,z,y)$

$p=x^2+4y^2=x^2+(2y)^2. \Box$

$$n\in\Bbb N^+$$, then

$$\prod_{(i,n)=1}i\equiv\begin{cases}\,-1\pmod n,\quad n=2,4,p^\alpha,2p^\alpha\\\quad1\pmod n, \quad \text{otherwise}\end{cases}$$

$$2,4,p^\alpha,2p^\alpha$$ 有原根, 此种情况下, 可以给出简单的证明. 至于完整的证明, 我还没有找出满意的办法, 下面是一种途径:

$$n\geqslant2, n=2^e p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$ 其中$$p_i\geqslant3(i=1,2,\dotsc,k)$$为质数, 则同余方程 $$x^2\equiv1\pmod n$$ 解的个数是 $$2^{k+\delta}$$, 这里
$$\delta=\begin{cases}0,\quad e=0,1,\\1,\quad e=2,\\2, \quad e\geqslant3.\end{cases}$$

$\prod_{(i,n)=1}i\equiv\prod_{ i^2\equiv1\pmod n} i\equiv(-1)^l\pmod n.$

Wilson 定理的组合证明

$\frac{(p-1）!}2 -\frac{p-1}2 =\frac12 ((p-1)! + 1 – p)$

Gauss 的经典传世名作, “算术研究(Disquisitiones Aritmeticae)”, 的中文版本, 已由哈尔滨工业大学出版社出版, 不过书的名字不是”算术研究”, 而是”算术探索”.

Disquisitiones Aritmeticae

Gauss 一生贡献众多, 以数论(Number Theory)中的这本”算术研究”, 以及微分几何(Differential Geometry)中的 Egregium theorem, 影响为最大.

“算术研究”是现代数论的开端. 这本书出现以前, 数论只是一些孤立定理与猜想. Gauss 首次将这些零星的结果加以系统的处理, 修补和改进了以往的证明, 并在此之上发展出了自己的一系列理论与成果. “算术研究” 亦是后来很多伟大数学家成果的出发点.

ISBN: 978-7-5603-3409-7