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 162012
 

奇质数 \(p\) 能表成两个正整数的平方和, 当且仅当 \(p\equiv1\pmod4.\)

Fermat 的这个平方和定理, 非常简洁, 相当漂亮! 这是我见过最多证明的定理, 比质数无限性的证明都多!

先看一看以 Minkowski定理(Minkowski’s theorem)为工具, 来给出Fermat定理的证明.

这个证明, 是 \(20\) 世纪才发现的. 我们从 Minkowski 的一个结果开始, 尽管看起来似乎和Fermat的平方和定理没有关系.

定理(Minkowski)  \(a,b,c\in\Bbb Z, a>0,ac-b^2=1,\) 那么方程 \(ax^2+2bxy+cy^2=1\) 有整数解.

   这定理其实仅是华罗庚的数论导引定理\(20.1.4\) 的特殊情况, 这里的证明似乎更直接.

取平面直角坐标系, 并在这个坐标系上用下列公式给出数量积:

\[((x,y),(x^\prime,y^\prime))=axx^\prime+bxy^\prime+bx^\prime y+cyy^\prime.\]

此数量积产生一个坐标原点到点 \((x,y)\) 的”距离”:

\[d((0,0),(x,y))=\sqrt{((x,y),(x,y))}=\sqrt{ax^2+2bxy+cy^2}.\]

我们来求从原点到格点网络 \((m,n)(m,n\in\Bbb Z)\) 上不同于点 \((0,0)\) 的任一点的最短距离. 设这个距离是 \(\hat d\), 并且它在点 \((\hat m,\hat n)\) 达到, 使得

\begin{equation}a{\hat m}^2+2b\hat m\hat n+c{\hat n}^2={\hat d}^2.\end{equation}

满足

\begin{equation}ax^2+2bxy+cy^2\leqslant {\hat d}^2\end{equation}

的平面点集 \((x,y)\) 是椭圆. 如果这个椭圆在位似变换上被压缩一半, 然后把这个”被压缩了的”椭圆中心平移到格点网络的点上, 那么所有得出的椭圆若相交, 就只相交在边界点上.

Minkowski's theorem

Minkowski’s theorem

容易看出, 平移后的所有椭圆与顶点为 \((0,0),(1,0),(1,1)\) 的三角形公共部分所占面积等于椭圆 \((2)\) 压缩后得到的椭圆面积

\[\frac{\pi{\hat{d}}^2}4\begin{vmatrix}a & b\\b& c\end{vmatrix}=\frac{\pi{\hat{d}}^2}4(ac-b^2)=\frac{\pi{\hat{d}}^2}4\]

的一半, 是 \(\frac{\pi{\hat d}^2}8,\) 这仅是三角形面积 \(\frac12\) 的一部分, 于是

\[\frac{\pi{\hat d}^2}8<\frac12,\]

故而 \({\hat d}^2<\frac4\pi.\)  因 \({\hat d}^2\) 是整数(\((1)\) 式), 这说明 \({\hat d}^2=1,\) 于是 \(\hat d=1,\) 这完成了证明. \(\Box\)

Minkowski 定理与 Fermat 平方和的联系在哪里?

事实上, 根据 Wilson 定理, 可有

\[((\frac{p-1}2)!)^2+1\equiv0\pmod p.\]

由 Minkowski 定理, 存在 \(m,n\in\Bbb Z\), 使得

\[am^2+2bmn+cn^2=1,\]

这里 \(a=p,b=(\frac{p-1}2)!,c=\frac{b^2+1}a.\) 于是

\[a=a^2m^2+2abmn+(b^2+1)n^2=(am+bn)^2+n^2,\]

此即

\[p=(am+bn)^2+n^2,\]

因为 \(a=p\). 我们的证明得以完成.  \(\Box\)

Aug 032012
 

如果把能表示成两个整数平方和的正整数, 按从小到大排成一列:

\begin{equation}a_0=0,a_1=1,a_2=2,a_3=4,a_4=5,\dotsc.\end{equation}

那么这个数列, 不妨名为二平方和数列, 有什么性质?

先来考察二平方和之间的间隙, 也就是数列 \((1)\) 中, 相邻两项的差的问题. 这个差, 有界还是无界?事实上, 这个差可以任意的大, 即我们有下面的定理:

定理 \(1\) 记 \(d_n=a_{n+1}-a_n(n\geqslant1),\) 则

\begin{equation}\varlimsup_{n\rightarrow\infty}d_n= \infty.\end{equation}

换句话说, 我们可以找到任意多个连续的正整数, 它们都不在 \((1)\) 中.

证明  工具是中国剩余定理(Chinese remainder theorem).

取 \(n\) 个不同的形如 \(4k+3\) 的质数 \(p_1, p_2,\dotsc,p_n.\) 考虑同余方程组

