Lifting-the-exponent lemma

In elementary number theory, the lifting the exponent (LTE) lemma provides several formulas for computing the p-adic valuation ${\displaystyle \nu _{p}}$ of special forms of integers. The lemma is named as such because it describes the steps necessary to "lift" the exponent of ${\displaystyle p}$ in such expressions. It is related to Hensel's lemma.

The exact origins of the LTE lemma are unclear; it has only come into focus within the last few decades.^[1][2] Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.^[3]

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

• When ${\displaystyle p}$ is odd:
  • If ${\displaystyle p|x-y}$, ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)+\nu _{p}(n)}$.
  • If ${\displaystyle n}$ is odd and ${\displaystyle p|x+y}$, ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)}$.
• When ${\displaystyle p=2}$:
  • If ${\displaystyle 4|x-y}$, ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n)}$.
  • If ${\displaystyle 2|x-y}$, ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1}$.
• For all ${\displaystyle p}$:
  • If ${\displaystyle \gcd(n,p)=1}$, ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$.
  • If ${\displaystyle \gcd(n,p)=1}$ with ${\displaystyle n}$ odd, ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$.

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|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.

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})}$.

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|x-y}$ by writing ${\displaystyle n=2^{a}b}$ where ${\displaystyle b}$ is 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 each factor in the difference of squares step in the form ${\displaystyle x^{2^{k}}+y^{2^{k}}}$ is congruent to ${\displaystyle 2{\pmod {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|x-y}$ is proven analogously.^[1]

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}$.^[4]

Solution: Note that ${\displaystyle 149-2=3\cdot 7^{2}}$. Using the LTE lemma, since ${\displaystyle 3\nmid 149}$ and ${\displaystyle 2}$ but ${\displaystyle 3|147}$, ${\displaystyle \nu _{3}(149^{n}-2^{n})=\nu _{3}(147)+\nu _{3}(n)=\nu _{3}(n)+1}$. Thus, ${\displaystyle 3^{3}|149^{n}-2^{n}\iff 3^{2}|n}$. Similarly, ${\displaystyle 7\nmid 149,2}$ but ${\displaystyle 7|147}$, so ${\displaystyle \nu _{7}(149^{n}-2^{n})=\nu _{7}(147)+\nu _{7}(n)=\nu _{7}(n)+2}$ and ${\displaystyle 7^{7}|149^{n}-2^{n}\iff 7^{5}|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 resiudes of ${\displaystyle 149^{n}-2^{n}}$ modulo 5 cycle through the sequence ${\displaystyle 2,2,1,0}$. Thus, ${\displaystyle 5|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}|149^{n}-2^{n}\iff 5^{4}|k\iff 4\cdot 5^{4}|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.

This article, Lifting-the-exponent lemma, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary. Reviewer tools: Inform author