升幂定理

升幂定理

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

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

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

模为奇素数

前提条件:n 为正整数,整数 ab 不被 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 为正整数,整数 ab 都是奇数。

如果 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 为奇数,则 k0n=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,于是 cd 都是平方数,于是 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,从而定理成立。


评论