升幂定理

定义

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

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

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

模为奇素数

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

定理为等式:

证明

,则 不整除

容易发现 不整除

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

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

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

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

模为 2

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

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

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

证明

,则 不整除

容易发现 不整除

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

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

如果 大于 ,记

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

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


评论