\[ \begin{cases}x+1\equiv p_1\pmod{p_1^2},\\ x+2\equiv p_2\pmod{p_2^2},\\ \cdots\\x+n\equiv p_n\pmod{p_n^2}.\end{cases} \]

这个方程组有解 \(l\). 于是 \(l+i\) 是 \(p_i\), 但不是 \(p_i^2\)  的倍数, 因此 \(l+i\) 的质因数分解式中, \(p_i\) 的指数是 \(1\), 故而 \(l+i\) 不是二平方和 \((i=1,2,\dotsc,n).\)

定义

\[S:=\{a_0,a_1,a_2,a_3,\dotsc\}.\]

\(S\) 的密率是 \(0\). 事实上, 我们有精确得多的结果.

定理 \(2\)  用 \(A(n)\) 表示 \((1)\) 中不大于 \(n\) 的正整数个数, 则

\begin{equation}\lim_{n\rightarrow\infty}\frac{A(n)\sqrt{\log n}}n=1.\end{equation}

记 \(\Pi_1\) 是所有形如 \(\equiv1\pmod4\) 的质数组成的集合, \(\Pi_3\) 是所有符合 \(\equiv3\pmod4\)的质数组成的集合.

\begin{equation}L_{1}(s)=\sum_{n\,\text{odd}}(-1)^\frac{n-1}2 n^{-s}=\prod_{p\in\Pi_1}\dfrac{1}{1-p^{-s}}\prod_{p\in\Pi_3}\dfrac1{1+p^{-s}}.\end{equation}

\begin{equation}L_{0}(s)=\sum_{n\,\text{odd}}n^{-s}=\prod_{p\in\Pi_1}\dfrac1{1-p^{-s}}\prod_{p\in\Pi_3}\dfrac1{1-p^{-s}}=(1-2^{-s})\zeta(s),\end{equation}

这里 \(\zeta\) 是 Riemann Zeta 函数.

分别在 \((4),(5)\) 两端取对数, 并利用 Taylor 级数, 可得

\begin{equation}\log L_0+\log L_1=2\sum_{p\in\Pi_1}p^{-s}+O(1),\end{equation}

\begin{equation}\log L_0-\log L_1=2\sum_{p\in\Pi_3}p^{-s}+O(1).\end{equation}

\(L_1\) 是交换级数, 因而收敛, 有界, 并且当 \(s\geqslant1\) 时, 其上下界与 \(s\) 无关. 于是

\begin{equation}\sum_{p\in\Pi_1}p^{-s}=\frac12\log\left[(1-2^{-s})\zeta (s)\right]+O(1),\end{equation}

\begin{equation}\sum_{p\in\Pi_3}p^{-s}=\frac12\log\left[(1-2^{-s})\zeta (s)\right]+O(1).\end{equation}

据 \((6),(7),(8),(9)\), 得

\begin{equation}\prod_{p\in\Pi_1}\frac1{1-p^{-s}}=\sqrt{(1-2^{-s})\zeta (s)}(1+O(1)),\end{equation}

\begin{equation}\prod_{p\in\Pi_3}\frac1{1-p^{-s}}=\sqrt{(1-2^{-s})\zeta (s)}(1+O(1)).\end{equation}

据二平方和定理, 得

\begin{equation}\sum_{n=1}^\infty a_n^{-s}=\frac1{1-2^{-s}}\prod_{p\in\Pi_1}\frac1{1-p^{-s}}\prod_{p\in\Pi_3}\frac1{1-p^{-2s}}=\sqrt{\zeta (s)\zeta (2s)}(1+O(1)).\end{equation}

当 \(s\rightarrow1\) 时, \(\zeta(2s)\) 的主部是常数, 因此 \(s\rightarrow1^+\) 时,

\begin{equation}\sum_{n=1}^\infty a_n^{-s}=\sqrt{\zeta(s)}(1+O(1)).\end{equation}

我们又有

\begin{equation}\sum_{n=1}^\infty a_{n}^{-s}=\sum_{n=1}^\infty\chi(n)n^{-s},\end{equation}

这里

\begin{equation}\chi(n)=\begin{cases}\,1,\quad\,n\in S\\0,\quad \text{otherwise}\end{cases}\end{equation}

定义

\[A(x)=\sum_{n\leqslant x}\chi(n),\]

利用 abel 求和公式, 得

\begin{equation}\sqrt{\zeta (s)}+O(1)=s\int_{0}^\infty A(x)x^{-(s+1)}dx.\end{equation}

令 \(s\rightarrow1^+\), 有

\begin{equation}\frac1{\sqrt{s-1}}+O(1)=\int_{0}^\infty A(x)x^{-(s+1)}dx.\end{equation}

