Lifting-the-exponent lemma

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

Background

Although this lemma has been rediscovered many times and is now part of mathematical "folklore", its ideas appear as early as 1878 in the work of Édouard Lucas,É. Lucas, "Théorie des Fonctions Numériques Simplement Périodiques. [Continued]", American Journal of Mathematics, vol. 1 (1878), pp. 197–240. https://www.jstor.org/stable/2369308 who was then a professor at Lycée Charlemagne. Lucas described related divisibility results (with a minor error in the case p = 2). However, the modern and systematic formulation of the lemma, especially in the context of olympiad mathematics, was first published by Romanian mathematician Mihai Manea in 2006.M. Manea, "Some a^n ± b^n Problems in Number Theory", Mathematics Magazine, vol. 79, no. 2, April 2006, pp. 140–145. https://web.archive.org/web/20200322064554/https://www.maa.org/sites/default/files/mathmag140-145-manea44299.pdf The lemma has since become widely known by the informal name "LTE" (short for "Lifting The Exponent"), particularly through its use on mathematics forums such as the Art of Problem Solving. Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.Geretschläger, R. (2020). Engaging Young Students in Mathematics through Competitions – World Perspectives and Practices. World Scientific. https://books.google.com/books?id=FNPkDwAAQBAJ&pg=PP1Heuberger, 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

Statements

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

When $p$ is odd:
If $p \mid x-y$ , then $\nu_p(x^n-y^n) = \nu_p(x-y)+\nu_p(n)$ .
If $p \mid x+y$ and $n$ is odd, then $\nu_p(x^n+y^n) = \nu_p(x+y)+\nu_p(n)$ .
If $p \mid x+y$ and $n$ is even, then $\nu_p(x^n+y^n) = 0$ .
When $p = 2$ :
If $2 \mid x-y$ and $n$ is even, then $\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 = \nu_2\left(\frac{x^2-y^2}{2}\right)+\nu_2(n)$ .
If $2 \mid x-y$ and $n$ is odd, then $\nu_2(x^n-y^n) = \nu_2(x-y)$ . (Follows from the general case below.)
Corollaries:
If $4 \mid x-y$ , and if both x and y are odd, then $\nu_2(x+y)=1$ and thus $\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(n)$ .
If $2 \mid x+y$ and $n$ is even, then $\nu_2(x^n+y^n) = 1$ .
If $2 \mid x+y$ and $n$ is odd, then $\nu_2(x^n+y^n) = \nu_2(x+y)$ .
For all $p$ :
If $p \mid x-y$ and $p \nmid n$ , then $\nu_p(x^n-y^n) = \nu_p(x-y)$ .
If $p \mid x+y$ , $p \nmid n$ and $n$ is odd, then $\nu_p(x^n+y^n) = \nu_p(x+y)$ .

Generalizations

The lifting-the-exponent lemma has been generalized to complex values of $x, y$ provided that the value of $\tfrac{x^n-y^n}{x-y}$ is integer.S. Riasat, [https://sriasat.wordpress.com/wp-content/uploads/2014/10/general-lte.pdf Generalising `LTE' and application to Fibonacci-type sequences].

Proof outline

= Base case =

The base case $\nu_p(x^n-y^n) = \nu_p(x-y)$ when $p \nmid n$ is proven first. Because $p \mid x-y \iff x \equiv y \pmod{p}$ ,

{{NumBlk|:| $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}$ |{{EquationRef|1}}}}

The fact that $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 $\nu_p(x^n+y^n) = \nu_p(x+y)$ for odd $n$ is similar, where we observe that the proof above holds for integers $x$ and $y$ , and therefore we can substitute $-y$ for $y$ above to obtain the desired result.

= General case (odd ''p'') =

Via the binomial expansion, the substitution $y = x+kp$ can be used in ({{EquationNote|1}}) to show that $\nu_p(x^p-y^p) = \nu_p(x-y)+1$ because ({{EquationNote|1}}) is a multiple of $p$ but not $p^2$ .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.) Likewise, $\nu_p(x^p+y^p) = \nu_p(x+y)+1$ .

Then, if $n$ is written as $p^ab$ where $p \nmid b$ , the base case gives $\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 $a$ ,

: $\begin{align}
\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{align}$

A similar argument can be applied for $\nu_p(x^n+y^n)$ .

= General case (''p'' = 2) =

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

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

: $\begin{align}
\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{align}$

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

The stronger statement $\nu_2(x^n-y^n) = \nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1$ when $2 \mid x-y$ is proven analogously.

In competitions

= Example problem =

The lifting-the-exponent lemma can be used to solve 2020 AIME I #12:

Let $n$ be the least positive integer for which $149^n-2^n$ is divisible by $3^3\cdot5^5\cdot7^7.$ Find the number of positive integer divisors of $n$ .2020 AIME I Problems. (2020). Art of Problem Solving. Retrieved July 11, 2020, from https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems

Solution. Note that $149-2 = 147 = 3\cdot 7^2$ . Using the lifting-the-exponent lemma, since $3 \nmid 149$ and $3 \nmid 2$ , but $3 \mid 147$ , $\nu_3(149^n-2^n) = \nu_3(147)+\nu_3(n) = \nu_3(n)+1$ . Thus, $3^3 \mid 149^n-2^n \iff 3^2 \mid n$ . Similarly, $7 \nmid 149,2$ but $7 \mid 147$ , so $\nu_7(149^n-2^n) = \nu_7(147)+\nu_7(n) = \nu_7(n)+2$ and $7^7 \mid 149^n-2^n \iff 7^5 \mid n$ .

Since $5 \nmid 147$ , the factors of 5 are addressed by noticing that since the residues of $149^n$ modulo 5 follow the cycle $4,1,4,1$ and those of $2^n$ follow the cycle $2,4,3,1$ , the residues of $149^n-2^n$ modulo 5 cycle through the sequence $2,2,1,0$ . Thus, $5 \mid 149^n-2^n$ iff $n = 4k$ for some positive integer $k$ . The lemma can now be applied again: $\nu_5(149^{4k}-2^{4k}) = \nu_5((149^4)^k-(2^4)^k) = \nu_5(149^4-2^4)+\nu_5(k)$ . Since $149^4-2^4 \equiv (-1)^4-2^4 \equiv -15 \pmod{25}$ , $\nu_5(149^4-2^4) = 1$ . Hence $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 $n = 2^2\cdot 3^2\cdot 5^4\cdot 7^5$ , which has $(2+1)(2+1)(4+1)(5+1) = 270$ positive divisors.

References

Category:Lemmas in number theory