Lifting-the-exponent lemma

In elementary number theory, the lifting-the-exponent (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.^[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 $x,y$ and positive integers $n$ and $p$ , where $p$ is a prime such that $p\nmid x$ and $p\nmid y$ , the following identities hold:

When $p$ $p$ is odd:
- If $p\mid x-y$ , $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)+\nu _{p}(n)$ .
- If $n$ is odd and $p\mid x+y$ , $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)$ .
When $p=2$ $p=2$ :
- If $4\mid x-y$ , $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n)$ .
- If $2\mid x-y$ and $n$ is even, $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1$ .
For all $p$ $p$ :
- If $\gcd(n,p)=1$ and $p\mid x-y$ , $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)$ .
- If $\gcd(n,p)=1$ , $p\mid x+y$ and $n$ odd, $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)$ .

Outline of proof

Base case

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

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 $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}$ .^[1] 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{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 $\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^{a}b$ where $a$ and $b$ are integers with $b$ odd and noting that

{\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 $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.^[1]

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$ .^[5]

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}\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 resiudes 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{\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$ .