升幂定理

定义

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

定理需要记为素数在整数中的个数，即 $p^{v_p(n)}$ 恰好整除整数， $p^{v_p(n)+1}$ 不整除整数。

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

模为奇素数

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

定理为等式：

证明

设，则，不整除。

a^n-b^n=a^{p^km}-b^{p^km}=(a^{p^k}-b^{p^k})(a^{m-1}+a^{m-2}b+\ldots+b^{m-1})

模容易发现不整除 $a^{m-1}+a^{m-2}b+\ldots+b^{m-1}$ 。

问题转化为分析 $a^{p^k}-b^{p^k}$ 。只要大于，记 $c=a^{p^{k-1}}$ ， $d=b^{p^{k-1}}$ ：

a^{p^k}-b^{p^k}=c^p-d^p=(c-d)(c^{p-1}+c^{p-2}d+\ldots+d^{p-1})

模容易发现整除 $c^{p-1}+c^{p-2}d+\ldots+d^{p-1}$ 。若令，由二项式定理有：

c^{p-1}+c^{p-2}d+\ldots+d^{p-1}=\frac{d^p-c^p}{d-c}=\frac{(c+kp)^p-c^p}{kp}=C_p^1 c^{p-1}+C_p^2 c^{p-2}kp+\ldots\equiv C_p^1 c^{p-1} \pmod {p^2}

因为是奇素数，可以得知不整除 $C_p^1 c^{p-1}$ ，因此也不整除 $c^{p-1}+c^{p-2}d+\ldots+c^{p-1}$ 。

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

模为 2

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

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

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

证明

设，则，不整除。

a^n-b^n=a^{2^km}-b^{2^km}=(a^{2^k}-b^{2^k})(a^{m-1}+a^{m-2}b+\ldots+b^{m-1})

模容易发现不整除 $a^{m-1}+a^{m-2}b+\ldots+b^{m-1}$ 。

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

如果为偶数，则至少为，问题转化为分析 $a^{2^k}-b^{2^k}$ 。

如果大于，记 $c=a^{2^{k-1}}$ ， $d=b^{2^{k-1}}$ ：

a^{2^k}-b^{2^k}=c^2-d^2=(c-d)(c+d)

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

因为至少为，归纳法的初始条件为，在 $\frac{a+b}{2}$ 和 $\frac{a-b}{2}$ 中至少有一个不被整除，和中有一个是，从而定理成立。

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