如何证明升幂定理？

一、定义

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

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

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

二、模为奇素数

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

定理为等式：

证明

设，则 ，p 不整除 m。

模 p 容易发现 p 不整除 。

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

模 p 容易发现 p 整除 。若令 d=c+kp ，由二项式定理有：

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

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