最后, 由 Perron 公式或者 Laplace 变换, 即得

\begin{equation}A(x)\sim\frac{x}{\sqrt{\log x}}.\end{equation}

定理 \(2\) 不容易, 据此, 马上得以定出 \(a_n\) 的阶.

定理 \(3\)  \(\lim\limits_{n\rightarrow\infty}\dfrac{a_n}{n\sqrt{\log n}}=1.\)

下面这件事情是显然的, 尽管也是定理 \(3\) 的推论.

定理 \(4\)  \(\lim\limits_{n\rightarrow\infty}\frac{a_{n+1}}{a_n}=1.\)

定理 \(4\) 的一个推论是:

定理 \(5\)  集合

\[\{\frac{s_1}{s_2}|s_1,s_2\in \Bbb S\}\]

在非负实数集 \(\Bbb R_+\) 中稠密.

事实上, 若定义 \(g(x), h(x)(x\in\Bbb R_+)\) 为

\[g(x)=a_n, h(x)=a_{n+1}(a_n\leqslant x<a_{n+1},n=0,1,2,\dotsc.),\]

则对任意 \(p, q\in\Bbb N^+\), 成立

\[\dfrac{\dfrac{g(np)}{h(nq)}}{\dfrac{h(np)}{g(nq)}}<\dfrac{\dfrac{g(np)}{g(nq)}}{\dfrac pq}<\dfrac{\dfrac{h(np)}{g(nq)}}{\dfrac{g(np)}{h(nq)}},\]

这是因为 \(\dfrac{g(np)}{h(nq)}<\dfrac{g(np)}{g(nq)}, \dfrac pq<\dfrac{h(np)}{g(nq)}\). 这便推出

\[\lim_{n\rightarrow\infty}\frac{g(np)}{g(nq)}=\frac pq.\]

注意, 这个证明并没有用到 \(S\) 的性质, 也就是说, 满足定理 \(4\) 的数列必定对定理 \(5\) 也成立.

定理 \(6\)  级数

\begin{equation}\sum_{n=1}^\infty\frac1{a_n}\end{equation}

发散.

实际上, 根据 Fermat 的平方和定理, 质数 \(p\equiv1\pmod4\) 都在数列 \((1)\) 中. 所以, 欲证明的结果仅仅是 Dirichlet 的一个经典定理

\[\sum_{p\equiv b\pmod a\atop (a,b)=1}\frac 1p=\infty\]

的特列.

定理 \(7\)  数列 \((1)\) 包含任意长的算术级数.

Jun 272012
 

theorem   Let \(n\) be a positive integer,  then \(n\) can be expressed as the sum of three squares iff it is not of  the  form

\begin{equation}4^a(8b+7)\end{equation}

for some \( a,b\in\Bbb Z,a,b\geq 0\).

For a integer \(n\equiv3\pmod8\), there exists three odd numbers \(x,y,z\) such that

\begin{equation}n=x^2+y^2+z^2.\end{equation}

Jun 232012
 

二平方和

引理 \(1\)正整数 \(a, b\) 互质, \((a,b)=1, p>2\) 是质数,并且 \(p\bigm|(a^2+b^2)\), 则 \(p\equiv1\pmod4\).

证明  不难用二次剩余(Quadratic residue)来给出证明:

由 \(p\bigm|(a^2+b^2)\) 得

\begin{equation}a^2\equiv-b^2\pmod p,\end{equation}

故而

\begin{equation}(\frac{a^2}{p})= (\frac{-1}{p})(\frac{b^2}{p}).\end{equation}

这里 \((\frac{n}{p})\) 是 Legendre symbol. 由于  \((a,b)=1\), 因之 \((p,a)=(p,b)=1\), 于是

\begin{equation}(\frac{a^2}{p})=(\frac{b^2}{p})=1\end{equation}

成为事实, 所以必定有

\begin{equation}(\frac{-1}{p})=1.\end{equation}

换句话说, 我们已经得到了所要的 \(p\equiv1\pmod4\).

 

下面换一个办法, 可能是最简单的, 工具是 Fermat 小定理(Fermat’s little theorem

用反证法.

假定有正整数 \(k\) 使得 \(p=4k-1\), 由 \((1)\)  可得

\[(a^2)^{2k-1}\equiv(-b^2)^{2k-1}\pmod p,\]

这也就是

\[a^{p-1}\equiv-b^{p-1}\pmod p.\]

但这是不可能的!

这里的处理方式, 也可以稍作变更:

\(p\bigm|(a^2+b^2)\), 注意到 \((a^2+b^2)\bigm|(a^{p-1}+b^{p-1})\)(因为 \(p-1=2(2k-1)\)), 于是

\[p\bigm|(a^{p-1}+b^{p-1}).\]

一样是不可能的.

 

引理 \(1\) 虽然简单, 但是隐含了下面的事实:

引理 \(2\)    质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|(a^2+b^2)\), 这里 \(a,b\) 是整数, 则 \(p\bigm|a,  p\bigm|b.\)

