升幂引理

内容

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

定义 $\nu_p(n)$ 为整数的标准分解中素因子的幂次，即 $\nu_p(n)$ 满足 $p^{\nu_p(n)}\mid n$ 且 $p^{\nu_p(n)+1}\nmid n$ .

由于升幂引理内容较长，我们将其分为三部分介绍：

以下内容设为素数，为满足 $p\nmid x$ 且 $p\nmid y$ 的整数，为正整数。

第一部分

对所有的素数和满足的整数，

若 $p\mid x-y$ ，则：
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)$
若 $p\mid x+y$ ，则对奇数有：
$\nu_p\left(x^n+y^n\right)=\nu_p(x+y)$

证明

若 $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\mid x-y$ ，则：
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(n)$
若 $p\mid x+y$ ，则对奇数有：
$\nu_p\left(x^n+y^n\right)=\nu_p(x+y)+\nu_p(n)$

证明

若 $p\mid x-y$ ，令，我们只需证明 $p\mid n$ 的情况。

若，则由二项式定理：
$\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$
若，则由数学归纳法可得
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+a$

因此命题得证。

对 $p\mid x+y$ 的情况证明方法类似。

第三部分

若且 $p\mid x-y$ ，

对奇数有（与第一部分的 1 相同）：
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)$
对偶数有：
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1$

另外对上述的，我们有：

若 $4\mid x-y$ ，则：

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

证明

我们只需证明为偶数的情况。由于此时 $p\nmid \dbinom{p}{2}$ ，故我们不能用第二部分的方法证明。

令，其中 $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

因此命题得证。

参考资料

Lifting-the-exponent lemma - Wikipedia

本页面最近更新：2024/12/16 13:10:29，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：c-forrest, Enter-tainer, Great-designer, iamtwz, Tiphereth-A, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用