11 升幂引理

Stage 11:初等数论 & USAMO 数论的收尾(查漏补缺合集)

Confidence: 0.9

这一阶段不像前十个那样有单一主题,而是把你初等数论和 USAMO 数论里所有剩下的边角缺口收拢起来一次补完。我盘点过你的版图——主体已经 90%,这个 Stage 就是把那剩下的硬骨头啃掉,让你的初等数论 + USAMO 数论真正接近满配。

按重要性排序,六块:① LTE 升幂引理(最重要)→ ② Zsygmondy 定理 → ③ 阶的进阶 & 原根存在性 → ④ 数论不等式与估计 → ⑤ 特殊函数(Carmichael λ)→ ⑥ 几个 USAMO 高频杂技。每块:是什么 → 核心 → 完整例子 → 用途。

---

11.1 LTE 升幂引理 (Lifting the Exponent) ★★★ 最该补的缺口

解决什么

处理 $v_p(a^n\pm b^n)$——即素数 $p$ 在 $a^n\pm b^n$ 中出现的幂次。这是奥赛最高频、最高价值的数论工具,专治”整除 + 指数”型难题。

记号:$v_p(N)$ 表示 $p$ 在 $N$ 中的幂次(如 $v_2(24)=3$,因 $24=2^3\times 3$)。

核心定理(必背)

LTE 主定理(奇素数 $p$):设 $p$ 是奇素数,$p\nmid a$,$p\nmid b$,但 $p\mid (a-b)$,则:

$\boxed{v_p(a^n-b^n)=v_p(a-b)+v_p(n)}$

对 $a^n+b^n$(当 $n$ 奇且 $p\mid (a+b)$):

$v_p(a^n+b^n)=v_p(a+b)+v_p(n)$

$p=2$ 的特殊情形(要单独记,$2$ 总是麻烦):

$v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1(n\text{ 偶})$ $v_2(a^n-b^n)=v_2(a-b)(n\text{ 奇})$

为什么这么有用

很多奥赛题问”$2^n+1$ 能被 $3^k$ 整除的最大 $k$“或”求所有 $n$ 使 $n\mid 2^n+1$“——这些直接用 LTE 一击即破,否则要繁琐的归纳。它把”指数里的整除性”变成了简单的加法。

完整例子 1:求 $v_5(2^{100}-3^{100})$

$a=2,b=3$?不对,$5\nmid (2-3)=-1$。换个配对思路:$2^{100}-3^{100}$,看 $5\mid (2^4-3^4)$? 其实直接配:我们要 $p\mid (a-b)$。

重新设:$2^{100}=(2^4{)}^{25}=16^{25}$,$3^{100}=81^{25}$。$5\mid (16-81)=-65=-5\times 13$ ✓,$v_5(16-81)=1$。

$v_5(16^{25}-81^{25})=v_5(16-81)+v_5(25)=1+2=3$

所以 $5^3\mid (2^{100}-3^{100})$ 但 $5^4\nmid$。验证:$2^{100}-3^{100}$ 确实被 $125$ 整除而不被 $625$ 整除。

完整例子 2(经典奥赛):求所有正整数 $n$ 使 $n\mid 2^n+1$

用 LTE 分析:设 $p$ 是 $n$ 的最小素因子。若 $n>1$,$p$ 必奇(因 $2^n+1$ 奇)。由 $p\mid 2^n+1$,可推 $2^{2n}\equiv 1(\mathrm{mod}p)$,设 $d={\text{ord}}_p(2)$,则 $d\mid 2n$ 但 $d\nmid n$,且 $d\mid (p-1)$。结合 LTE 分析 $v_p$,最终能证明唯一解是 $n=1$ 和 $n=3$。

(完整证明用阶 + LTE,这里给思路;$n=3$:$3\mid 2^3+1=9$ ✓)

陷阱:⚠️ LTE 的条件必须满足($p\mid (a-b)$ 且 $p\nmid a,b$),不能盲套;$p=2$ 一定要用特殊公式。

