Aug 212012
 

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 称为”数论酵母” 的二次互反律.

自 Legendre 的那个没有完成的证明以来, 据 Reciprocity Laws: From Euler to Eisenstein 的作者 Franz Lemmermeyer 统计, 发表的证明是 \(240\) 个. 可以预见的到, 这个数字还会不断增加. 这些证明的作者, 发表年份,使用的方法以及文献的详细列表可在 Lemmermeyer 的个人主页找到. 其中, \(1889\) 这一年就有 \(6\) 个证明公布, \(1893,1951,1961\) 年也各有 \(5\) 个证明发表在不同的期刊上. 仅看从 \(1950\) 年到今天的这 \(60\) 多年, 只有 \(1956,1959,1968,1970,1975,1977,1982,1986,1988,1996,2002\) 这 \(11\) 年没有证明发表.不过, Lemmermeyer 的统计好像有小错误, 例如 Wouter Castryck 在 \(2008\) 年发表了一篇文章, 办法类似于 V. A. Lebesgue 在 \(1838\) 年的论证, 但 Lemmermeyer 的统计认为 Castryck 的证明在 \(2007\) 年给出.

这么多的证明, 想要全部分门别类, 整理好写出来, 肯定是困难的. 文献多, 不容易都找到. 即便都找齐了, 也因为是不同的语言, 也不能都看懂. 这些方法各有繁简. 哪个证明才是最简单的呢? 显然, Proofs from THE BOOK 给出的两个途径, 是比较繁琐的; Jean-Pierre Serre 在他的 A Couse in Arithmetic 第一章给出的都依靠 Gauss 引理的两个证明, 也不算太简单. 那么, 到底哪个才是最简单的呢? 各人的看法可能有不同. 但, 美妙的, 能给人以深刻印象, 令人荡气回肠的证明, 应该有一些共同的特征, 或者说一个证明要能成为好的证明, 美丽的证明, 应该有一定的门槛, 满足一定的条件. 我们试着列出这些条件:

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

同时满足这些要求的证明不容易找到, Castryck 的证明大概可以满足前两条. 下面是他的详细论证:

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,

\begin{equation}N_p\equiv1+\left(\frac qp\right) \pmod p.\end{equation}

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

\begin{equation}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.\end{equation}

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\)

接下来的论证, 是 Aurelien Bessard (2010) 改编自 V. A. Lebesgue 和 Eisenstein的一个证明:

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

\begin{equation} N \equiv \Big( \frac pq \Big) + 1 \pmod p.\end{equation}

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{equation}\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}\end{equation}

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

Aug 202012
 

卢昌海谈 Riemann 猜想(Riemann hypothesis)的系列文章, 刚刚由清华大学出版社结集出版, 书名”黎曼猜想漫谈”.

the Riemann hypothesis

book on the Riemann hypothesis

从卢昌海动笔写第一篇谈Riemann 猜想的小文章, 到现在出版成书, 过去了八年仅仅差三个月. 在正式出版之前, 其内容已经在网络广为流传, 被很多人转载, 也被数学杂志连载刊登过, 影响巨大. 现在作为数学科普出版, 相信会促进科学的传播, 有助于大家了解这个数学中最重要的难题.

书名: 黎曼猜想漫谈
ISBN: 978-7-302-29324-8
出版社: 清华大学出版社
作者: 卢昌海
出版日期: 2012年08月
定价: 25 人民币元

Aug 192012
 

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

具体说来, \(a,b\in\Bbb Z\), 我们假定 \(b>0\), 并记 \(r_0=a, r_1=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_0,r_1,r_2,\dotsc,r_n\) 冠名为(始于 \(a,b\) 的) Euclidean algorithm 余数数列.

记数列 \(\{s_i\},\{t_i\}\) 使得

\begin{equation}r_i=s_ia+t_ib( i=0,1,2,\dotsc,n).\end{equation}

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

