Zsigmondy定理：从分圆多项式开始-拓崇最新章节-免费小说-全文免费阅读-拓崇作品-话本小说网

Zsigmondy定理 . α＞b≥1为互素的正整数，对n≥2，存在素数p整除αⁿ−bⁿ，但p∤αᵏ−bᵏ，1≤k＜n . 除去以下情况均成立：

( 1 ) n＝2，α＋b为2的方幂

( 2 ) n＝6，α＝2，b＝1

PART0 . 约定

记号 . ord(α)为满足αᵏ＝1的最小正整数k； δₚ(α)为满足αᵏ≡1(mod p)的最小正整数k；υₚ(α)为α的标准分解式中素数p的次数；φ(n)为欧拉函数; μ(n)为Mobius函数 .

此处我们不加证明地给出几个引理 .

LTE引理 . p为素数，x，y∈Z，m≥1，满足x≡y≢0(mod p) .

( 1 ) 若p≥3，则

υₚ(xᵐ−yᵐ)＝υₚ(x−y)＋υₚ(m)

( 2 ) 若p＝2，则

υ₂(xᵐ−yᵐ) m

{υ₂(x²−y²)＋υₚ(─)2∣m

＝ n

{υ₂(x−y) 2 ∤ m

引理1 . f(x)，g(x)∈𝔽[x]，f(x)为不可约多项式，𝔽¯⊃𝔽 为扩域，则有

( 1 ) f(x)，g(x)在𝔽¯上有公共根 ⟺f(x)∣g(x)

( 2 ) f(x)，g(x)在F¯上无公共根 ⟺(f(x)，g(x))＝1

PART1 . 分圆多项式及其部分性质

2πi

定义1 . ε＝e ──为n次单位根，分圆多项式

Φₙ(x)＝∏ (x−εᵏ)＝φ(n)

1≤k≤n(k，n)＝1 ∏(x−εₖ)

k＝1

其中εₖ＝εᵏ(k，n)＝1为n次本原单位根 .

等价定义1 . 1 xⁿ−1＝∏d∣ₙ Φd(x)

证明：

ₙ

xⁿ−1＝∏ (x−εᵏ)

k＝1

=∏ ∏ (x−εᵏ) n

d∣n (k，n)＝─)=)

＝∏ Φd(x)

d∣n

▢

再用Mobius逆变换可以得到

等价定义1 . 2 Φₙ＝∏d∣n (xᵈ−1)μ(n)＝∏d∣n(xn−1)μ⁽ᵈ⁾ ─

─ d

性质1 . Φₙ(x)为首一整系数多项式

性质2 . Φₙ(x)在ℤ[x]上不可约

性质3 . 若d为n的真因子，则有

Φₙ(x)∣xⁿ−1

───

xᵈ−1

