Contents

Lifting-the-exponent lemma

Background

The exact origins of the LTE lemma are unclear; the result, with its present name and form, has only come into focus within the last 10 to 20 years.^[1] However, several key ideas used in its proof were known to Gauss and referenced in his Disquisitiones Arithmeticae.^[2] Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.^[3][4]

Statements

For any integers ${\displaystyle x,y}$, a positive integer ${\displaystyle n}$, and a prime number ${\displaystyle p}$ such that ${\displaystyle p\nmid x}$ and ${\displaystyle p\nmid y}$, the following statements hold:

• When ${\displaystyle p}$ is odd:
  • If${\displaystyle p\mid x-y}$, then ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)+\nu _{p}($n)} .
  • If${\displaystyle n}$ is odd and ${\displaystyle p\mid x+y}$, then ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}($n)} .
• When ${\displaystyle p=2}$:
  • If${\displaystyle 2\mid x-y}$ and ${\displaystyle n}$ is even, then ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}($n)-1} .
  • If${\displaystyle 2\mid x-y}$ and ${\displaystyle n}$ is odd, then ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)}$. (Follows from the general case below.)
  • Corollaries:
    • If${\displaystyle 4\mid x-y}$, then ${\displaystyle \nu _{2}(x+y)=1}$ and thus ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}($n)} .
    • If${\displaystyle 2\mid x+y}$ and ${\displaystyle n}$ is even, then ${\displaystyle \nu _{2}(x^{n}+y^{n})=1}$.
    • If${\displaystyle 2\mid x+y}$ and ${\displaystyle n}$ is odd, then ${\displaystyle \nu _{2}(x^{n}+y^{n})=\nu _{2}(x+y)}$.
• For all ${\displaystyle p}$:
  • If${\displaystyle \gcd(n,p)=1}$ and ${\displaystyle p\mid x-y}$, then ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$.
  • If${\displaystyle \gcd(n,p)=1}$, ${\displaystyle p\mid x+y}$ and ${\displaystyle n}$ odd, then ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$.

Outline of proof

Base case

The base case ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$ when ${\displaystyle \gcd(n,p)=1}$ is proven first. Because ${\displaystyle p\mid x-y\iff x\equiv y{\pmod {p}}}$,

${\displaystyle x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1}\equiv nx^{n-1}\not \equiv 0{\pmod {p}}\ ($1)}

The fact that ${\displaystyle x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1})}$ completes the proof. The condition ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$ for odd ${\displaystyle n}$ is similar.

General case (odd p)

Via the binomial expansion, the substitution ${\displaystyle y=x+kp}$ can be used in (1) to show that ${\displaystyle \nu _{p}(x^{p}-y^{p})=\nu _{p}(x-y)+1}$ because (1) is a multiple of ${\displaystyle p}$ but not ${\displaystyle p^{2}}$.^[1] Likewise, ${\displaystyle \nu _{p}(x^{p}+y^{p})=\nu _{p}(x+y)+1}$.

Then, if ${\displaystyle n}$ is written as ${\displaystyle p^{a}b}$ where ${\displaystyle p\nmid b}$, the base case gives ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}((x^{p^{a}})^{b}-(y^{p^{a}})^{b})=\nu _{p}(x^{p^{a}}-y^{p^{a}})}$. By induction on ${\displaystyle a}$,

${\displaystyle {\begin{aligned}\nu _{p}(x^{p^{a}}-y^{p^{a}})&=\nu _{p}(((\dots (x^{p})^{p}\dots ))^{p}-((\dots (y^{p})^{p}\dots ))^{p})\ {\text{(exponentiation used }}a{\text{ times per term)}}\\&=\nu _{p}(x-y)+a\end{aligned}}}$

A similar argument can be applied for ${\displaystyle \nu _{p}(x^{n}+y^{n})}$.

General case (p = 2)

The proof for the odd ${\displaystyle p}$ case cannot be directly applied when ${\displaystyle p=2}$ because the binomial coefficient ${\displaystyle {\binom {p}{2}}={\frac {p(p-1)}{2}}}$ is only an integral multiple of ${\displaystyle p}$ when ${\displaystyle p}$ is odd.

