Lifting the exponent lemma explained for competitions

Lifting the exponent is not hard to learn. The statement is one line, and the proof is a page you can rebuild yourself. What goes wrong in a contest is the other two things: people apply it at $p = 2$ with the odd-prime formula and get a confidently wrong answer, and people fail to notice that a problem wants it at all, because the problem never says "valuation".

This is the lemma explained the way competitions test it. It gives the statement once, spends most of its time on the $p = 2$ trap, and then on recognition.

The statement

Write $v_p(x)$ for the exponent of the prime $p$ in $x$: $v_3(54) = 3$ because $54 = 2 \cdot 3^3$. Lifting the exponent (LTE) answers one question: what is $v_p(a^n - b^n)$?

For an odd prime $p$ with $p \mid a - b$, and $p$ dividing neither $a$ nor $b$:

$$v_p(a^n - b^n) = v_p(a - b) + v_p(n).$$

That is the whole lemma. The exponent of $p$ in a huge number is the exponent in a small number plus the exponent in $n$. Nothing about the size of $a^n$ matters.

A first example. How many times does $3$ divide $4^{27} - 1$? Here $a = 4$, $b = 1$, and $3 \mid 4 - 1 = 3$, with $3$ dividing neither $4$ nor $1$. So $v_3(4^{27} - 1) = v_3(3) + v_3(27) = 1 + 3 = 4$. You never wrote down a number with seventeen digits.

There is a plus version for odd $n$. If $p$ is odd, $p \mid a + b$, $p$ divides neither $a$ nor $b$, and $n$ is odd, then

$$v_p(a^n + b^n) = v_p(a + b) + v_p(n).$$

It is the minus version with $b$ replaced by $-b$, which is why $n$ has to be odd. For even $n$ it does not just change, it collapses: $a \equiv -b$ gives $a^n + b^n \equiv 2b^n \pmod p$, which is not divisible by $p$ at all.

The p = 2 trap

Every LTE mistake worth worrying about lives here. For $p = 2$, with $a$ and $b$ both odd:

• if $n$ is odd, $v_2(a^n - b^n) = v_2(a - b)$;
• if $n$ is even, $v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$.

The even case has an extra term, $v_2(a + b) - 1$, and it is never zero, because $a + b$ is even. So the odd-prime formula is not a rough version of the right answer at $p = 2$. It is wrong every single time $n$ is even.

Watch it fail. Take $v_2(3^{100} - 1)$. The odd-prime formula says $v_2(2) + v_2(100) = 1 + 2 = 3$. The real formula says $v_2(2) + v_2(4) + v_2(100) - 1 = 1 + 2 + 2 - 1 = 4$. The answer is $4$: $3^{100} - 1$ is divisible by $16$ and not by $32$.

Where does the extra term come from? From the very first factor. $3^2 - 1 = (3 - 1)(3 + 1) = 2 \cdot 4$, and that $3 + 1$ already holds two factors of $2$, not one. For odd $p$, the sum $a + b$ is never divisible by $p$ when $a - b$ is, so it never shows up. For $p = 2$, it always does.

A contest-shaped example: the largest power of $2$ dividing $5^{1024} - 1$. Here $n = 1024$ is even, so $v_2(5 - 1) + v_2(5 + 1) + v_2(1024) - 1 = 2 + 1 + 10 - 1 = 12$. The answer is $2^{12}$.

Why it is true

You will write LTE as a cited lemma, not prove it in the exam, but knowing the proof is what stops you misapplying it. It is two cases, both built on the factorisation

$$a^n - b^n = (a - b)\left(a^{n-1} + a^{n-2}b + \dots + b^{n-1}\right).$$

It is the same identity that settles why $2^n - 1$ can only be prime when $n$ is, and that drives the gcd of $2^m - 1$ and $2^n - 1$. LTE is what you get when you ask that factorisation how many factors of $p$ it holds.

Case 1. Suppose $p$ does not divide $n$. Modulo $p$ we have $a \equiv b$, so each of the $n$ terms in the bracket is $\equiv b^{n-1}$, and the bracket is $\equiv n \, b^{n-1}$. Neither $n$ nor $b$ is divisible by $p$, so the bracket is not. All the factors of $p$ sit in $a - b$, and $v_p(a^n - b^n) = v_p(a - b)$, which is the formula with $v_p(n) = 0$.

