开篇

Zsigmondy’s theorem states that if \(a>b>0\) and \(n>1\) are positive integers, then

1. \(a^n+b^n\) has at least one prime factor that does not divide \(a^k+b^k\) for all positive integers \(k<n\), with the exception of \(2^3+1^3\);
2. if \((a,b)=1\), then there is a prime number that divides \(a^n-b^n\) and does not divide \(a^k-b^k\) for all positive integer \(k<n\) unless

•   \(a=2,b=1\) and \(n=6\); or
•   \(a+b\) is a power of \(2\) and \(n=2\).

这就是如今人们常常谈到的 Zsigmondy 定理, \(2\) 实际上更为常见.  Zsigmondy 当初其实允许 \(b<0\), 此时的例外当然要稍作修改, 比如 \(2\) 要增加 \(a=2,b=-1,n=3\).

此定理经常在群论(group theory)中大展拳脚, 在数论中当然也有很多应用.

这个定理的完整证明很难找到, 容易搜索到的是 \(b=1\) 时, 使用分圆多项式(cyclotomic polynomial)对\(2\)的证明.

历史

在 Zsigmondy\(1892\)年的论文出现之前, Bang已经在\(1886\) 年证明了\(b=1\) 的情形, 即所谓的 Bang定理. 至于 Bang 当年的文章,是否包括了 Zsigmondy 定理的两种情形, 我无法得知, 因为没有看到原文. 后来, 又有不少人重新发现 Zsigmondy 定理或者 Bang 的结果, 也可能是某种特殊情况下的结论, 当然也有人给出新的证明. Birkhoff 和 Vandiver \(1904\) 年的论文 \([1]\) 用初等的办法证明了 \(2\). 这个证明, 稍后我们会详细谈到.

Carmichael \(1913\) 年的文章 \([2]\) 很值得一看, 他实际上证明了对 Lucas 序列(Lucas sequence)

\begin{equation}U_n=\frac{a^n-b^n}{a-b},\,V_n=a^n+b^n\end{equation}

而言, 结论一样成立. 尽管 \(a^n-b^n\) 与 \(U_n\) 确有许多相似, 但是毕竟差别还是有的, \(U_n\) 的本原质因数并不见得就是 \(a^n-b^n\) 的本原质因数. 例如, 当 \(a=5,\,b=2,\,n=3\) 时, \(U_3=\frac{5^3-2^3}{5-2}\) 的本原质因数 \(3\) 并不是 \(5^3-2^3\) 的本原质因数.

Artin 在研究线性群(linear group)的时候, 用初等办法建立了Zsigmondy定理的 \(2\), 并且允许 \(a,b\) 可以为负, 见 \([3]\).

准备工作

继续下文之前, 先看几个简单的事实.

引理\(1\) 当 \(a,b\) 互质, 也即 \((a,b)=1\) 之时,

\begin{equation}(a^m-b^m,\,a^n-b^n)=a^{(m,n)}-b^{(m,n)}\end{equation}

成立, 这里 \(m,n\in\Bbb N^+.\)

\((2)\) 虽然简单, 却从未在哪本书上见过. 数论书上只有当 \(b=1\) 时的特殊情形, 所以这里算是一个推广. 至于证明, 可以归纳完成, 也可以选择 Bézout 恒等式(Bézout’s identity), 与 \(b=1\) 没有本质不同.

下面来探讨阶的性质.

设正整数 \(m>1,a\in\Bbb Z,(a,m)=1.\) 记 \(a\) 模 \(m\) 的阶为 \(\delta_m(a).\) 正整数 \(r\) 使得

\begin{equation}a^r\equiv-1\pmod m\end{equation}

成立.

引理\(2\) 设满足 \((3)\) 的最小正整数为 \(r\), 那么

• 若 \(a^n\equiv-1\pmod m, n\in\Bbb N^+\), 则 \(r|n;\)
• \(\delta_m(a)=\begin{cases}\;r,\quad m=2;\\2r, \quad m\geqslant3.\end{cases}\)

引理\(3\)  \(p\) 为质数, \(a,b,n\in\Bbb Z, n>0, p\nmid ab, p^\alpha\parallel n, p^\beta\parallel (a-b), \alpha,\beta\in\Bbb N.\) 如果在 \(p=2\) 时, \(\beta\geqslant2\); 在 \(p\geqslant3\) 时, \(\beta\geqslant1,\) 那么 \(p^{\alpha+\beta}\parallel (a^n-b^n).\)

证 设 \(a=b+tp^\beta, p\nmid t,\) 则

\[a^n-b^n=(b+tp^\beta)^n-b^n=\sum_{i=1}^n{n\choose i}b^{n-i}(tp^\beta)^i.\]

当 \(i\geqslant2\) 时, 由 \({n\choose i}(tp^\beta)^i=\dfrac ni{n-1\choose i-1}(tp^\beta)^i, (p^\beta)^{i-1}\geqslant3^{i-1}>i,\) 可得 \(p^{\alpha+\beta+1}|{n\choose i}b^{n-i}(tp^\beta)^i\); \(p^{\alpha+\beta}\parallel{n\choose1}b^{n-1}(tp^\beta).\) 综合起来, 我们的证明得以完成.

本原因子的定义与性质

若 \(a^n\pm b^n\) 的某质因数不整除 \(a^k\pm b^k(k=1,\,2,\,\dotsc,\,n-1),\) 我们把这样的质因子叫做本原质因数. 也可以考察 \(a^n\pm b^n\) 的不是质数的因数, 这个时候, 要把整除不整除换成互质不互质: 若 \(a^n\pm b^n\) 的某因数与 \(a^k\pm b^k( k=1,\,2,\,\dotsc,\,n-1)\) 都互质, 我们把这样的因数叫做本原因数.

本原因数要求与 \(a^k\pm b^k, k<n\) 都互质, 所有的 \(n-1\) 个数 \(a\pm b, a^2\pm b^2,\dotsc,a^{n-1}\pm b^{n-1}\) 一个不落下. 能否把这个条件换成表面上更弱，实际上等价的条件, 使得利用这个定义的时候, 更加得心应手?

借助阶的性质以及引理 \(2\), 很容易就得到了第一个定理.

定理 \(1\)  记 \(n\) 的 \(d(n)\)个因数是 \(d_1=1,d_2,\dotsc,d_{d(n)}=n\). 如果 \(a^n\pm b^n\) 的一个因数与 \(a^k\pm b^k( k=d_1,d_2,\dotsc,d_{d(n)-1})\) 都互质, 那么这个因数是 \(a^n\pm b^n\) 的本原因数.

引理 \(1\) 也可以很方便的完成就 \(W_n\) 这种情况的证明, 这里

\begin{equation}W_n=a^n-b^n.\end{equation}

下一条性质出自 Euler.

定理\(2\)   \(d\) 是 \(W_n\) 的本原因数, 则 \(d\equiv1\pmod n.\)

\(2\) 的初等证明

参考文献

1. Geo. D. Birkhoff and H. S. Vandiver, On the Integral Divisors of \(a^n – b^n \), The Annals of Mathematics, \(1904, 173-180\).
2. Carmichael, On the Numerical Factors of  the Arithmetic Forms \(a^n \pm b^n \), The Annals of Mathematics, \(1913, 30-70\).
3. Artin, The orders of the linear groups, Communications on pure and applied mathematics, vol 7, \(1955, 355-366\).