Lifting-the-exponent lemma

In elementary number theory, the lifting-the-exponent lemma (LTE 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

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. However, several key ideas used in its proof were known to Gauss and referenced in his Disquisitiones Arithmeticae. Despite chiefly featuring in mathematical olympiads, it is sometimes applied to research topics, such as elliptic curves.

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$, 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

LTE has been generalized to complex values of $x,y$ provided that the value of $\frac{x^n-y^n}{x-y}$ is 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)$,

$x^{n-1}+x^{n-2}y+x^{n-3}{y}^2+\dots +y^{n-1}\equiv n{x}^{n-1}\equiv ̸0(\mathrm{mod}p)$ (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.

General case (odd p)

Via the binomial expansion, the substitution $y=x+kp$ can be used in (1) to show that ${\nu }_p(x^p-y^p)={\nu }_p(x-y)+1$ because (1) 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{gathered} \begin{array}{rl}{\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} \end{gathered}$$

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}{rl}{\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 since $x\equiv y\equiv \pm 1(\mathrm{mod}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 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\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 LTE lemma, since $3\nmid 149$ and $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 LTE 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.