跳转至

# 升幂引理

## 内容

升幂（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，

1. 若 𝑝 ∣𝑥 −𝑦 p∣x−y，则：

   𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)ν p(x n−y n)=ν p(x−y)

2. 若 𝑝 ∣𝑥 +𝑦 p∣x+y，则对奇数 𝑛 n 有：

   𝜈 𝑝(𝑥 𝑛+𝑦 𝑛)=𝜈 𝑝(𝑥+𝑦)ν p(x n+y n)=ν p(x+y)

证明

若 𝑝 ∣𝑥 −𝑦 p∣x−y，则不难发现 𝑝 ∣𝑥 −𝑦 ⟺ 𝑥 ≡𝑦(m o d 𝑝)p∣x−y⟺x≡y(mod p)，则显然有：

𝑛−1∑𝑖=0 𝑥 𝑖 𝑦 𝑛−1−𝑖≡𝑛 𝑥 𝑛−1≢0(m o d 𝑝)∑i=0 n−1 x i y n−1−i≡n x n−1≢0(mod p)

进而由 𝑥 𝑛 −𝑦 𝑛 =(𝑥 −𝑦)∑𝑛−1 𝑖=0 𝑥 𝑖 𝑦 𝑛−1−𝑖 x n−y n=(x−y)∑i=0 n−1 x i y n−1−i 可知命题得证．

对 𝑝 ∣𝑥 +𝑦 p∣x+y 的情况证明方法类似．

### 第二部分

若 𝑝 p 是奇素数，

1. 若 𝑝 ∣𝑥 −𝑦 p∣x−y，则：

   𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)+𝜈 𝑝(𝑛)ν p(x n−y n)=ν p(x−y)+ν p(n)

2. 若 𝑝 ∣𝑥 +𝑦 p∣x+y，则对奇数 𝑛 n 有：

   𝜈 𝑝(𝑥 𝑛+𝑦 𝑛)=𝜈 𝑝(𝑥+𝑦)+𝜈 𝑝(𝑛)ν p(x n+y n)=ν p(x+y)+ν p(n)

证明

若 𝑝 ∣𝑥 −𝑦 p∣x−y，令 𝑦 =𝑥 +𝑘 𝑝 y=x+k p，我们只需证明 𝑝 ∣𝑛 p∣n 的情况．

- 若 𝑛 =𝑝 n=p，则由二项式定理：

  𝑝−1∑𝑖=0 𝑥 𝑝−1−𝑖 𝑦 𝑖=𝑝−1∑𝑖=0 𝑥 𝑝−1−𝑖 𝑖∑𝑗=0(𝑖 𝑗)𝑥 𝑗(𝑘 𝑝)𝑖−𝑗≡𝑝 𝑥 𝑝−1(m o d 𝑝 2)∑i=0 p−1 x p−1−i y i=∑i=0 p−1 x p−1−i∑j=0 i(i j)x j(k p)i−j≡p x p−1(mod p 2)

  从而

  𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)+1 ν p(x n−y n)=ν p(x−y)+1

- 若 𝑛 =𝑝 𝑎 n=p a，则由数学归纳法可得

  𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)+𝑎 ν p(x n−y n)=ν p(x−y)+a

因此命题得证．

对 𝑝 ∣𝑥 +𝑦 p∣x+y 的情况证明方法类似．

### 第三部分

若 𝑝 =2 p=2 且 𝑝 ∣𝑥 −𝑦 p∣x−y，

1. 对奇数 𝑛 n 有（与第一部分的 1 相同）：

   𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)ν p(x n−y n)=ν p(x−y)

2. 对偶数 𝑛 n 有：

   𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)+𝜈 𝑝(𝑥+𝑦)+𝜈 𝑝(𝑛)−1 ν p(x n−y n)=ν 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(x n−y n)=ν 2(x−y)+ν 2(n)

证明

我们只需证明 𝑛 n 为偶数的情况．由于此时 𝑝 ∤(𝑝 2)p∤(p 2)，故我们不能用第二部分的方法证明．

令 𝑛 =2 𝑎 𝑏 n=2 a b，其中 𝑎 =𝜈 𝑝(𝑛)a=ν p(n)，2 ∤𝑏 2∤b，从而

𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥 2 𝑎−𝑦 2 𝑎)=𝜈 𝑝((𝑥−𝑦)(𝑥+𝑦)𝑎−1∏𝑖=1(𝑥 2 𝑖+𝑦 2 𝑖))ν p(x n−y n)=ν p(x 2 a−y 2 a)=ν p((x−y)(x+y)∏i=1 a−1(x 2 i+y 2 i))

注意到 2 ∣𝑥 −𝑦 ⟹ 4 ∣𝑥 2 −𝑦 2 2∣x−y⟹4∣x 2−y 2，从而 (∀𝑖 ≥1), 𝑥 2 𝑖 +𝑦 2 𝑖 ≡2(m o d 4)(∀i≥1), x 2 i+y 2 i≡2(mod 4)，进而上式可变为：

𝜈 𝑝(𝑥 𝑛−𝑦 𝑛)=𝜈 𝑝(𝑥−𝑦)+𝜈 𝑝(𝑥+𝑦)+𝜈 𝑝(𝑛)−1 ν p(x n−y n)=ν p(x−y)+ν p(x+y)+ν p(n)−1

因此命题得证．

## 参考资料

1. Lifting-the-exponent lemma - Wikipedia

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, c-forrest, Enter-tainer, Great-designer, iamtwz, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用