AIOJ

Content

The Lift the Exponent (LTE) lemma is a theorem commonly used in elementary number theory.

Define $\nu_p(n)$ as the exponent of the prime factor $p$ in the standard factorization of integer $n$ ; that is, $\nu_p(n)$ satisfies $p^{\nu_p(n)}\mid n$ and $p^{\nu_p(n)+1}\nmid n$ .

Because the LTE lemma is lengthy, we divide it into three parts:

In what follows, let $p$ be prime, let $x,y$ be integers satisfying $p\nmid x$ and $p\nmid y$ , and let $n$ be a positive integer.

Part I

For every prime $p$ and integer $n$ satisfying $(n,p)=1$ :

If $p\mid x-y$ , then:
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)$
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$ , then it is easy to see that $p\mid x-y\iff x\equiv y\pmod p$ , so clearly:

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

It follows from $x^n-y^n=(x-y)\sum_{i=0}^{n-1}x^iy^{n-1-i}$ that the statement is proved.

The case $p\mid x+y$ is proved similarly.

Part II

If $p$ is an odd prime:

If $p\mid x-y$ , then:
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(n)$
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 $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}$
Therefore:
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+1$
If $n=p^a$ , mathematical induction gives:
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+a$

Therefore, the statement is proved.

The case $p\mid x+y$ is proved similarly.

Part III

If $p=2$ and $p\mid x-y$ :

For odd $n$ (the same as item 1 of Part I):
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)$
For even $n$ :
$\nu_p\left(x^n-y^n\right)=\nu_p(x-y)+\nu_p(x+y)+\nu_p(n)-1$

In addition, 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 $p\nmid \dbinom{p}{2}$ in this case, we cannot use the method from Part II.

Let $n=2^a b$ , where $a=\nu_p(n)$ and $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$ , so $(\forall i\geq 1),~~x^{2^i}+y^{2^i}\equiv 2\pmod 4$ . Thus the equation above becomes:

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

Therefore, the statement is proved.

References

Lifting-the-exponent lemma - Wikipedia

Lifting the Exponent Lemma

Content

Part I

Part II

Part III

References