升幂定理

定义

升幂定理（Lift the Exponent，常简记为 LTE）根据相应乘法群的结构不同，升幂定理分为两部分，模为奇素数与模为 ，简记为 和 。

定理需要记 为素数 在整数 中的个数，即 恰好整除整数 ， 不整除整数 。

由于其针对模数为素数的幂（）的强大威力，常出现在各种结论的快速证明中。

模为奇素数

前提条件： 为正整数，整数 与 不被 整除，且模 同余。

定理为等式：

证明

设 ，则 ， 不整除 。

模 容易发现 不整除 。

问题转化为分析 。只要 大于 ，记 ，：

模 容易发现 整除 。若令 ，由二项式定理有：

因为 是奇素数，可以得知 不整除 ，因此也不整除 。

利用归纳法，初始条件显然，从而证完了原命题。

模为 2

前提条件： 为正整数，整数 与 都是奇数。

如果 为奇数，定理为等式：

如果 为偶数，定理为等式：

证明

设 ，则 ， 不整除 。

模 容易发现 不整除 。

如果 为奇数，则 为 ，，这部分定理就证完了。

如果 为偶数，则 至少为 ，问题转化为分析 。

如果 大于 ，记 ，：

容易发现 整除 。由于假设 大于 ，于是 和 都是平方数，于是 不整除 ，因此 里只含一个 。

因为 至少为 ，归纳法的初始条件为 ，在 和 中至少有一个不被 整除， 和 中有一个是 ，从而定理成立。