升幂引理

内容

升幂（Lift the Exponent，LTE）引理是初等数论中比较常用的一个定理。

定义 为整数 的标准分解中素因子 的幂次，即 满足 且 .

由于升幂引理内容较长，我们将其分为三部分介绍：

以下内容设 为素数， 为满足 且 的整数， 为正整数。

第一部分

对所有的素数 和满足 的整数 ，

1. 若 ，则：

2. 若 ，则对奇数 有：

证明

若 ，则不难发现 ，则显然有：

进而由 可知命题得证。

对 的情况证明方法类似。

第二部分

若 是奇素数，

1. 若 ，则：

2. 若 ，则对奇数 有：

证明

若 ，令 ，我们只需证明 的情况。

• 若 ，则由二项式定理：

  从而

• 若 ，则由数学归纳法可得

因此命题得证。

对 的情况证明方法类似。

第三部分

若 且 ，

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

2. 对偶数 有：

另外对上述的 ，我们有：

若 ，则：

证明

我们只需证明 为偶数的情况。由于此时 ，故我们不能用第二部分的方法证明。

令 ，其中 ，，从而

注意到 ，从而 ，进而上式可变为：

因此命题得证。

参考资料

1. Lifting-the-exponent lemma - Wikipedia

---

最后更新: 2024年12月16日
创建日期: 2021年9月9日