\begin{equation}s_0=1,s_1=0,s_{i+1}=s_{i-1}-q_is_i,\end{equation}

\begin{equation}t_0=0,t_1=1,t_{i+1}=t_{i-1}-q_it_i,\end{equation}

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

看来, 又可以和连分数(Continued fraction)扯上关系了, 这似乎也揭示了采用辗转相除法与连分数来证明Fermat的定理, 其本质没有区别. 由于连分数与辗转相除法的关系, 也不让人意外. 好吧, 我们先暂且不牵涉到连分数, 而继续探讨 \(r_i,s_i,t_i\) 的性质. 分别把 \(\{r_i\},\{q_i\},\{t_i\}\) 称为 \(r\)-数列, \(q\)-数列, \(t\)-数列.

首先要指出的是, 式 \((1)\) 对 \(i=n+1\) 也成立, 即我们有 \(r_{n+1}=s_{n+1}a+t_{n+1}b=0\). 进而

\begin{equation}t_ib\equiv r_i\pmod a\end{equation}

总是成立.

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.\)

据 \(5,\) 数列 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个始于 \(|t_{n+1}|,|t_n|\) 的Euclidean algorithm 余数数列.

利用 \(5\) 以及 \(r_i\) 的性质, 进行归纳可得 \(6\). 事实上, 奠基显然. 假定 \(6\) 对 \(i\) 成立\((1\leqslant i\leqslant n),\) 那么
\begin{equation}\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}\end{equation}
这就得出了结果.

由 \(6\), 我们有

\[a=r_n|t_{n+1}|+r_{n+1}|t_n|=|t_{n+1}|d,\]

这里 \(d=r_n=(a,b).\) 根据 \(2\), 就得到了 \(t_{n+1}=\dfrac{(-1)^na}d.\)  然后, 因为 \(s_{n+1}a+t_{n+1}b=0\), 所以 \(s_{n+1}=\dfrac{(-1)^{n+1}b}d.\)

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

利用 \(7,\) 就得到 \(|s_n|\leqslant \frac b2.\) 同理可得 \(|t_n|\leqslant \frac a2.\)

做了这么多准备工作, 终于可以进行我们最重要的事情, 证明 Fermat 的平方和定理了. 为此, 还需要建立一条定理:

定理(Aubry 1913, Thue 1902, Vinogradov 1926)  \(a>b>0, (a,b)=1.\) 有 \(x,y\) 使

\begin{equation}bx\equiv y\pmod a,\end{equation}

且 \(1\leqslant |x|,|y|\leqslant \sqrt a.\)

事实上, \(r_0=a>\sqrt a>1=r_n,\) 必有 \(k(1\leqslant k \leqslant n)\) 使得

\begin{equation}r_{k-1}>\sqrt a\geqslant r_k,\end{equation}

根据 \(6\), 得

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

于是 \(|t_k|<\sqrt a.\) 最后, \((4)\) 说明

\[bt_k\equiv r_k\pmod a,\]

故此, \((t_k,r_k)\) 符合我们的要求.

现在, Fermat 的平方和定理呼之欲出. 下面是 Serret 于 \(1848\) 年给出的证明:

质数 \(p\equiv1\pmod4, u^2+1=lp, 1\leqslant u<\frac p2.\)

令 \(r_0=p, r_1=u.\) 选取 \(k\) 使得 \(r_{k-1}>\sqrt p>r_k,\) 此时

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

于是 \(r_k^2+t_k^2=p.\)

我们继续往前走, 探讨这种情况下, 可以得到的更精细的结果. 下面几条性质都假定 \(r_0=p, r_1=u,\) 谈到的 \(r\)-数列, \(q\)-数列, \(t\)-数列以及\(\{|t_i|:i=n+1,n,\dotsc,1\}\), 也是相应的由 \(p,u\) 得到的.

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}.\)

