docs/math/number-theory/lift-the-exponent.md
升幂（Lift the Exponent，LTE）引理是初等数论中比较常用的一个定理．
定义 $\nu_p(n)$ 为整数 $n$ 的标准分解中素因子 $p$ 的幂次，即 $\nu_p(n)$ 满足 $p^{\nu_p(n)}\mid n$ 且 $p^{\nu_p(n)+1}\nmid n$.
由于升幂引理内容较长，我们将其分为三部分介绍：
以下内容设 $p$ 为素数，$x,y$ 为满足 $p\nmid x$ 且 $p\nmid y$ 的整数，$n$ 为正整数．
对所有的素数 $p$ 和满足 $(n,p)=1$ 的整数 $n$，
若 $p\mid x-y$，则：
$$ \nu_p\left(x^n-y^n\right)=\nu_p(x-y) $$
若 $p\mid x+y$，则对奇数 $n$ 有：
$$ \nu_p\left(x^n+y^n\right)=\nu_p(x+y) $$
???+ note "证明" 若 $p\mid x-y$，则不难发现 $p\mid x-y\iff x\equiv y\pmod p$，则显然有：
$$
\sum_{i=0}^{n-1}x^iy^{n-1-i}\equiv nx^{n-1}\not\equiv 0\pmod p
$$
进而由 $x^n-y^n=(x-y)\sum_{i=0}^{n-1}x^iy^{n-1-i}$ 可知命题得证．
对 $p\mid x+y$ 的情况证明方法类似．
若 $p$ 是奇素数，
若 $p\mid x-y$，则：
$$ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(n) $$
若 $p\mid x+y$，则对奇数 $n$ 有：
$$ \nu_p\left(x^n+y^n\right)=\nu_p(x+y)+\nu_p(n) $$
???+ note "证明" 若 $p\mid x-y$，令 $y=x+kp$，我们只需证明 $p\mid n$ 的情况．
- 若 $n=p$，则由二项式定理：
$$
\begin{aligned}
\sum_{i=0}^{p-1}x^{p-1-i}y^i&=\sum_{i=0}^{p-1}x^{p-1-i}\sum_{j=0}^i\binom{i}{j}x^j(kp)^{i-j}\\
&\equiv px^{p-1} \pmod{p^2}\\
\end{aligned}
$$
从而
$$
\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+1
$$
- 若 $n=p^a$，则由数学归纳法可得
$$
\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+a
$$
因此命题得证．
对 $p\mid x+y$ 的情况证明方法类似．
若 $p=2$ 且 $p\mid x-y$，
对奇数 $n$ 有（与第一部分的 1 相同）：
$$ \nu_p\left(x^n-y^n\right)=\nu_p(x-y) $$
对偶数 $n$ 有：
$$ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1 $$
另外对上述的 $x,y,n$，我们有：
若 $4\mid x-y$，则：
???+ note "证明" 我们只需证明 $n$ 为偶数的情况．由于此时 $p\nmid \dbinom{p}{2}$，故我们不能用第二部分的方法证明．
令 $n=2^a b$，其中 $a=\nu_p(n)$，$2\nmid b$，从而
$$
\begin{aligned}
\nu_p\left(x^n-y^n\right)&=\nu_p\left(x^{2^a}-y^{2^a}\right)\\
&=\nu_p\left((x-y)(x+y)\prod_{i=1}^{a-1}\left(x^{2^i}+y^{2^i}\right)\right)
\end{aligned}
$$
注意到 $2\mid x-y\implies 4\mid x^2-y^2$，从而 $(\forall i\geq 1),~~x^{2^i}+y^{2^i}\equiv 2\pmod 4$，进而上式可变为：
$$
\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1
$$
因此命题得证．