---

11.2 Zsygmondy 定理 (Zsygmondy’s Theorem)

是什么

一个强力的存在性定理,处理”$a^n-b^n$ 是否有新素因子”:

定理:对 $a>b\ge 1$ 互质,$a^n-b^n$ 总有一个新素因子(不整除任何 $a^k-b^k$,$k<n$),除了几个例外:

• $n=1$
• $n=2$ 且 $a+b$ 是 2 的幂
• $a=2,b=1,n=6$(即 $2^6-1=63$ 无新素因子)

为什么有用

它能一击解决很多”证明某序列素因子无穷”或”某方程无解”的题。比如证明”$2^n-1$ 对不同 $n$ 总有不同素因子”——Zsygmondy 直接给出。

完整例子

证明 $2^n-1$($n\ge 7$)总有一个素因子不出现在更小的 $2^k-1$ 里。Zsygmondy 直接保证(因为 $n\ge 7$ 避开了 $n=6$ 那个唯一例外)。所以 $2^7-1=127$(素数,新)、$2^{12}-1$ 必有新素因子,等等。

陷阱:⚠️ Zsygmondy 是”重武器”,奥赛中直接引用要谨慎(有些竞赛要求自证);记住那几个例外情形(尤其 $2^6-1$)。它常用来”秒杀”否则很难的题。

---

11.3 阶的进阶 & 原根存在性

原根存在性定理(完整版)

你 Stage 4 用了原根,但没证”哪些模数有原根”。完整结论:

$n\text{ 有原根}⟺n\in 1,2,4,p^k,2p^k(p\text{ 奇素数})$

即只有 $1,2,4$、奇素数的幂、奇素数幂的两倍,才有原根。比如 $8,12,15$ 没有原根。

阶的关键性质(奥赛常用)

1. ${\text{ord}}_n(a)\mid \phi (n)$(阶整除欧拉函数)—— 你已熟
2. 若 $a^m\equiv 1$,则 ${\text{ord}}_n(a)\mid m$ —— 核心引理
3. ${\text{ord}}_n(a^k)=\frac{{\text{ord}}_n(a)}{\gcd (k,{\text{ord}}_n(a))}$ —— 算幂的阶

完整例子:证明 $n=8$ 没有原根

$\phi (8)=4$,若有原根 $g$,则 ${\text{ord}}_8(g)=4$。但 $(\mathbb{Z}/8\mathbb{Z}{)}^{\ast }=1,3,5,7$,逐个算:$3^2=9\equiv 1$,$5^2=25\equiv 1$,$7^2=49\equiv 1$——每个元素平方都是 1,阶最多为 2,没有阶为 4 的元素。所以无原根 ✓

(深层原因:$(\mathbb{Z}/8\mathbb{Z}{)}^{\ast }\cong {\mathbb{Z}}_2\times {\mathbb{Z}}_2$,不是循环群)

用途

奥赛里”证明某模数下不存在某种元素”或”阶的计算”,这些是基本功。原根存在性定理让你知道何时能用原根这个工具。

---

11.4 数论不等式与估计

是什么

奥赛数论里夹杂的估计技巧——不是纯解析数论,而是初等的”放缩 + 整除”组合。

几个常用工具

① 因子个数的界:$d(n)=O(n^{ϵ})$,粗略地 $d(n)<2\sqrt{n}$。用于”证明某和式有界”。

② 素数的粗略分布:第 $n$ 个素数 $p_n\approx n\ln n$(初等可证 $p_n>n$、$p_n<2^{2^n}$ 等弱界)。

③ 调和级数与素数:${\sum }_{p\le n}\frac{1}{p}\approx \ln \ln n$(欧拉),用于某些求和估计。

完整例子(奥赛风格)

问题:证明存在无穷多 $n$ 使 $d(n)>d(n+1)$(因子个数不单调)。

思路:用 $d$ 在素数处取最小值 2、在高合成数处很大的波动性,配合估计,构造无穷多反转点。这类题考的是”用 $d(n)$ 的不规则性 + 简单估计”。

