升幂引理

内容

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

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

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

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

第一部分

对所有的素数 $p$ 和满足 $(n, p) = 1$ 的整数 $n$ ，

若 $p ∣ x - y$ ，则：
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y)$
若 $p ∣ x + y$ ，则对奇数 $n$ 有：
$ν_{p} (x^{n} + y^{n}) = ν_{p} (x + y)$

证明

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

\sum_{i = 0}^{n - 1} x^{i} y^{n - 1 - i} \equiv n x^{n - 1} ≢ 0 (\mod p)

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

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

第二部分

若 $p$ 是奇素数，

若 $p ∣ x - y$ ，则：
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y) + ν_{p} (n)$
若 $p ∣ x + y$ ，则对奇数 $n$ 有：
$ν_{p} (x^{n} + y^{n}) = ν_{p} (x + y) + ν_{p} (n)$

证明

若 $p ∣ x - y$ ，令 $y = x + k p$ ，我们只需证明 $p ∣ 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} (k p)^{i - j} \\ \equiv p x^{p - 1} (\mod p^{2}) \end{aligned}$
从而
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y) + 1$
若 $n = p^{a}$ ，则由数学归纳法可得
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y) + a$

因此命题得证。

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

第三部分

若 $p = 2$ 且 $p ∣ x - y$ ，

对奇数 $n$ 有（与第一部分的 1 相同）：
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y)$
对偶数 $n$ 有：
$ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y) + ν_{p} (x + y) + ν_{p} (n) - 1$

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

若 $4 ∣ x - y$ ，则：

$ν_{2} (x + y) = 1$
$ν_{2} (x^{n} - y^{n}) = ν_{2} (x - y) + ν_{2} (n)$

证明

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

令 $n = 2^{a} b$ ，其中 $a = ν_{p} (n)$ ， $2 ∤ b$ ，从而

\begin{aligned} ν_{p} (x^{n} - y^{n}) & = ν_{p} (x^{2^{a}} - y^{2^{a}}) \\ = ν_{p} ((x - y) (x + y) \prod_{i = 1}^{a - 1} (x^{2^{i}} + y^{2^{i}})) \end{aligned}

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

ν_{p} (x^{n} - y^{n}) = ν_{p} (x - y) + ν_{p} (x + y) + ν_{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 协议之条款下提供，附加条款亦可能应用