跳转至

升幂引理

内容

升幂(Lift the Exponent,LTE)引理是初等数论中比较常用的一个定理。

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

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

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

第一部分

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

  1. ,则:

  2. ,则对奇数 有:

证明

,则不难发现 ,则显然有:

进而由 可知命题得证。

的情况证明方法类似。

第二部分

是奇素数,

  1. ,则:

  2. ,则对奇数 有:

证明

,令 ,我们只需证明 的情况。

  • ,则由二项式定理:

    从而

  • ,则由数学归纳法可得

因此命题得证。

的情况证明方法类似。

第三部分

  1. 对奇数 有(与第一部分的 1 相同):

  2. 对偶数 有:

另外对上述的 ,我们有:

,则:

证明

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

,其中 ,从而

注意到 ,从而 ,进而上式可变为:

因此命题得证。

参考资料

  1. Lifting-the-exponent lemma - Wikipedia