升幂引理

内容

升幂（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$，

1. 若 $p\mid x-y$，则：

   $${\nu }_p(x^n-y^n)={\nu }_p(x-y)$$

2. 若 $p\mid x+y$，则对奇数 $n$ 有：

   $${\nu }_p(x^n+y^n)={\nu }_p(x+y)$$

证明

若 $p\mid x-y$，则不难发现 $p\mid x-y⟺x\equiv y(\mathrm{mod}p)$，则显然有：

$$\sum _{i=0}^{n-1}{x}^i{y}^{n-1-i}\equiv n{x}^{n-1}\not\equiv 0(\mathrm{mod}p)$$

进而由 $x^n-y^n=(x-y)\sum _{i=0}^{n-1}{x}^i{y}^{n-1-i}$ 可知命题得证。

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

第二部分

若 $p$ 是奇素数，

1. 若 $p\mid x-y$，则：

   $${\nu }_p(x^n-y^n)={\nu }_p(x-y)+{\nu }_p(n)$$

2. 若 $p\mid x+y$，则对奇数 $n$ 有：

   $${\nu }_p(x^n+y^n)={\nu }_p(x+y)+{\nu }_p(n)$$

第三部分

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

1. 对奇数 $n$ 有（与第一部分的 1 相同）：

   $${\nu }_p(x^n-y^n)={\nu }_p(x-y)$$

2. 对偶数 $n$ 有：

   $${\nu }_p(x^n-y^n)={\nu }_p(x-y)+{\nu }_p(x+y)+{\nu }_p(n)-1$$

另外对上述的 $x,y,n$，我们有：

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

• ${\nu }_2(x+y)=1$
• ${\nu }_2(x^n-y^n)={\nu }_2(x-y)+{\nu }_2(n)$

证明

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

令 $n=2^{a}b$，其中 $a={\nu }_p(n)$，$2\nmid b$，从而

$$\begin{array}{rl}{\nu }_p(x^n-y^n)& ={\nu }_p(x^{2^a}-y^{2^a})\\ & ={\nu }_p((x-y)(x+y)\prod _{i=1}^{a-1}(x^{2^i}+y^{2^i}))\end{array}$$

注意到 $2\mid x-y⟹4\mid x^2-y^2$，从而 $(\mathrm{\forall }i\ge 1),x^{2^i}+y^{2^i}\equiv 2(\mathrm{mod}4)$，进而上式可变为：

$${\nu }_p(x^n-y^n)={\nu }_p(x-y)+{\nu }_p(x+y)+{\nu }_p(n)-1$$

因此命题得证。

参考资料

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 协议之条款下提供，附加条款亦可能应用