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 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 人民币元
Jul 292012
 

\(m\in\Bbb N^+,a\in\Bbb Z,\) 并且 \(( a, m ) = 1\), 则一次同余方程
\[ax\equiv b\pmod m\]
有唯一解 \(\dfrac ba\).

\(\dfrac ba\) 只是一个形式分数, 并不是我们需要的真正答数. 那么, 如何通过这个分数找出真正的解呢?

我没有看到什么书来系统论述这个问题. 单墫在他的大部头著作”数学竞赛研究教程”介绍中国剩余定理的时候, 在一个例题的解答里, 简略的提到了下面的变换 I 与 III. 人民教育出版社的新版普通高中课程标准实验教科书中, 有一本选修数学教材”初等数论初步”, 也谈到了这种办法, 并冠名为形式分数法, 更进一步指出这个办法是基于同余式的恒等变形,并在配套的教师用书给出了证明.

具体来说, 从 \(\dfrac ba\) 这个分数出发, 找出这个真正的解, 可以采取如下三个变换:
I      分子或分母可以加上 \(m\) 的整数倍. 换句话说, 分母或者分子可以换成对模 \(m\) 同余的数;
II     可用用与 \(m\) 互质的数同时乘以分母和分子;
III    可以约分.

在实际应用中, I 和 III 是必须要的, 而且足以把解找出来, 于是下面的第二件事情是成立的:

  1.  手术的合法性;
  2. 一次同余方程的解必定可以通过这三个变换得出.

至于 \(1\) 也比较显然, 就此打住.

\(\dfrac ba\) 是一个形式分数, 实际是一个整数. 把握这一点比较要紧. 下面是一个问题:

\(p\) is a odd prime, then

\[ 2^p-1\equiv (-1)^{\frac{p-1}2}{{p-1}\choose{\frac{p-1}2}}\pmod{p^2}. \]

proof.  Let \(n=\frac{p-1}2\), it is easy to see that

\[ (-1)^n\binom{p-1}n=\prod_{k=1}^n\frac{k-p}{k}\equiv\prod_{k=1}^n(1-\frac pk)\equiv1-p\sum_{k=1}^n\frac1k\pmod{p^2},\]

Remembering  that \(\sum\limits_{k=1}^{p-1}\dfrac1k\equiv0\pmod{p^2}\), we get that

\[\begin{split}2^p-1&=1+\sum_{k=1}^{p-1}\binom pk\equiv1+p\sum_{k=1}^{p-1}\frac{(-1)^{k-1}}k\\
&\equiv1+p\sum_{k\,odd}\frac1k-p\sum_{k\,even}\frac1k\equiv1-2p\sum_{k\,even}\frac1k\\
&\equiv1-p\sum_{k=1}^n\frac1k\pmod{p^2}.  \Box\end{split}\]