这些性质导出 Fermat 平方和是很容易的. 实际上, 若记 \(k=\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}.\]

故此 \(r_k^2+r_{k+1}^2=p.\)

现在来证明 \(2\bigm|n.\) 从 \((4),\) 以及 \(r_n=1\) 可得

\[t_nu\equiv 1\pmod p.\]

从而

\[t_n\equiv -u\pmod p,\]

也就是 \(p\bigm|(t_n+u).\) 结合

\[|t_n+u|\leqslant |t_n|+|u|<p,\]

可得 \(t_n+u=0, t_n=-u.\) 另一方面, 由 \(2\) 可知 \[t_n=(-1)^{n+1}|t_n|.\]

故而 \(2\bigm|n.\) 由 \(7\) 可有

\[ t_{n+1}=(-1)^n|t_{n+1}|=p.\]

从 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个始于 \(|t_{n+1}|=p,|t_n|=u\) 的Euclidean algorithm 余数数列, 知晓 \(\{|t_i|:i=n+1,n,\dotsc,1\}\) 与 \(r\)-数列相同, 因此, 其相应的商组成的数列与 \(q\)-数列一致; 另一方面, 从 \(5\) 看出这些商组成的数列刚好与 \(q\)-数列顺序相反, 于是, \(q_i=q_{n+1-i}(i=1,2,\dotsc, n).\)

再次根据 \((4),\) 得

\[(t_iu)^2\equiv r_i^2\pmod p,\]

这就是 \(p\bigm|(r_i^2+t_i^2).\)

既然 \(2\bigm|n,\) 可设 \(n=2k.\) 由 \(6,10\), 得

\[p=r_k|t_{k+1}|+r_{k+1}|t_k|=r_k^2+r_{k+1}^2,\]

于是 \(\sqrt p>r_k.\) 由

\[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,\]

于是 \(r_{k-1}>\sqrt p.\) 综合起来, 就完成了证明.

下面换一个想法, 不利用 \(6,7,8,\) 来证明 \(10, 9,13\). 先介绍 Euler 的一个从连分数中来的公式.

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\).

现在回到初始值 \(p,u.\) 先指出 \(10\) 的合理.

