升幂定理

升幂定理

升幂定理（Lift the Exponent，常简记为 LTE）由于其针对模数为素数的幂（）的强大威力，常出现在各种结论的快速证明中。

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

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

模为奇素数

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

定理为等式：

证明

设 ，则 ， 不整除 。

模 容易发现 不整除 。

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

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

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

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

模为 2

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

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

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

证明

设 ，则 ， 不整除 。

模 容易发现 不整除 。

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

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

如果 大于 ，记 ，：

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

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

build本页面最近更新：2021/9/9 22:14:05，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Enter-tainer, Great-designer
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论