证明： xᵈ−1＝∏ᵈₖ₌₁d(x−εᵏn

─

，(kn

─

d，n)≠1，所以Φₙ(x)和xᵈ−1无公共根，则由引理1知

(Φₙ(x)，xᵈ−1)＝1

又因为Φₙ(x)∣xⁿ−1＝xⁿ−1

───(xᵈ−1)，

xᵈ−1

所以Φₙ(x)∣xⁿ−1

───

xᵈ−1

▢

性质4 . α＞1，n＞2，素数p∣(n，Φₙ(α))，则p是n的最大素因子，且p²∤Φₙ(α)

证明：设n＝pᵏm，(p，m)＝1 . 由p∣Φₙ(α)可得p∣αⁿ−1，于是(p，α)＝1 .

( 1 ) 若p＝2，n＝2ᵏm，若m＞1，由LTE引理有υ₂(αⁿ−1)＝υ₂(α²ᵏ−1) . 2ᵏ是n的真因子，故由性质1 . 3，2∤Φₙ(α)，矛盾！

故m＝1，n＝2ᵏ，2是n的最大素因子 .

由n＞2知k＞1，所以2ᵏ⁻¹是n的真因子，由LTE引理有υ₂(αⁿ−1)＝υ₂(α²ᵏ⁻¹)＋1，由性质3，2²∤Φₙ(α) .

( 2 ) 若p为奇素数，由Fermat小定理知αᵐ≡(αᵐ)ᵖᵏ≡1(mod p)，于是δ＝δₚ(α)∣m .

若δ＜m，则δ是m的真因子，pᵏδ是n的真因子，由LTE引理有υₚ(αⁿ−1)＝υₚ(αᵖᵏδ−1)，由性质3得p∤Φₙ(α)，矛盾！

故δ＝m，又由Fermat小定理知δ∣p−1，于是δ≤p−1＜p，p是n的最大素因子 .

再由LTE引理，υₚ(αⁿ−1)＝υₚ(αᵐᵖᵏ⁻¹ −1)＋1，故p²∤Φₙ(α)

▢

推论 . α＞1，n＞2，p为n的素因子，n＝pᵏm，(p，m)＝1，若素数p∣Φₙ(α)，则α模p的阶δₚ(α)＝m .

性质5 . p为素数，则

{Φₙ(xᵖ) p∣n

Φₙₚ(x)＝{Φₙ(xᵖ)

────

{Φₙ(x) p∤n

证明：记ωₘ为m次单位根 .

( 1 ) 若p∣n，由φ(pn)＝pφ(n)，(k，pn)＝1⟺(k，n)＝1

得

Φₙₚ(x)＝∏ (x−ωᵏₙₚ)

1≤k≤ₙₚ(k，ₙₚ)＝1

＝∏ (x−ωᵏₙₚ)(x − ωₙₚᵏ⁺ⁿ)· · ·(x−ωₙₚᵏ⁺⁽ᵖ⁻¹⁾ⁿ)

1≤k≤p(k，n)＝1

＝∏ (x−ωᵏₙₚ)(x−ωᵏₙₚωₚ)· · ·(x−ωᵏₙₚωₚᵖ⁻¹)

1≤k≤p(k，n)＝1

x x x

＝∏ ωᵏᵖₙₚ (─ − 1)(─ − ωₚ)· · ·(─ − ωₚᵖ⁻¹)

ωᵏₙₚ ωᵏₙₚ ωᵏₙₚ

1≤k≤p(k，n)＝1

xᵖ

＝∏ ωᵏᵖₙₚ (── −1)

ωᵏₙₚ

1≤k≤p(k，n)＝1

＝∏(xᵖ − ωᵏₙ)

1≤k≤p(k，n)＝1

＝Φₙ(xᵖ)

（2）若p∤n，由φ(np)＝(p−1)φ(n)得到pφ(n)＝φ(np)＋φ(n)，又易知np次、n次本原单位根互不相等且均为Φₙ(xᵖ)的根，从而有Φₙ(xᵖ)＝Φₙ(x)Φₙₚ(x)

▢

推论 . 若(p，n)=1，k≥1，则

Φₚᵏₙ(x)＝Φₙ(xᵖᵏ)

───

Φₙ(xᵖᵏ⁻¹)

性质6 . x＞1，n ≥ 3，则有

(x−1)φ(n)＜Φₙ(x)＜(x＋1)φ(n)

证明：对所有n次本原单位根ω，都有

x−1≤|x−ω|≤x＋1

因为n≥3，故φ(n)≥2，上式对于不同的ω不同时取等，所以

(x−1)φ⁽ⁿ⁾＜∏ |x−ω|

ord(ω)＝n

＜(x＋1)φ⁽ⁿ⁾

▢

性质7 . α＞1，p是n的素因子，n＝pᵏm，(m，p)＝1，b＝αᵖᵏ⁻¹，则

Φₙ(α)＞(bᵖ−1)φ⁽ᵐ⁾

───

b＋1)

证明：由性质5推论可得

Φₘ(αᵖᵏ)

Φₙ(α)＝Φ ₚᵏₘ (α)＝────

Φₘ(αᵖᵏ⁻¹)

Φₘ(bᵖ)

＝───

Φₘ(b)

与性质6类似，考虑

φ(m) φ(m)

Φₘ(bᵖ)＝∏ (bᵖ−εₖ)＝∏

k＝1 k＝1

∣bᵖ−εₖ∣≥(bᵖ−1)φ(m)

φ(m) φ(m)

Φₘ(b)＝∏ (b−εₖ)＝∏∣b−εₖ∣≤ (b＋1)φ(m)

k＝1 k＝1

两式不同时取等，故

Φₙ(α)＞(bᵖ−1)φ(m)

───

(b＋1)

▢

PART2 . 用分圆多项式证明Zsigmondy定理

定义2 . Ψₙ(x，y)＝yφ⁽ⁿ⁾Φₙ(─)

等价定义2 . 1

xⁿ−yⁿ＝∏d∣ₙ Ψd(x，y)

证明：利用φ(n)＝∑d∣n n

─

d μ(d)与Mobius变换即得 .

▢

再用Mobius逆变换可以得到

等价定义2 . 2

Ψₙ(x，y)＝∏d∣ₙ(x n

─

d−yn

─

d)μ(d)

引理2 . 正整数α，b，n，n＞1，α＞b，d为n的真因子，(α，b)＝1，若p∣(αᵈ−bᵈ，Ψₙ(α，b))，则p∣n

证明：易知p，α，b两两互素，故存在c＞1使得α≡bc(mod p)，于是有

0≡Ψₙ(α，b)≡Ψₙ(bc，b)≡bφ⁽ⁿ⁾Φₙ(c)(mod p)0≡αᵈ−bᵈ≡bᵈ(cᵈ−1)(mod p)

故p∣Φₙ(c)，p∣cᵈ−1 .

d为n的真因子，由性质3可得

Φₙ(x)∣xⁿ−1

───

xᵈ−1，从而

p∣(cᵈ−1，cⁿ−1)

───

(cᵈ−1)

＝(A，(A＋1)─

d−1 n

───────)＝(A，─)

A d

于是p∣─，所以p∣n

▢

引理3 . 正整数α，b，n，n＞2，α＞b，(α，b)＝1，若p∣(n，Ψₙ(α，b))，则p是n的最大素因子且p²∤Ψₙ(α，b)

证明：易知p，α，b两两互素，故存在c＞1使得α≡bc(mod p²)，于是

Ψₙ(α，b)≡Ψₙ(bc，b)≡bφ⁽ⁿ⁾Φₙ(c)(mod p²) 0≡bφ⁽ⁿ⁾Φₙ(c) (mod p)

故p∣Φₙ(c)，由性质4可得p是n的最大素因子，且p²∤Φₙ(c)，所以p²∤Ψₙ(α，b)

▢

引理4 . 当n＞1为偶数时，Ψ₂ₙ(x，y)＝xⁿ＋yⁿ .

证明：由等价定义2 . 1知

x²ⁿ−y²ⁿ＝∏d Ψd(x，y)

∣2n

＝Ψ₂ₙ(x，y)∏ Ψd(x，y)

d∣n

＝Ψ₂ₙ(x，y)(xⁿ−yⁿ)

即得Ψ₂ₙ(x，y)＝xⁿ＋yⁿ .

▢

Zsigmondy定理的证明：

设对αⁿ−bⁿ的任意素因子p，均存在1≤k＜n，满足p∣αᵏ−bᵏ .

以下考虑Ψₙ(α，b)的任意素因子p，则有p∣αⁿ−bⁿ . 设k为1，2，⋯，n−1中满足p∣αᵏ−bᵏ的最小整数 . 于是

p∣(αⁿ−bⁿ，αᵏ−bᵏ)＝(A⋅(α⁽ⁿ，ᵏ⁾−b⁽ⁿ，ᵏ⁾)，B⋅(α⁽ⁿ，ᵏ⁾−b⁽ⁿ，ᵏ⁾))(A，B∈ℤ)

从而p∣(α⁽ⁿ，ᵏ⁾−b⁽ⁿ，ᵏ⁾)，由于k≤(n，k)≤k，故k＝(n，k)，所以k是n的真因子 . 故由引理2可得p∣n .

假设Ψₙ(α，b)有不同的素因子p，q，则n＞2，且有p，q∣Ψₙ(α，b)，由引理3得p＞q，q＞p，矛盾！故Ψₙ(α，b)为某素数的幂次，设Ψₙ(α，b)＝pᵘ， n＝pαs，(p，s)＝1 .

易知p，α，b两两互素，故存在c＞1使得α≡bc(mod p)，故

0≡Ψₙ(α，b)≡Ψₙ(bc，b)≡bφ⁽ⁿ⁾Φₙ(c) (mod p)

所以p∣Φₙ(c) .

( 1 ) 若p＝2，则α，b为奇数，所以c也为奇数 . 若s＞1，则由性质4推论得s＝δ₂(c)＝1，矛盾！故s＝1，n＝2α .

若α＞1，则由引理4知

2ᵘ＝Ψ₂α(α，b)＝α²α⁻¹＋b²α⁻¹≡2(mod 4)

所以u＝1，但2＝α²α⁻¹＋b²α⁻¹＞2矛盾！

故α＝1，n＝2，α＋b为2的方幂 .

( 2 ) 若p＞2，则n＞2 . 由引理3知p是n的最大素因子，且p²∤Ψₙ(α，b)，故Ψₙ(α，b)＝p .

记r＝α

─＞1，由

φ(pαs)＝pα⁻¹(p−1)φ(s)与性质7得

p＝Ψₙ(α，b)＝bφ⁽ⁿ⁾Φₙ(r)

＞bφ⁽ⁿ⁾(rpα −1)φ⁽ˢ⁾

───

(rpα⁻¹＋1)

≥bφ⁽ⁿ⁾(rᵖα⁻¹(p−1)−rᵖα⁻¹(p−2))φ⁽ˢ⁾

＝(αᵖα⁻¹(p−2)(αᵖα⁻¹−bᵖα⁻¹))φ⁽ˢ⁾

≥(αᵖ⁻²(α−b))φ⁽ˢ⁾

若α≥3，则p＞3ᵖ⁻²＝(1＋2)ᵖ⁻²≥2p−3，推出p＜3，矛盾！

故α＝2，b＝1，此时有

p＞(2ᵖ⁻²)φ⁽ˢ⁾＝((1＋1)ᵖ⁻²)φ⁽ˢ⁾≥(p−1)φ⁽ˢ⁾

故φ(s)＝1，s＝1或2 . 则n＝3α或2⋅3α .

若α≥2，则由定义2与性质5、6得

3＝Ψ₃αₛ(2，1)＝Φ₃αₛ(2)＝Φ₃ₛ(2³α⁻¹)＞2³α⁻¹−1≥2³−1＞3

矛盾！故α＝1 .

若n＝3，则3＝Ψ₃(2，1)＝Φ₃(2)＝7，矛盾！

若n＝6，则3＝Ψ₆(2，1)＝Φ₆(2)＝3，成立 .

综上，除去两种特殊情况1 ) n＝2，α＋b为2的方幂；2 ) n＝6，α＝2，b＝1外，假设均不成立，即证 .

▢

参考文献 .

1.Zsigmondy's theorem-Wikipedia

2.An Elementary Proof of

Zsigmondy's Theorem·Yan Sheng's site(angyansheng.github.io)

3.分圆多项式与kn+1型素数

(zhihu.com)

4.Zsigmondy定理(zhihu.com)