若复数α和β满足α+β与αβ是互素的非零整数, 并且α/β不是单位根, 则数列(α^n-β^n)/(α-β)的每一项都是整数, 这个数列叫作Lucas数列
Lucas研究了这类数列的整除性质, 并且称在α和β为整数时, 可以证明对每个足够大的n, (α^n-β^n)/(α-β)都有一个与此前每一项都互素的素因子(可以称为本原因子primitive divisor或特征因子characteristic factor). 以下是后来被发现的一些有关结论
(1) α和β为整数的情况 (Zsigmondy定理)
A.S.Bang(1886)在论文Taltheoretiske undersøgelser中讨论了β=1, α为大于1的正整数a时的情况
(https://www.jstor.org/stable/24539988)
K.Zsigmondy(1892)在论文Zur Theorie der Potenzreste中证明了当α=a和β=b是整数时的一般情况
(https://zenodo.org/records/2131326)
G.D.Birkhoff & H.S.Vandiver(1904)在论文On the Integral Divisors of 𝑎^𝑛−𝑏^𝑛 中也独立给出了一部分相同的结果(定理V)
(https://www.jstor.org/stable/2007263)
Zsigmondy定理 (Bang-Zsigmondy-Birkhoff &Vandiver定理) 可以总结为:
若正整数a>b且a,b互素, 则对任意正整数n>1, (a,b为正的要求可以推广)
(i) 除了以下两类例外情况以外, a^n-b^n总存在本原素因子p, 使得对任意正整数k<n, p与a^k-b^k都互素. 其中一种例外是(a,b,n)=(2,1,6), 另一种是n=2且a+b是2的幂
(ii) 除了(a,b,n)=(2,1,3)的例外情况以外, a^n+b^n总存在本原素因子p, 使得对任意正整数k<n, p与a^k+b^k都互素. 例外是
|m|>1时用P(m)表示整数m的(绝对值)的最大素因子, 令P(1)=P(0)=P(-1)=1.定理的一个推论是对正整数a>b, n>2, P(a^n-b^n)>=n+1.
(2) α和β不为整数时Carmichael的推广
R.D.Carmichael(1912)在论文On the Numerical Factors of the Arithmetic Forms α^n ± β^n中对实数α和β构成的Lucas数列Dn= (α^n-β^n)/(α-β)以及Sn = α^n+β^n 证明了类似的结论(定理XXIII, XXIV)
(https://www.jstor.org/stable/1967797 以及 https://www.jstor.org/stable/1967798)
定理: 若绝对值不相等的实数α和β满足α+β与αβ是互素的非零整数
(i) 除了(α+β, αβ, n) = (1,-1,12)的例外情况以外, 当正整数n≠1,2,6时, Dn=(α^n-β^n)/(α-β)总存在特征素因子p, 使得对任意正整数k<n, p与Dk=(α^k-β^k)/(α-β)互素, 并且与(α-β)^2互素
(ii) 除了(α+β, αβ, n) = (1,-1,6)的例外情况以外, 当正整数n≠1,3时, Sn=α^n+β^n总存在特征素因子p, 使得对任意正整数k<n, p与Sk=α^k+β^k互素, 并且与(α-β)^2互素
这类特征素因子总满足n | p+1 或 n | p-1, 论文中提到有关kn+-1型素数存在性的一些结论, 并且由此可以推出, 除了特例以外, 对任意正整数n≠1,2,6, P((α^n-β^n)/(α-β))>=n-1 总成立.
(3) Lehmer数列
D.H.Lehmer指出若复数α和β满足(α+β)^2与αβ是互素的非零整数, 并且α/β不是单位根, 对正奇数n, Pn=(α^n-β^n)/(α-β)总是整数, 对正偶数n, Pn=(α^n-β^n)/(α^2-β^2)总是整数. 这样的整数Pn组成的数列称为Lehmer数列
M.Ward(1955)在论文The Intrinsic Divisors of Lehmer Numbers中得到的结论是:
(https://www.jstor.org/stable/1969677)
由实数α和β确定的Lehmer数列中, 除了以下几组例外, 对任意正整数n>2, Pn总存在素因子p, 使得对任意正整数k<n, p与Pk都互素. 例外是((α+β)^2,αβ,n) = (1,-1,6),(1,-1,12),(1,-1,18),(5,1,6),(5,1,12),(5,1,18),(9,2,6).
L.K.Durst(1959)在论文Exceptional real Lehmer sequences中指出Ward的分析过程有误, 并且证明n=6的例外会出现在无穷多个Lehmer数列中, n=12的例外仅有((α+β)^2,αβ,n)=(1,-1,12),(5,1,12), 除此以外其它指数n>2且n≠6不会出现例外.
(https://msp.org/pjm/1959/9-2/pjm-v9-n2-p08-s.pdf)
由此可以推出, 对于实数α和β对应的Lehmer数列Pn, 当n≠1,2,6时除了几组例外总有P(Pn)>=n-1
(4) α和β为复数的一般情况
A.Schinzel进一步研究了复数的α和β确定的Lucas数列与Lehmer数列, 证明存在由α和β决定的正实数C, 使得当n>C时对应的数列第n项总存在本原素因子. 随后Schinzel(1974)又证明C可以替换为一个与α和β无关的常数C0.
此后C.L.Stewart证明除了有限多个例外, C0对Lucas数列可以取6, 对Lehmer数列可以取12. 这些例外是由有限多组方程确定的. Y.Bilu, G.Hanrot &P.M.Voutier处理了这些反例, 证明对所有的Lucas数列与Lehmer数列, C0可以取到30.
(5) 关于P(a^n-b^n)
只使用分圆多项式的方法可以证明对正整数a>b,n>=2,都有P(a^n-b^n)>=n+1 (Zsigmondy定理), 在abc猜想和广义RH成立的前提下对此的估计可以进一步改进.
不基于任何前提的改进最早是由Schinzel(1962)在论文On primitive prime factors of a^n−b^n中证明的以下结论:
若a,b是不相等的互素整数, 存在非零整数c使得ab=c^2或2c^2, 则除了(a,b,n)=(2,1,4),(2,1,6),(2,1,12)这几组例外, 对任意正整数n>2, 都有P(a^n-b^n)>=2n+1
Schinzel证明了对于满足要求的a,b, 除了一些例外a^n-b^n总有至少2个本原素因子. 并且问是否存在|ab|=2c^2或c^h,h>=2以外的其它情况使P(a^n-b^n)>=2n+1对所有足够大的正整数n都成立. Erdos(1965)也猜想过当n趋于无穷时P(2^n-1)/n也趋于无穷.
Stewart(2013)在论文On divisors of Lucas and Lehmer numbers中证明了以上两个猜想都是成立的, 结论如下:
(https://arxiv.org/abs/1008.1274)
若复数α和β满足(α+β)^2与αβ都是非零整数且α/β不是单位根, 则存在一个仅由αβ不同素因子个数以及disc(α/β)的正数C, 使得对任意正整数n>C, P(phi_n(α,β))>n*exp(logn / 104loglogn) 都成立, 其中phi_n是二元的分圆多项式
特别地, 对任意正整数a>b, P(a^n-b^n)>n*exp(logn / 104loglogn) 对任意n>N成立, 其中N是一个只依赖于ab的不同素因子个数的正数.
Lucas研究了这类数列的整除性质, 并且称在α和β为整数时, 可以证明对每个足够大的n, (α^n-β^n)/(α-β)都有一个与此前每一项都互素的素因子(可以称为本原因子primitive divisor或特征因子characteristic factor). 以下是后来被发现的一些有关结论
(1) α和β为整数的情况 (Zsigmondy定理)
A.S.Bang(1886)在论文Taltheoretiske undersøgelser中讨论了β=1, α为大于1的正整数a时的情况
(https://www.jstor.org/stable/24539988)
K.Zsigmondy(1892)在论文Zur Theorie der Potenzreste中证明了当α=a和β=b是整数时的一般情况
(https://zenodo.org/records/2131326)
G.D.Birkhoff & H.S.Vandiver(1904)在论文On the Integral Divisors of 𝑎^𝑛−𝑏^𝑛 中也独立给出了一部分相同的结果(定理V)
(https://www.jstor.org/stable/2007263)
Zsigmondy定理 (Bang-Zsigmondy-Birkhoff &Vandiver定理) 可以总结为:
若正整数a>b且a,b互素, 则对任意正整数n>1, (a,b为正的要求可以推广)
(i) 除了以下两类例外情况以外, a^n-b^n总存在本原素因子p, 使得对任意正整数k<n, p与a^k-b^k都互素. 其中一种例外是(a,b,n)=(2,1,6), 另一种是n=2且a+b是2的幂
(ii) 除了(a,b,n)=(2,1,3)的例外情况以外, a^n+b^n总存在本原素因子p, 使得对任意正整数k<n, p与a^k+b^k都互素. 例外是
|m|>1时用P(m)表示整数m的(绝对值)的最大素因子, 令P(1)=P(0)=P(-1)=1.定理的一个推论是对正整数a>b, n>2, P(a^n-b^n)>=n+1.
(2) α和β不为整数时Carmichael的推广
R.D.Carmichael(1912)在论文On the Numerical Factors of the Arithmetic Forms α^n ± β^n中对实数α和β构成的Lucas数列Dn= (α^n-β^n)/(α-β)以及Sn = α^n+β^n 证明了类似的结论(定理XXIII, XXIV)
(https://www.jstor.org/stable/1967797 以及 https://www.jstor.org/stable/1967798)
定理: 若绝对值不相等的实数α和β满足α+β与αβ是互素的非零整数
(i) 除了(α+β, αβ, n) = (1,-1,12)的例外情况以外, 当正整数n≠1,2,6时, Dn=(α^n-β^n)/(α-β)总存在特征素因子p, 使得对任意正整数k<n, p与Dk=(α^k-β^k)/(α-β)互素, 并且与(α-β)^2互素
(ii) 除了(α+β, αβ, n) = (1,-1,6)的例外情况以外, 当正整数n≠1,3时, Sn=α^n+β^n总存在特征素因子p, 使得对任意正整数k<n, p与Sk=α^k+β^k互素, 并且与(α-β)^2互素
这类特征素因子总满足n | p+1 或 n | p-1, 论文中提到有关kn+-1型素数存在性的一些结论, 并且由此可以推出, 除了特例以外, 对任意正整数n≠1,2,6, P((α^n-β^n)/(α-β))>=n-1 总成立.
(3) Lehmer数列
D.H.Lehmer指出若复数α和β满足(α+β)^2与αβ是互素的非零整数, 并且α/β不是单位根, 对正奇数n, Pn=(α^n-β^n)/(α-β)总是整数, 对正偶数n, Pn=(α^n-β^n)/(α^2-β^2)总是整数. 这样的整数Pn组成的数列称为Lehmer数列
M.Ward(1955)在论文The Intrinsic Divisors of Lehmer Numbers中得到的结论是:
(https://www.jstor.org/stable/1969677)
由实数α和β确定的Lehmer数列中, 除了以下几组例外, 对任意正整数n>2, Pn总存在素因子p, 使得对任意正整数k<n, p与Pk都互素. 例外是((α+β)^2,αβ,n) = (1,-1,6),(1,-1,12),(1,-1,18),(5,1,6),(5,1,12),(5,1,18),(9,2,6).
L.K.Durst(1959)在论文Exceptional real Lehmer sequences中指出Ward的分析过程有误, 并且证明n=6的例外会出现在无穷多个Lehmer数列中, n=12的例外仅有((α+β)^2,αβ,n)=(1,-1,12),(5,1,12), 除此以外其它指数n>2且n≠6不会出现例外.
(https://msp.org/pjm/1959/9-2/pjm-v9-n2-p08-s.pdf)
由此可以推出, 对于实数α和β对应的Lehmer数列Pn, 当n≠1,2,6时除了几组例外总有P(Pn)>=n-1
(4) α和β为复数的一般情况
A.Schinzel进一步研究了复数的α和β确定的Lucas数列与Lehmer数列, 证明存在由α和β决定的正实数C, 使得当n>C时对应的数列第n项总存在本原素因子. 随后Schinzel(1974)又证明C可以替换为一个与α和β无关的常数C0.
此后C.L.Stewart证明除了有限多个例外, C0对Lucas数列可以取6, 对Lehmer数列可以取12. 这些例外是由有限多组方程确定的. Y.Bilu, G.Hanrot &P.M.Voutier处理了这些反例, 证明对所有的Lucas数列与Lehmer数列, C0可以取到30.
(5) 关于P(a^n-b^n)
只使用分圆多项式的方法可以证明对正整数a>b,n>=2,都有P(a^n-b^n)>=n+1 (Zsigmondy定理), 在abc猜想和广义RH成立的前提下对此的估计可以进一步改进.
不基于任何前提的改进最早是由Schinzel(1962)在论文On primitive prime factors of a^n−b^n中证明的以下结论:
若a,b是不相等的互素整数, 存在非零整数c使得ab=c^2或2c^2, 则除了(a,b,n)=(2,1,4),(2,1,6),(2,1,12)这几组例外, 对任意正整数n>2, 都有P(a^n-b^n)>=2n+1
Schinzel证明了对于满足要求的a,b, 除了一些例外a^n-b^n总有至少2个本原素因子. 并且问是否存在|ab|=2c^2或c^h,h>=2以外的其它情况使P(a^n-b^n)>=2n+1对所有足够大的正整数n都成立. Erdos(1965)也猜想过当n趋于无穷时P(2^n-1)/n也趋于无穷.
Stewart(2013)在论文On divisors of Lucas and Lehmer numbers中证明了以上两个猜想都是成立的, 结论如下:
(https://arxiv.org/abs/1008.1274)
若复数α和β满足(α+β)^2与αβ都是非零整数且α/β不是单位根, 则存在一个仅由αβ不同素因子个数以及disc(α/β)的正数C, 使得对任意正整数n>C, P(phi_n(α,β))>n*exp(logn / 104loglogn) 都成立, 其中phi_n是二元的分圆多项式
特别地, 对任意正整数a>b, P(a^n-b^n)>n*exp(logn / 104loglogn) 对任意n>N成立, 其中N是一个只依赖于ab的不同素因子个数的正数.
, 只有一个很特殊的情况可以证明出来, 是这样子:
