开篇
Zsigmondy’s theorem states that if \(a>b>0\) and \(n>1\) are positive integers, then
- \(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\);
- 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\) 的初等证明
参考文献
- Geo. D. Birkhoff and H. S. Vandiver, On the Integral Divisors of \(a^n – b^n \), The Annals of Mathematics, \(1904, 173-180\).
- Carmichael, On the Numerical Factors of the Arithmetic Forms \(a^n \pm b^n \), The Annals of Mathematics, \(1913, 30-70\).
- Artin, The orders of the linear groups, Communications on pure and applied mathematics, vol 7, \(1955, 355-366\).