首先, 必定 \(t_{n+1}=\pm p.\) 类似前面已经指出的, \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个Euclidean algorithm 余数数列, 其相应的商组成的数列,从 \(5,\) 刚好与 \(q\)-数列顺序相反; 但是把自变量顺序颠倒, Euler 公式是不变的, 因此, \(|t_{n+1}|=p,\) 因为 \(p\) 与 \(|t_{n+1}|\) 都是这些商的同一个函数值. 再据 \((4), t_nu\equiv 1\pmod p.\) 于是 \(t_n\equiv -u\pmod p;\)  因 \(|t_n|<p,\) 所有 \(t_n=-u\) 或者 \(t_n=p-u.\) 但 \(t_n=p-u\) 的不可能的, 否则 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 就成了 \(p,p-u,u,\dotsc,\) 比 \(r\)-数列长, 矛盾. \(t_n=-u. \{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 的头两项是 \(p,u,\) 其必定与 \(r\)-数列相同. 现在 \(t_n<0, t\)-数列正负相间, 所以 \(n\) 是偶数.

利用 \(q\)-数列的对称性, 使用Euler 公式可说明, \(f(q_{\frac n2+1},\dotsc,q_n)^2\) 的每一项都会在 \(f(q_1,q_2,\dotsc,q_n)\) 中出现. 于是, \(r_{\frac n2}^2=f(q_1,\dotsc,q_{\frac n2})f(q_{\frac n2+1},\dotsc,q_n),\) 并且这式子中的每一项也会现身于 \(f(q_1,q_2,\dotsc,q_n)=p.\) 故此, \(r_{\frac n2}^2<p, p\) 是质数, 等号不能成立. 同样, 可以说明 \(f(q_1,q_2,\dotsc,q_n)\) 的每一项也会出现在 \(r_{\frac n2-1}^2=f(q_1,\dotsc,q_{\frac n2+1})f(q_{\frac n2},q_{\frac n2+1},\dotsc,q_n)\) 中, 于是 \(r_{\frac n2-1}^2>p.\)

Aug 182012
 

这里将在有理数域 \(\Bbb Q\) 中来考察 Fermat 的平方和, 慢慢走向椭圆曲线(elliptic curve).

首先指出, \(n\in\Bbb N\) 是否两个有理数的平方和, 与其是否两个整数的平方和, 是一码事.

定理  设 \(n\in\Bbb N\), 则下面两件事情等价:

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

只要说明 \(1\Rightarrow2\) 即可. 事实上, 这可归结到, 若有 \(q,n,a,b\in\Bbb N\) 使得

\[q^2n=a^2+b^2,\]

则 \(n\) 可表成两个整数的平方和. 可以认为 \((a,b)=1,\) 并且 \(n\) 不是完全平方. 记 \(l\in\Bbb N^+\) 使得

\[l^2<n<(l+1)^2.\]

于 \(au+bv\) 中, 令 \(u,v\) 分别取 \(0,1,2,\dotsc,l\), 共 \(l+1\) 个值, 则得 \((l+1)^2>n\) 个差数, 故其必有两个数于\(\mod n\) 同余. 设

\[au+bv\equiv au^\prime+bv^\prime\pmod n,\]

\[n\bigm|(ax+by),\]

这里 \(x=u-u^\prime,y=v-v^\prime\), 满足 \( |x|,|y|\leqslant l\). 于是, 更有

\[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,n)=1\), 所以 \(n\bigm|(x^2+y^2)\). 注意到 \(0<x^2+y^2<2n,\) 就得出了 \(n=x^2+y^2.\)

从二平方和定理来看, 本定理是显然的, 但我们没有这样做, 完全避开了它.

 

现在, Hilbert符号(Hilbert symbol)可以登堂了.

Aug 182012
 

质数 \(p=4n+1\), 那么存在 \( a,b\in\Bbb Z,\) 并且

\begin{equation}a\equiv\frac12{2n\choose n}\pmod p,\end{equation}

使得 \( p=a^2+b^2.\)

这是 Gauss 在 \(1825\) 年的一个结果, 已经指出了适合 Fermat 平方和定理的唯一一对 \(a,b\): 由

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

可决定唯一的一个 \(a,\) 然后

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

定出的唯一的 \(b,\) 此 \(a,b\) 使得  \( p=a^2+b^2.\)

据说他本人给出的证明有 \(28\) 页之多. 我争取在这里给出一个简单的证明.

Aug 182012
 

Zagier 的一句话证明(1990)

有限集 \(S=\{(x,y,z)\in\Bbb N^3|x^2+4yz=p\}\) 上的对合(Involution)

\[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)\]

必有不动点 \((x,y,z)\), 它满足 \(y=z\), 进而

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

Aug 052012
 

\(n\in\Bbb N^+\), then

\begin{equation}\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}\end{equation}

这里 \(i\) 跑遍 \(n\) 的缩系.

这是 Gauss 在 DA.\(78\) 给出的 Wilson 定理(Wilson’s theorem) 的推广.

\(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}\), 这里
\begin{equation}\delta=\begin{cases}0,\quad e=0,1,\\1,\quad e=2,\\2, \quad e\geqslant3.\end{cases}\end{equation}

引理的证明, 请参考华罗庚的数论导引, 定理3.5.1, 2.8.1 得出全部.

