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.

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}$ 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\mid x-y}$, ${\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}$, ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)}$.
• When ${\displaystyle p=2}$:
  • If ${\displaystyle 4\mid x-y}$, ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n)}$.
  • If ${\displaystyle 2\mid 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)}$.

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

1. Pavardi, A. H. (2011). Lifting The Exponent Lemma (LTE). Retrieved July 11, 2020, from http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.5543 (Note: The old link to the paper is broken; try https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/lifting-the-exponent.pdf instead.)
2. Gauss, C. (1801) Disquisitiones arithmeticae. Results shown in Articles 86–87. https://gdz.sub.uni-goettingen.de/id/PPN235993352?tify={%22pages%22%3A%5B70%5D}
3. Geretschläger, R. (2020). Engaging Young Students in Mathematics through Competitions – World Perspectives and Practices. World Scientific. https://books.google.com/books?id=FNPkDwAAQBAJ&lpg=PA3&ots=rkjtruFbsM&lr&pg=PP1
4. Heuberger, C. and Mazzoli, M. (2017). Elliptic curves with isomorphic groups of points over finite field extensions. Journal of Number Theory, 181, 89–98. https://doi.org/10.1016/j.jnt.2017.05.028
5. 2020 AIME I Problems. (2020). Art of Problem Solving. Retrieved July 11, 2020, from https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems