Lifting-the-exponent lemma

Template:Short description In elementary number theory, the lifting-the-exponent lemma provides several formulas for computing the [[p-adic valuation|Template:Mvar-adic valuation]] ${\nu }_p$ of binomial expressions which are differences of powers of integers: that is, how many factors of a prime $p$ are present. The lemma describes the steps necessary to "lift" the exponent of $p$ in such expressions. It is related to Hensel's lemma. It is often used in mathematical olympiads.

History

By 1878, some ideas in the lemma had appeared in the work of mathematician Édouard Lucas, who was then a professor at Lycée Charlemagne. Lucas described related divisibility results (with a minor error in the case $p=2$).

In 2006, Romanian mathematician Mihai Manea first published the modern and systematic formulation of the lemma, especially in the context of olympiad mathematics.

By 2011, the lemma had become well-known in the math olympiad folklore, particularly through its use on mathematics forums such as the Art of Problem Solving.

Statements

For a prime number $p$, let ${\nu }_p(x)=k$, where $p^k$ is the highest power of $p$ which is a divisor of $x$, so that $p^k\mid x,p^{k+1}\nmid x$. For any integers $x$ and $y$ with $p\nmid x$ and $p\nmid y$, and a positive integer $n$, 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 $\frac{x^n-y^n}{x-y}$ is an integer.

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⟺x\equiv y(\mathrm{mod}p)$, Template:NumBlk

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 (Template:EquationNote) to show that ${\nu }_p(x^p-y^p)={\nu }_p(x-y)+1$ because the quantity in (Template:EquationNote) is a multiple of $p$ but not $p^2$. Likewise, ${\nu }_p(x^p+y^p)={\nu }_p(x+y)+1$.

Then, if $n$ is written as $p^{a}b$ 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{array}{cc}{\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{array}$

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 $(\genfrac{}{}{0ex}{}{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^{a}b$ where $a$ and $b$ are integers with $b$ odd and noting that

$\begin{array}{cc}{\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{array}$

because $x\equiv y\equiv \pm 1(\mathrm{mod}4)$ implies that each factor of the form $x^{2^k}+y^{2^k}$ in the difference-of-squares step 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.

Example problem

Problem 12 of the March 2020 AIME:

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

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⟺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⟺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(\mathrm{mod}25)$, ${\nu }_5(149^4-2^4)=1$. Hence $5^5\mid 149^n-2^n⟺5^4\mid k⟺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.