

升幂定理

升幂定理¶

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

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

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

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

定理为等式：

$v_p(a^n-b^n)=v_p(a-b)+v_p(n)$

设 $n=p^km$ ，则 $k=v_p(n)$ ， $p$ 不整除 $m$ 。

$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})$

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

问题转化为分析 $a^{p^k}-b^{p^k}$ 。只要 $k$ 大于 $0$ ，记 $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})$

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

$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}$

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

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

前提条件： $n$ 为正整数，整数 $a$ 与 $b$ 都是奇数。

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

$v_2(a^n-b^n)=v_2(a-b)$

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

$v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1$

设 $n=2^km$ ，则 $k=v_2(n)$ ， $2$ 不整除 $m$ 。

$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})$

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

如果 $n$ 为奇数，则 $k$ 为 $0$ ， $n=m$ ，这部分定理就证完了。

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

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

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

容易发现 $2$ 整除 $c+d$ 。由于假设 $k$ 大于 $1$ ，于是 $c$ 和 $d$ 都是平方数，于是 $4$ 不整除 $c+d$ ，因此 $c+d$ 里只含一个 $2$ 。

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用