照样可以使用二次剩余来得到欲证的结果: 同样由 \((1)\), 我们又得出 \((2)\)! 注意 \( (\frac{-1}{p})=-1\), 所以

\begin{equation}(\frac{a^2}{p})= -(\frac{b^2}{p}).\end{equation}

这又迫使下面的等式成为事实:

\begin{equation}(\frac{a^2}{p})= (\frac{b^2}{p})=0.\end{equation}

这也就是 \(p\bigm|a,  p\bigm|b.\)

 

下面直接借用引理 \(1\) 来完成引理 \(2\) 的证明. 事实上, 记 \(d=(a,b)\)为 \(a,b\) 的最大公约数, 则有整数 \(a_1,b_1\) 使得 \(a=a_1d, b=b_1d\), 并且 \((a_1,b_1)=1\). 于是

\begin{equation}a^2+b^2=d^2(a_1^2+b_1^2). \end{equation}

由 \(p\bigm|(a^2+b^2)\), 得

\begin{equation}p\bigm|d^2(a_1^2+b_1^2).\end{equation}

根据引理 \(1\), 可以知道

\begin{equation}(p,a_1^2+b_1^2)=1,\end{equation}

于是

\begin{equation}p\bigm|d^2,\end{equation}

从而

\begin{equation}p\bigm|d.\end{equation}

我们得到了需要的 \(p\bigm|a,  p\bigm|b.\)

 

现在, 假定 \(n\) 是正整数, 并且有整数 \(a,b\), 使得 \(n=a^2+b^2\). 质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|n\).  根据 \((7), (9), (10),\) \(n\) 的质因数分解式中的 \(p\) 全部出现在 \(d^2\) 的质因数分解式中,因此 \(n\) 的质因数分解式中 \(p\) 的指数等于 \(d^2\) 的质因数分解式中 \(p\) 的指数,是 \(d\) 的质因数分解式中 \(p\)  的指数的 \(2\) 倍, 当然是偶数, 故而有了引理 \(3\):

引理 \(3\)   正整数 \(n\) 是二平方和, 即有整数 \(a,b\), 使得 \(n=a^2+b^2\). 质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|n\), 则 \(n\) 的质因数分解式中, \(p\) 的指数是偶数.

 

至此, 我们也就得出了下述的二平方和定理

正整数 \(n\)  能写成两个整数的平方和的充分必要条件是, 所有 \(n\) 的质因数分解式中形如 \(4k-1\) (\(k\) 为正整数)的质数的指数皆为偶数.

 

利用 \(\Bbb Z[i]\) 的唯一分解定理, 也可以证明引理 \(3\):

事实上, 假定 \(n\) 是正整数, 并且有 \(a,b\in\Bbb Z\), 使得 \(n=a^2+b^2\), 则

\begin{equation}n=(a+bi)(a-bi).\end{equation}

假定 \(a+bi\) 在 \(\Bbb Z[i]\) 中有分解式

\begin{equation}a+bi=(a_1+b_1i)(a_2+b_2i)\cdots(a_l+b_li),\end{equation}

\begin{equation}a-bi=(a_1-b_1i)(a_2-b_2i)\cdots(a_l-b_li),\end{equation}

于是

\begin{equation}n=(a_1^2+b_1^2)(a_2^2+b_2^2)\cdots(a_l^2+b_l^2).\end{equation}

若有 \(b_k=0(1\leq k \leq l)\), 则 \(a_k^2\) 即为\(\Bbb Z\) 中的平方数; 如果 \(b_k\neq0(1\leq k \leq l)\), 则 \(a_k^2+b_k^2\) 就是\(\Bbb Z\) 中的质数: 这是因为, 假若不是如此, 则有 \(\neq\pm1\) 的整数 \(s, t\) 使得 \(a_k^2+b_k^2=st\). 将 \(s, t\) 在 \(\Bbb Z[i]\) 中分解, 就得到了一种不同于 \((a_k+b_ki)(a_k-b_ki)\) 的, 是两个有理整数或三个以上质因数的积的分解式. 这与 \(\Bbb Z[i]\) 的唯一分解定理是矛盾的.

既然 \(a_k^2+b_k^2\) 是\(\Bbb Z\) 中的质数, 那么 \(a_k^2+b_k^2\) 要么是 \(2\), 要么 \(\equiv1\pmod4\), 肯定不是 \(p\). 至此已经知道, 在\(n\) 的质因数分解式中, \(p\) 的指数是偶数.