假定 \( x^2\equiv1\pmod n\) 有 \(2l\) 个解. 若 \((i,n)=1\), 且 \(i\) 不是 \( x^2\equiv1\pmod n\) 的解, 此时必有 \(i^\prime\neq i\) 使得 \( ii^\prime\equiv1\pmod n\), 并且不同的 \(i\) 对应于不同的 \(i^\prime\), 于是可将 \( i,i^\prime\) 配对, 所有这样的 \(i\) 的积 \(\prod\limits i\equiv1\pmod n\); 如果 \( i^2\equiv1\pmod n\), 可以将 \( i,-i\) 配对, \( i(-i)=-i^2\equiv-1\pmod n\).  \( i,-i\) 这样的配对一共有 \(l\) 对, 因之

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

当 \(l\) 为奇数, \(k+\delta=1\), 即 \(n=2,4,p^\alpha,2p^\alpha\) 时, \(\prod\limits_{(i,n)=1}i\equiv-1\pmod n\); 余下的 \(n\) 将使得 \(k+\delta\geqslant2\), \(l\) 为偶数, 从而 \(\prod\limits_{(i,n)=1}i\equiv1\pmod n\).

Wilson 定理的组合证明

来自 \(1930\) 年代的一本俄文杂志, 作者是 A. B. (Moscow)

考虑一个圆周上的 \(p\) 等分点. 依次连结这 \(p\) 个点, 得到一个正 \(p\) 边形, 随便旋转多少个 \(\frac{360^\circ}p\) 所得到的图形都和原来重合. 同理, 连结第 \(1, 1+k, 1+2k,\dotsc\) 也得到一个星形的广义正 \(p\) 边形, 它们同样满足类似的旋转对称性质. 由于跳过 \(k\) 个点和跳过 \(p-k-2\) 个点是一回事, 因此这种类型的多边形一共有\(\frac{p-1}2\) 个.

除了这种旋转对称的“广义正 \(p\) 边形”以外, 其它的多边形随便旋转多少都不能和原来重合. 假设有图形最少只需要旋转  \(d\) 个点的位置(\(d>1\)) 之后就与原图形重合, 那么 \(p\) 一定是 \(d\) 的倍数.

另一方面, 连接圆周上的各点所能形成的多边形总数为 \(\frac{p!}2\). 这是因为规定了起始点后,多边形就由剩下的  \(p-1\) 个点的排列确定, 但每个多边形都各算了两次(顺时针,逆时针遍历各一次). 如前所说,广义的正 \(p\) 边形有  \(\frac{p-1}2\) 个.  故而, 非旋转对称的多边形总数

\[\frac{(p-1)!}2 -\frac{p-1}2 =\frac12 ((p-1)! + 1 – p)\]

被 \(\frac{p-1}2\) 整除当且仅当 \((p-1)! + 1\) 能被 \(p\)  整除.

Jul 302012
 

薪尽火传     “算术研究”中文版出版

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

Disquisitiones Aritmeticae

Disquisitiones Aritmeticae

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

这本书是 Gauss 于1801 年夏天出版, 全书用拉丁文(Latin)写成, 并且是最晚的使用学院拉丁文(scholarly Latin)写就的数学著作之一. 全书分为七个部分 \(335\) 篇, 始于同余理论, 探讨了同余齐次式, 同余方程和二次剩余理论(quadratic residue), 终于分圆多项式和尺规作图.

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

本书的法文译本在1807年出版, 1870年再版, 附有编者评注, 对原著作了少许必要的编辑改动. 1889年德文译本出版. 1959年出版了,参照拉丁文版,从德文译出的俄文译本, 并且1965年再版. 英文版第一版于1966年推出, 第二版的出现是1986年. 现在, 中文版的面世, 可算填补了一项空缺.

本书在引用的时候, 一般简写为 “DA”.

为了人类智慧的火种得以发扬光大, 燃烧生命亦在所不惜.

书名: 算术探索
ISBN: 978-7-5603-3409-7
出版社: 哈尔滨工业大学出版社
作者: (德)高斯
译者: 潘承彪 张明尧 沈永欢
出版日期: 2012年07月01日
定价: 158 人民币元