Lifting The Exponent Lemma

Content

The Lifting-the-exponent lemma (LTE) is a commonly used theorem in elementary number theory.

Define \(\nu_p(n)\) as the exponent of the prime factor \(p\) in the prime factorization of the integer \(n\), i.e., \(\nu_p(n)\) satisfies \(p^{\nu_p(n)}\mid n\) and \(p^{\nu_p(n)+1}\nmid n\).

Since the LTE lemma is relatively long, we introduce it in three parts:

In the following, let \(p\) be a prime number, \(x,y\) be integers satisfying \(p\nmid x\) and \(p\nmid y\), and \(n\) be a positive integer.

Part 1

For all prime numbers \(p\) and integers \(n\) satisfying \((n,p)=1\),

1. If \(p\mid x-y\), then:

   \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y) \]

2. If \(p\mid x+y\), then for odd \(n\):

   \[ \nu_p\left(x^n+y^n\right)=\nu_p(x+y) \]

Proof

If \(p\mid x-y\), it is not hard to see that \(p\mid x-y\iff x\equiv y\pmod p\), then obviously:

\[ \sum_{i=0}^{n-1}x^iy^{n-1-i}\equiv nx^{n-1}\not\equiv 0\pmod p \]

Then from \(x^n-y^n=(x-y)\sum_{i=0}^{n-1}x^iy^{n-1-i}\), the proposition is proved.

The proof for the case \(p\mid x+y\) is similar.

Part 2

If \(p\) is an odd prime,

1. If \(p\mid x-y\), then:

   \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(n) \]

2. If \(p\mid x+y\), then for odd \(n\):

   \[ \nu_p\left(x^n+y^n\right)=\nu_p(x+y)+\nu_p(n) \]

Proof

If \(p\mid x-y\), let \(y=x+kp\), we only need to prove the case where \(p\mid n\).

• If \(n=p\), then by the binomial theorem:

  \[ \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} \]

  Thus

  \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+1 \]

• If \(n=p^a\), then by mathematical induction we obtain

  \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+a \]

Therefore the proposition is proved.

The proof for the case \(p\mid x+y\) is similar.

Part 3

If \(p=2\) and \(p\mid x-y\),

1. For odd \(n\) (same as Part 1, 1):

   \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y) \]

2. For even \(n\):

   \[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1 \]

Additionally, for the above \(x,y,n\), we have:

If \(4\mid x-y\), then:

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

Proof

We only need to prove the case where \(n\) is even. Since in this case \(p\nmid \dbinom{p}{2}\), we cannot use the method from Part 2.

Let \(n=2^a b\), where \(a=\nu_p(n)\), \(2\nmid b\), then

\[ \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} \]

Note that \(2\mid x-y\implies 4\mid x^2-y^2\), thus \((\forall i\geq 1),~~x^{2^i}+y^{2^i}\equiv 2\pmod 4\), so the above expression can be transformed into:

\[ \nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1 \]

Therefore the proposition is proved.

References

1. Lifting-the-exponent lemma - Wikipedia

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用