升幂定理

升幂定理

升幂定理（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} 。

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

模为 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 ，从而定理成立。

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

评论