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