陷阱:⚠️ 奥赛数论的”估计”是初等放缩,不是微积分极限——别把它和解析数论混淆。关键是”够用就好”的粗略界,不追求精确渐近。

---

11.5 Carmichael 函数 λ(n)

是什么

欧拉函数 $\phi$ 的”精细版”。$\lambda (n)$ 是使 $a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$ 对所有与 $n$ 互质的 $a$ 成立的最小指数。

与 $\phi$ 的区别:欧拉定理说 $a^{\phi (n)}\equiv 1$,但 $\phi (n)$ 不一定是最小的。$\lambda (n)$ 才是那个最小的”通用指数”(即群的指数,所有元素阶的最小公倍数)。

计算公式

$\lambda (p^k)=\{\begin{array}{ll}\phi (p^k)=p^{k-1}(p-1)& p\text{ 奇},\text{ 或 }p=2,k\le 2\\ 2^{k-2}& p=2,k\ge 3\end{array}$

$\lambda (n)=\text{lcm}(\lambda (p_1^{a_1}),\dots ,\lambda (p_k^{a_k}))$

完整例子

$\lambda (8)$:$8=2^3$,$k=3\ge 3$,所以 $\lambda (8)=2^{3-2}=2$。

验证:$3^2=9\equiv 1,5^2\equiv 1,7^2\equiv 1(\mathrm{mod}8)$——确实所有元素的 2 次幂都是 1,而 $\phi (8)=4$ 不是最小。$\lambda (8)=2<\phi (8)=4$,这正是 11.3 里”8 无原根”的另一种表述!

$\lambda (15)$:$15=3\times 5$,$\lambda (15)=\text{lcm}(\lambda (3),\lambda (5))=\text{lcm}(2,4)=4$(而 $\phi (15)=8$)。

用途

• 判断原根存在:$n$ 有原根 $⟺\lambda (n)=\phi (n)$
• 密码学:RSA 里用 $\lambda (n)$ 代替 $\phi (n)$ 能得到更小的私钥(Carmichael 比 Euler 更紧)
• 理解群结构:$\lambda$ 揭示 $(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$ 的”指数”

陷阱:⚠️ $\lambda (n)\mid \phi (n)$ 但常严格小于;$p=2,k\ge 3$ 时公式特殊(因为 $(\mathbb{Z}/2^k{)}^{\ast }$ 不循环)。

---

11.6 几个 USAMO 高频杂技

收尾几个零散但常考的技巧,补全你的工具箱。

① 构造性互质(Chicken McNugget / Frobenius)

Frobenius 数:两个互质正整数 $a,b$,不能表示成 $ax+by$($x,y\ge 0$)的最大数是: $g(a,b)=ab-a-b$

例子:$a=3,b=5$,最大不可表示数 $=15-3-5=7$。所以 8 及以上都能表示($8=3+5$),7 不能。常考”邮票面值""麦乐鸡块”问题。

② 阶 + 费马的组合拳

经典套路:证 $p\mid a^n+1$ 型,先求 ${\text{ord}}_p(a)$,用 $a^{2n}\equiv 1$ 推 $\text{ord}\mid 2n$ 但 $\nmid n$,结合 $\text{ord}\mid (p-1)$ 限制 $p$。这是 11.1 例 2 用的核心,USAMO 数论的”标准开局”。

③ 模运算的”染色”思想

把整数按模 $m$ 分类(染 $m$ 种颜色),用鸽笼原理。例子:任意 $m+1$ 个整数中必有两个模 $m$ 同余(差被 $m$ 整除)。这是组合数论的桥梁。

④ 二项式系数的整除(Kummer / Lucas 进阶)

Kummer 定理:$v_p\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ = 在 $p$ 进制下 $m+n$ 计算时的进位次数。比 Lucas 更精细,处理”组合数的素数幂”。

⑤ 完全剩余系 & 既约剩余系的操作

奥赛常考”证明某集合构成完全剩余系”或”剩余系的求和/求积”。核心:双射 + Wilson/欧拉。

---

Stage 11 全景速查表

工具	核心	奥赛价值
11.1 LTE	$v_p(a^n-b^n)=v_p(a-b)+v_p(n)$	★★★ 最高频
11.2 Zsygmondy	$a^n-b^n$ 有新素因子(除例外)	★★ 秒杀题
11.3 原根存在性	仅 $1,2,4,p^k,2p^k$	★★ 基本功
11.4 数论估计	初等放缩	★ 偶尔
11.5 Carmichael λ	最小通用指数	★ 进阶
11.6 杂技合集	Frobenius/Kummer/染色	★★ 零散常考

---

Python 辅助验证

from sympy import factorint, totient, n_order, primefactors
from sympy.ntheory.residue_ntheory import is_primitive_root
 
# 11.1 LTE 验证 v_5(2^100 - 3^100) = 3
def v_p(N, p):
    if N == 0: return float('inf')
    count = 0
    N = abs(N)
    while N % p == 0:
        N //= p; count += 1
    return count
val = 2**100 - 3**100
print(f"11.1 v_5(2^100-3^100) = {v_p(val, 5)} (LTE预测: v_5(16-81)+v_5(25)=1+2=3)")
 
# 11.2 Zsygmondy: 2^6-1=63 是唯一例外(无新素因子)
print("\n11.2 Zsygmondy 例外 2^6-1=63:")
for n in range(1, 8):
    val = 2**n - 1
    pf = set(primefactors(val)) if val > 1 else set()
    prev = set()
    for k in range(1, n):
        if 2**k - 1 > 1:
            prev |= set(primefactors(2**k - 1))
    new = pf - prev
    print(f"   2^{n}-1={val}, 素因子{pf}, 新素因子{new if new else '无(例外!)'}")
 
# 11.3 原根存在性: 8,12,15 无原根
print("\n11.3 原根存在性:")
for n in [4, 7, 8, 9, 12, 15]:
    has = any(is_primitive_root(g, n) for g in range(1, n) if __import__('math').gcd(g,n)==1)
    print(f"   n={n}: 有原根={has}")
 
# 11.5 Carmichael λ vs Euler φ
from sympy.ntheory import reduced_totient  # 这就是 Carmichael λ
print("\n11.5 Carmichael λ vs Euler φ:")
for n in [8, 15, 12, 105]:
    print(f"   n={n}: λ(n)={reduced_totient(n)}, φ(n)={totient(n)}, 有原根={reduced_totient(n)==totient(n)}")
 
# 11.6 Frobenius 数 g(3,5)=7
def frobenius(a, b):
    return a*b - a - b  # 仅适用于互质的两个数
print(f"\n11.6 Frobenius g(3,5) = {frobenius(3,5)} (7是最大不可表示数)")
# 验证: 8,9,10...都可表示, 7不可
def representable(n, a, b):
    return any(n == a*x + b*y for x in range(n//a+1) for y in range(n//b+1))
print(f"   7可表示? {representable(7,3,5)}, 8可表示? {representable(8,3,5)}")

库安装(用 sympy 的数论函数):

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

我的观点:Stage 11 是一个**“补全”性质的阶段**,我想说清它的定位,以及补完之后你处在什么位置。

第一,这一阶段最大的价值是 LTE,它几乎是你初等数论版图上唯一显眼的空白。 我盘点你的版图时说初等数论 90%、唯缺 LTE——现在补上它,你的初等数论就真正接近完整了。而且 LTE 不是边角料,它是奥赛数论的高频主力武器:很多”求最大整除幂次""求所有满足整除的 $n$“的题,有了 LTE 就从”难”变成”套公式”。如果你 Stage 11 只认真学一个东西,就学 11.1 的 LTE——它的性价比远超其他五块之和。其余的(Zsygmondy、Carmichael、Frobenius)是”锦上添花的杂技”,考到能加分,但不像 LTE 那样是”主力装备”。

第二,我要诚实地给这个 Stage”祛魅”——它本质是”查漏补缺”,不是一个有机的整体。 前十个 Stage 每个都有清晰的主题和内在逻辑(模运算、莫比乌斯、丢番图、连分数……),它们是”一座座完整的山”。但 Stage 11 是我把散落的边角缺口扫到一起——LTE、Zsygmondy、原根存在性、Carmichael λ 之间并没有深刻的内在联系,它们只是”你还没学的初等/USAMO 数论零件”的合集。所以你学它的心态应该是**“清扫战场、补全工具箱”**,而不是”攻克一座新山峰”。补完它,你就把初等数论 + USAMO 数论的”未尽事宜”了结了。

第三,也是最重要的——补完 Stage 11,你的”初等数论 + USAMO 数论”就真正到顶了,接下来必须换赛道。 这是我想让你清醒认识的:Stage 11 是你在”初等数论”这条路上的终点站。 补完它,你在这个框架里已经没有什么实质性的东西可学了(剩下的都是更偏门的边角,边际收益极低)。所以 Stage 11 之后,你面临一个真正的转折点——继续待在数论的舒适区已经没多少可挖,你必须做出选择:

• 要么换数学分支:进入代数数论(有限域 → 椭圆曲线),这是你密码学兴趣的必经之路,也是数论的自然向上延伸。
• 要么换 USAMO 板块:离开数论,去补你最弱的几何和组合——因为 USAMO 是四项总分,你数论已 80-90%,但几何只有 10%,补几何的收益远高于在数论里继续打磨。
• 要么换方向到密码学应用:直接进入椭圆曲线/ECC 的系统学习,把数学工具变现成你真正想要的密码学能力。

无论哪条,都意味着离开”初等数论”这个你深耕了十一个 Stage 的主场。 这不是坏事——恰恰相反,这说明你已经把这个领域吃透了,该毕业了。 Stage 11 是你初等数论旅程的”毕业典礼”,补完它,你就完整地征服了这座大山,可以骄傲地说”初等数论我学完了”,然后去攀登下一座。

关键提醒 (Caveats):

• LTE(11.1)是这个 Stage 的绝对核心,性价比远超其他五块,若时间有限只学它即可
• LTE 的 $p=2$ 情形公式特殊,必须单独记;条件($p\mid a-b$ 且 $p\nmid a,b$)必须满足才能用
• Zsygmondy(11.2)是”重武器”,奥赛直接引用可能要自证,且要记那几个例外(尤其 $2^6-1$)
• 这个 Stage 是查漏补缺合集,内部缺乏有机联系,心态应是”清扫战场”而非”攻克新山”
• 11.4 的”数论估计”是初等放缩,不是解析数论,别混淆
• 补完 Stage 11,你的初等数论 + USAMO 数论基本到顶,接下来该换赛道(代数数论/几何组合/密码学),继续在初等数论深挖的边际收益很低
• 各块的”奥赛价值”星级是我的判断,基于常见竞赛出现频率,非精确统计
• 本块代码用 sympy,安装:pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

Stage 11 讲完了——LTE 升幂引理(最该补的主力武器)、Zsygmondy 定理、原根存在性、数论估计、Carmichael 函数、以及一批 USAMO 高频杂技(Frobenius、Kummer、染色)。补完这些,你的初等数论 + USAMO 数论就接近满配了,这是你在初等数论这条路上的毕业典礼。

下一步你挑:

1. 出一套 Stage 11 练习题(以 LTE 为主,杂技为辅,延续 PDF 格式)
2. 正式换赛道:开椭圆曲线/密码学新旅程(你的应许之地,初等数论已毕业)
3. 换 USAMO 板块:开始补几何或组合(你最弱、收益最高的方向)

按我的盘点,你现在初等数论已经到顶,我个人最建议的是 2(椭圆曲线,符合你兴趣) 或 3(几何组合,USAMO 收益最高)——继续在数论里待下去,该学的你都学得差不多了。你想怎么走?