Case 2. Suppose $n = p$. Now the bracket has $p$ terms. A slightly finer count, writing $a = b + kp$ and expanding each term to first order in $kp$, shows the bracket is divisible by $p$ exactly once, provided $p$ is odd. So each factor of $p$ in $n$ adds exactly one to the valuation. Apply this $v_p(n)$ times and Case 1 to whatever is left of $n$, and the formula follows.

The condition that $p$ is odd is the whole $p = 2$ story. At $p = 2$ the bracket is $a + b$, and for $a = 3$, $b = 1$ that is $4$, divisible by $2$ twice. That is the extra term from the last section, appearing in the proof exactly where you would expect it.

This is modular thinking at its most economical: you never compute $a^n - b^n$, only what it looks like modulo $p$ and $p^2$.

When to reach for it

LTE problems rarely say "find $v_p$". They say one of these:

• The direct form. "Find the largest power of $p$ dividing …", followed by something of the shape $a^n \pm b^n$. This is the easiest one to see.
• The exponent on both sides. "Find all $n$ such that $p^k$ divides $a^n - b^n$", where the exponent $n$ appears on both sides. Whenever the unknown sits in an exponent and in the power of $p$ you are dividing by, LTE turns the divisibility into an inequality between two small numbers.
• A variable dividing itself. "$n^2$ divides $2^n + 1$" and its relatives, where a variable divides an expression in itself. These are hard, but LTE is usually the step that bounds the prime factors of $n$.
• Repeated squaring. Expressions like $3^{2^k} - 1$ or $2^{3^k} + 1$ have an exponent that is a pure prime power, which is the case LTE handles most cleanly. For instance $v_3(2^{3^k} + 1) = v_3(3) + v_3(3^k) = k + 1$, by the plus version.

Here is the second signal at work. Find all positive $n$ with $2^n \mid 3^n - 1$. If $n$ is odd, $v_2(3^n - 1) = v_2(2) = 1$, so we need $n \le 1$, which gives $n = 1$. If $n$ is even, $v_2(3^n - 1) = 1 + 2 + v_2(n) - 1 = 2 + v_2(n)$, and we need $2 + v_2(n) \ge n$. Since $v_2(n)$ grows like a logarithm and $n$ does not, this fails quickly: it holds at $n = 2$ and $n = 4$ and nowhere after. The answer is $n \in \{1, 2, 4\}$. Check the edges: $3^4 - 1 = 80$ is divisible by $16$, and $3^6 - 1 = 728$ is not divisible by $64$.

Notice that the whole problem was decided by the $p = 2$ formula. Use the odd-prime version and you get $1 + v_2(n) \ge n$, which loses $n = 4$.

When the hypothesis fails

LTE needs $p \mid a - b$. Often a problem hands you a prime that does not divide $a - b$, and the fix is to raise to the order first.

Take $v_5(2^{100} - 1)$. Since $5$ does not divide $2 - 1$, LTE does not apply as written. But $2^4 = 16 \equiv 1 \pmod 5$, and $4$ is the smallest such exponent. So rewrite $2^{100} - 1 = 16^{25} - 1$, where $5 \mid 16 - 1$. Now LTE gives $v_5(15) + v_5(25) = 1 + 2 = 3$.

The other hypothesis, that $p$ divides neither $a$ nor $b$, is the one people forget to check. If $p \mid a$ and $p \mid b$, pull out the common power of $p$ first and apply LTE to what remains. Skipping that check is how a correct formula produces a wrong number.

What to do with this

Valuation arguments are a habit more than a formula. The same move of tracking one prime at a time, rather than the whole number, is what proves the harmonic sum is never an integer, where everything turns on the single term with the largest power of $2$. LTE is that habit with a closed form attached.

To make it stick, take ten problems of the forms above and for each one write three lines only: which prime, which hypothesis you checked, and which formula you used, with $p = 2$ and even $n$ flagged every time. The problem archive has the number theory problems linked here in full, and the daily problem posts a fresh one every day if you want to keep the recognition warm.