升幂引理

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

因为证明比较简单，所以本文就不写了，想知道就看参考文献[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/