Lifting-the-exponent lemma

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.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.) However, several key ideas used in its proof were known to Gauss and referenced in his Disquisitiones Arithmeticae.Gauss, C. (1801) [https://gdz.sub.uni-goettingen.de/id/PPN235993352?tify={%22pages%22%3A%5B70%5D} Disquisitiones arithmeticae.] Results shown in Articles 86–87. 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

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

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

LTE has been generalized to complex values of $x,\; y$ provided that the value of $\backslash 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].

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

{{NumBlk|:|$x^\{n-1\}+x^\{n-2\}y+x^\{n-3\}y^2+\backslash dots+y^\{n-1\}\; \backslash equiv\; nx^\{n-1\}\; \backslash not\backslash equiv\; 0\; \backslash 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+\backslash dots+y^\{n-1\})$ completes the proof. The condition $\backslash nu\_p(x^n+y^n)\; =\; \backslash 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.

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

Then, if $n$ is written as $p^ab$ where $p\; \backslash nmid\; b$, the base case gives $\backslash nu\_p(x^n-y^n)\; =\; \backslash nu\_p((x^\{p^a\})^b-(y^\{p^a\})^b)\; =\; \backslash 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 $\backslash nu\_p(x^n+y^n)$.

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

However, it can be shown that $\backslash nu\_2(x^n-y^n)\; =\; \backslash nu\_2(x-y)+\backslash nu\_2(n)$ when $4\; \backslash 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\; \backslash equiv\; y\; \backslash equiv\; \backslash pm\; 1\; \backslash 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 $\backslash nu\_2(x^n-y^n)\; =\; \backslash nu\_2(x-y)+\backslash nu\_2(x+y)+\backslash nu\_2(n)-1$ when $2\; \backslash mid\; x-y$ is proven analogously.

The LTE 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\backslash cdot5^5\backslash 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\backslash cdot\; 7^2$. Using the LTE lemma, since $3\; \backslash nmid\; 149$ and $3\; \backslash nmid\; 2$, but $3\; \backslash mid\; 147$, $\backslash nu\_3(149^n-2^n)\; =\; \backslash nu\_3(147)+\backslash nu\_3(n)\; =\; \backslash nu\_3(n)+1$. Thus, $3^3\; \backslash mid\; 149^n-2^n\; \backslash iff\; 3^2\; \backslash mid\; n$. Similarly, $7\; \backslash nmid\; 149,2$ but $7\; \backslash mid\; 147$, so $\backslash nu\_7(149^n-2^n)\; =\; \backslash nu\_7(147)+\backslash nu\_7(n)\; =\; \backslash nu\_7(n)+2$ and $7^7\; \backslash mid\; 149^n-2^n\; \backslash iff\; 7^5\; \backslash mid\; n$.

Since $5\; \backslash 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\; \backslash mid\; 149^n-2^n$ iff $n\; =\; 4k$ for some positive integer $k$. The LTE lemma can now be applied again: $\backslash nu\_5(149^\{4k\}-2^\{4k\})\; =\; \backslash nu\_5((149^4)^k-(2^4)^k)\; =\; \backslash nu\_5(149^4-2^4)+\backslash nu\_5(k)$. Since $149^4-2^4\; \backslash equiv\; (-1)^4-2^4\; \backslash equiv\; -15\; \backslash pmod\{25\}$, $\backslash nu\_5(149^4-2^4)\; =\; 1$. Hence $5^5\; \backslash mid\; 149^n-2^n\; \backslash iff\; 5^4\; \backslash mid\; k\; \backslash iff\; 4\backslash cdot\; 5^4\; \backslash mid\; n$.

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

{{reflist|colwidth=30em}}

Category:Lemmas in number theory