升幂定理

定义

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

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

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

模为奇素数

前提条件: 为正整数,整数 不被 整除,且模 同余。

定理为等式:

证明

,则 不整除

容易发现 不整除

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

容易发现 整除 。若令 ,由二项式定理有:

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

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

模为 2

前提条件: 为正整数,整数 都是奇数。

如果 为奇数,定理为等式:

如果 为偶数,定理为等式:

证明

,则 不整除

容易发现 不整除

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

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

如果 大于 ,记

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

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