升幂定理

定义

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

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

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

模为奇素数

前提条件：\(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}\)。

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

模为 2

前提条件：\(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\)，从而定理成立。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用