However, it can be shown that ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}($n)} when ${\displaystyle 4\mid x-y}$ by writing ${\displaystyle n=2^{a}b}$ where ${\displaystyle a}$ and ${\displaystyle b}$ are integers with ${\displaystyle b}$ odd and noting that

${\displaystyle {\begin{aligned}\nu _{2}(x^{n}-y^{n})&=\nu _{2}((x^{2^{a}})^{b}-(y^{2^{a}})^{b})\\&=\nu _{2}(x^{2^{a}}-y^{2^{a}})\\&=\nu _{2}((x^{2^{a-1}}+y^{2^{a-1}})(x^{2^{a-2}}+y^{2^{a-2}})\cdots (x^{2}+y^{2})(x+y)(x-y))\\&=\nu _{2}(x-y)+a\end{aligned}}}$

because since ${\displaystyle x\equiv y\equiv \pm 1{\pmod {4}}}$, each factor in the difference of squares step in the form ${\displaystyle x^{2^{k}}+y^{2^{k}}}$ is congruent to 2 modulo 4.

The stronger statement ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}($n)-1} when ${\displaystyle 2\mid x-y}$ is proven analogously.^[1]

In competitions

Example problem

The LTE lemma can be used to solve 2020 AIME I #12:

Let ${\displaystyle n}$ be the least positive integer for which ${\displaystyle 149^{n}-2^{n}}$ is divisible by ${\displaystyle 3^{3}\cdot 5^{5}\cdot 7^{7}.}$ Find the number of positive integer divisors of ${\displaystyle n}$.^[5]

Solution. Note that ${\displaystyle 149-2=147=3\cdot 7^{2}}$. Using the LTE lemma, since ${\displaystyle 3\nmid 149}$ and ${\displaystyle 2}$ but ${\displaystyle 3\mid 147}$, ${\displaystyle \nu _{3}(149^{n}-2^{n})=\nu _{3}(147)+\nu _{3}($n)=\nu _{3}(n)+1} . Thus, ${\displaystyle 3^{3}\mid 149^{n}-2^{n}\iff 3^{2}\mid n}$. Similarly, ${\displaystyle 7\nmid 149,2}$ but ${\displaystyle 7\mid 147}$, so ${\displaystyle \nu _{7}(149^{n}-2^{n})=\nu _{7}(147)+\nu _{7}($n)=\nu _{7}(n)+2} and ${\displaystyle 7^{7}\mid 149^{n}-2^{n}\iff 7^{5}\mid n}$.

Since ${\displaystyle 5\nmid 147}$, the factors of 5 are addressed by noticing that since the residues of ${\displaystyle 149^{n}}$ modulo 5 follow the cycle ${\displaystyle 4,1,4,1}$ and those of ${\displaystyle 2^{n}}$ follow the cycle ${\displaystyle 2,4,3,1}$, the residues of ${\displaystyle 149^{n}-2^{n}}$ modulo 5 cycle through the sequence ${\displaystyle 2,2,1,0}$. Thus, ${\displaystyle 5\mid 149^{n}-2^{n}}$ iff ${\displaystyle n=4k}$ for some positive integer ${\displaystyle k}$. The LTE lemma can now be applied again: ${\displaystyle \nu _{5}(149^{4k}-2^{4k})=\nu _{5}((149^{4})^{k}-(2^{4})^{k})=\nu _{5}(149^{4}-2^{4})+\nu _{5}($k)} . Since ${\displaystyle 149^{4}-2^{4}\equiv (-1)^{4}-2^{4}\equiv -15{\pmod {25}}}$, ${\displaystyle \nu _{5}(149^{4}-2^{4})=1}$. Hence ${\displaystyle 5^{5}\mid 149^{n}-2^{n}\iff 5^{4}\mid k\iff 4\cdot 5^{4}\mid n}$.

Combining these three results, it is found that ${\displaystyle n=2^{2}\cdot 3^{2}\cdot 5^{4}\cdot 7^{5}}$, which has ${\displaystyle (2+1)(2+1)(4+1)(5+1)=270}$ positive divisors.

References