升幂引理
内容
升幂（Lift the Exponent，LTE）引理是初等数论中比较常用的一个定理．
定义 𝜈𝑝(𝑛)νp(n)
为整数 𝑛n 的标准分解中素因子 𝑝p 的幂次，即 𝜈𝑝(𝑛)νp(n) 满足 𝑝𝜈𝑝(𝑛) ∣𝑛pνp(n)∣n 且 𝑝𝜈𝑝(𝑛)+1 ∤𝑛pνp(n)+1∤n.
由于升幂引理内容较长，我们将其分为三部分介绍：
以下内容设 𝑝p 为素数，𝑥,𝑦x,y 为满足 𝑝 ∤𝑥p∤x 且 𝑝 ∤𝑦p∤y 的整数，𝑛n 为正整数．
第一部分
对所有的素数 𝑝p 和满足 (𝑛,𝑝) =1(n,p)=1 的整数 𝑛n，
- 若 𝑝 ∣𝑥 −𝑦p∣x−y，则：
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)νp(xn−yn)=νp(x−y)
- 若 𝑝 ∣𝑥 +𝑦p∣x+y，则对奇数 𝑛n 有：
𝜈𝑝(𝑥𝑛+𝑦𝑛)=𝜈𝑝(𝑥+𝑦)νp(xn+yn)=νp(x+y)
证明
若 𝑝 ∣𝑥 −𝑦p∣x−y，则不难发现 𝑝 ∣𝑥 −𝑦 ⟺ 𝑥 ≡𝑦(mod𝑝)p∣x−y⟺x≡y(modp)，则显然有：
𝑛−1∑𝑖=0𝑥𝑖𝑦𝑛−1−𝑖≡𝑛𝑥𝑛−1≢0(mod𝑝)∑i=0n−1xiyn−1−i≡nxn−1≢0(modp)
进而由 𝑥𝑛 −𝑦𝑛 =(𝑥 −𝑦)∑𝑛−1𝑖=0𝑥𝑖𝑦𝑛−1−𝑖xn−yn=(x−y)∑i=0n−1xiyn−1−i 可知命题得证．
对 𝑝 ∣𝑥 +𝑦p∣x+y 的情况证明方法类似．
第二部分
若 𝑝p 是奇素数，
- 若 𝑝 ∣𝑥 −𝑦p∣x−y，则：
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)+𝜈𝑝(𝑛)νp(xn−yn)=νp(x−y)+νp(n)
- 若 𝑝 ∣𝑥 +𝑦p∣x+y，则对奇数 𝑛n 有：
𝜈𝑝(𝑥𝑛+𝑦𝑛)=𝜈𝑝(𝑥+𝑦)+𝜈𝑝(𝑛)νp(xn+yn)=νp(x+y)+νp(n)
证明
若 𝑝 ∣𝑥 −𝑦p∣x−y，令 𝑦 =𝑥 +𝑘𝑝y=x+kp，我们只需证明 𝑝 ∣𝑛p∣n 的情况．
- 若 𝑛 =𝑝n=p，则由二项式定理：
𝑝−1∑𝑖=0𝑥𝑝−1−𝑖𝑦𝑖=𝑝−1∑𝑖=0𝑥𝑝−1−𝑖𝑖∑𝑗=0(𝑖𝑗)𝑥𝑗(𝑘𝑝)𝑖−𝑗≡𝑝𝑥𝑝−1(mod𝑝2)∑i=0p−1xp−1−iyi=∑i=0p−1xp−1−i∑j=0i(ij)xj(kp)i−j≡pxp−1(modp2)
从而
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)+1νp(xn−yn)=νp(x−y)+1
- 若 𝑛 =𝑝𝑎n=pa，则由数学归纳法可得
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)+𝑎νp(xn−yn)=νp(x−y)+a
因此命题得证．
对 𝑝 ∣𝑥 +𝑦p∣x+y 的情况证明方法类似．
第三部分
若 𝑝 =2p=2 且 𝑝 ∣𝑥 −𝑦p∣x−y，
- 对奇数 𝑛n 有（与第一部分的 1 相同）：
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)νp(xn−yn)=νp(x−y)
- 对偶数 𝑛n 有：
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)+𝜈𝑝(𝑥+𝑦)+𝜈𝑝(𝑛)−1νp(xn−yn)=νp(x−y)+νp(x+y)+νp(n)−1
另外对上述的 𝑥,𝑦,𝑛x,y,n，我们有：
若 4 ∣𝑥 −𝑦4∣x−y，则：
- 𝜈2(𝑥 +𝑦) =1ν2(x+y)=1
- 𝜈2(𝑥𝑛−𝑦𝑛) =𝜈2(𝑥 −𝑦) +𝜈2(𝑛)ν2(xn−yn)=ν2(x−y)+ν2(n)
证明
我们只需证明 𝑛n 为偶数的情况．由于此时 𝑝 ∤(𝑝2)p∤(p2)，故我们不能用第二部分的方法证明．
令 𝑛 =2𝑎𝑏n=2ab，其中 𝑎 =𝜈𝑝(𝑛)a=νp(n)，2 ∤𝑏2∤b，从而
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥2𝑎−𝑦2𝑎)=𝜈𝑝((𝑥−𝑦)(𝑥+𝑦)𝑎−1∏𝑖=1(𝑥2𝑖+𝑦2𝑖))νp(xn−yn)=νp(x2a−y2a)=νp((x−y)(x+y)∏i=1a−1(x2i+y2i))
注意到 2 ∣𝑥 −𝑦 ⟹ 4 ∣𝑥2 −𝑦22∣x−y⟹4∣x2−y2，从而 (∀𝑖 ≥1), 𝑥2𝑖 +𝑦2𝑖 ≡2(mod4)(∀i≥1), x2i+y2i≡2(mod4)，进而上式可变为：
𝜈𝑝(𝑥𝑛−𝑦𝑛)=𝜈𝑝(𝑥−𝑦)+𝜈𝑝(𝑥+𝑦)+𝜈𝑝(𝑛)−1νp(xn−yn)=νp(x−y)+νp(x+y)+νp(n)−1
因此命题得证．
参考资料
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Tiphereth-A, c-forrest, Enter-tainer, Great-designer, iamtwz, Xeonacid 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用