升幂引理

发现自己居然没有写过升幂引理的东西。

因为证明比较简单，所以本文就不写了，想知道就看参考文献[1]吧。

---

以下设 $p$ 为质数，令 $x,y$ 为满足 $p \not\mid x$ 且 $p \not\mid y$ 的整数，且 $n$ 为正整数

升幂（Lift the Exponent，LTE）引理是初等数论中比较常用的一个定理。

定义 $v_p(n)$ 为整数 $n$ 标准分解中素因数 $p$ 的幂次，即 $n = \prod_{p \mid n} p^{v_p(n)}$ 。

第一部分

对于所有的素数 $p$ 和满足 $\gcd(n, p) = 1$ 的整数 $n$ ：

• 若 $p \mid x - y$​ ，则

  $$v_p\left(x^n-y^n\right)=v_p(x-y)$$

• 若 $p \mid x + y$ ，则对奇数 $n$​ 有

  $$v_p\left(x^n+y^n\right)=v_p(x+y)$$

第二部分

对于奇素数 $p$​ 和任意正整数 $n$

• 若 $p \mid x - y$​ ，则

  $$v_p\left(x^n-y^n\right)=v_p(x-y)+v_p(n)$$

• 若 $p \mid x + y$ ，则对奇数 $n$​ 有

  $$v_p\left(x^n+y^n\right)=v_p(x+y)+v_p(n)$$

第三部分

若 $p = 2$ 且 $p \mid x - y$ ，则

• 对于奇数 $n$ 有

  $$v_p\left(x^n-y^n\right)=v_p(x-y)$$

• 对于偶数 $n$ 有

  $$v_p\left(x^n-y^n\right)=v_p(x-y)+v_p(x+y)+v_p(n)-1$$

对于上述 $x,y,n$ （仅第三部分），若 $4 \mid x- y$ 则

• $v_2(x+y)=1$
• $v_2\left(x^n-y^n\right)=v_2(x-y)+v_2(n)$​

---

参考文献：

[1] https://oiwiki.org/math/number-theory/lift-the-exponent/