Number TheoryDifficulty 65-100214 tagged problems

Lifting the Exponent

Lifting the Exponent is the habit of computing prime valuations of expressions like $a^n-b^n$ under useful hypotheses. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$v_p\!\left(a^n - b^n\right) = v_p(a - b) + v_p(n) \quad \text{for odd prime } p,\ p \mid a - b,\ p \nmid a, p \nmid b$$

When an odd prime $p$ divides $a - b$ but not $a$ or $b$, the Lifting the Exponent lemma gives the exact power of $p$ dividing $a^n - b^n$ in one line.

Why It Works

1
Goal (odd prime $p$, $p \mid a - b$, $p \nmid a$, $p \nmid b$, and $a \ne b$): $v_p(a^n - b^n) = v_p(a - b) + v_p(n)$.
2
Case $p \nmid n$. Write $a^n - b^n = (a - b)\,S$ with $S = \sum_{i=0}^{n-1} a^i b^{n-1-i}$. Since $a \equiv b \pmod p$, each term $a^i b^{n-1-i} \equiv a^{n-1} \pmod p$, so $S \equiv n\,a^{n-1} \pmod p$. As $p \nmid n$ and $p \nmid a$, we get $p \nmid S$, hence $v_p(a^n - b^n) = v_p(a - b)$.
3
Key sub-step $v_p(a^p - b^p) = v_p(a - b) + 1$. Now $a^p - b^p = (a - b)\,T$ with $T = \sum_{i=0}^{p-1} a^i b^{p-1-i}$. Put $t = v_p(a - b) \ge 1$ and write $a = b + cp^t$ with $p \nmid c$. Expanding $a^i \equiv b^i + i\,b^{i-1} c p^t \pmod{p^{t+1}}$ gives $T \equiv \sum_{i=0}^{p-1}\!\big(b^{p-1} + i\,b^{p-2} c p^t\big) = p\,b^{p-1} + c p^t b^{p-2}\tfrac{p(p-1)}{2} \pmod{p^{t+1}}$.
4
Because $p$ is odd, $\tfrac{p(p-1)}{2}$ is a multiple of $p$, so the second term is $\equiv 0 \pmod{p^{t+1}}$ and $T \equiv p\,b^{p-1} \pmod{p^{t+1}}$. In particular $T \equiv p\,a^{p-1} \pmod{p^2}$ with $p \nmid a^{p-1}$, so $v_p(T) = 1$ exactly and $v_p(a^p - b^p) = v_p(a - b) + 1$.
5
Induction on $v_p(n)$. Write $n = p^k m$ with $p \nmid m$. Applying the sub-step to the pair $a^{p^j}, b^{p^j}$ (which still satisfies the hypotheses) for $j = 0, \dots, k-1$ gives $v_p\!\left(a^{p^k} - b^{p^k}\right) = v_p(a - b) + k$. Then $a^n - b^n = \left(a^{p^k}\right)^m - \left(b^{p^k}\right)^m$ with $p \nmid m$, so the first case applies: $v_p(a^n - b^n) = v_p\!\left(a^{p^k} - b^{p^k}\right) = v_p(a - b) + k = v_p(a - b) + v_p(n)$.

Worked Examples

Example 1

Find the largest power of $3$ dividing $10^{9} - 1$.

1
Take $p = 3$, $a = 10$, $b = 1$, $n = 9$. Check hypotheses: $3 \mid (10 - 1)$, and $3 \nmid 10$, $3 \nmid 1$.
2
Apply LTE: $v_3(10^9 - 1) = v_3(10 - 1) + v_3(9)$.
3
Compute the two pieces separately: the base term $v_3(10 - 1) = v_3(9) = v_3(3^2) = 2$, and the exponent term $v_3(n) = v_3(9) = 2$. The total is $2 + 2 = 4$.
4
So $3^4 = 81$ divides $10^9 - 1 = 999999999$ but $3^5$ does not (indeed $999999999 / 81 = 12345679$, whose digit sum $37$ is not a multiple of $3$).

Answer:

$3^4 = 81$

Warm-up

Find the exact power of $7$ dividing $8^{2025} - 1$.

1
Take $p = 7$, $a = 8$, $b = 1$, $n = 2025$. Check the hypotheses: $7 \mid (8 - 1)$, and $7 \nmid 8$, $7 \nmid 1$, with $p = 7$ odd.
2
Apply LTE: $v_7(8^{2025} - 1) = v_7(8 - 1) + v_7(2025)$.
3
Compute $v_7(8 - 1) = v_7(7) = 1$, and $2025 = 3^4 \cdot 5^2$ has no factor of $7$, so $v_7(2025) = 0$.
4
Total: $1 + 0 = 1$, so $7^1 \mid 8^{2025} - 1$ but $7^2 \nmid 8^{2025} - 1$.

Answer:

$7^1 = 7$

Contest level

Find the largest power of $2$ dividing $7^{100} - 1$.

1
Here $p = 2$, which needs the special $p = 2$ form of LTE. For odd $a, b$ and EVEN exponent $n$: $v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$.
2
Both $a = 7$, $b = 1$ are odd and $n = 100$ is even, so the formula applies.
3
Compute the pieces: $v_2(7 - 1) = v_2(6) = 1$, $v_2(7 + 1) = v_2(8) = 3$, and $v_2(100) = 2$.
4
Total: $1 + 3 + 2 - 1 = 5$, so $2^5 = 32$ divides $7^{100} - 1$ but $2^6$ does not.

Answer:

$2^5 = 32$

Olympiad / Challenge

Find all positive integers $n$ such that $2^n \mid 3^n - 1$.

1
We need $v_2(3^n - 1) \ge n$. Split on the parity of $n$, since the $p = 2$ LTE behaves differently for odd vs even exponents.
2
If $n$ is odd: $v_2(3^n - 1^n) = v_2(3 - 1) = 1$ (for odd exponents only the base difference matters). The condition $1 \ge n$ forces $n = 1$, which works ($2 \mid 3 - 1 = 2$).
3
If $n$ is even: the $p=2$ form gives $v_2(3^n - 1) = v_2(3 - 1) + v_2(3 + 1) + v_2(n) - 1 = 1 + 2 + v_2(n) - 1 = 2 + v_2(n)$. The condition is $n \le 2 + v_2(n)$.
4
Write $n = 2^k m$ with $m$ odd ($k \ge 1$), so $v_2(n) = k$ and we need $2^k m \le 2 + k$. For $m \ge 3$ already $2^k m \ge 6 > 2 + k$; for $m = 1$: $2^k \le 2 + k$ holds only for $k = 1$ ($2 \le 3$) and $k = 2$ ($4 \le 4$), giving $n = 2, 4$. Check: $3^2 - 1 = 8$ ($2^2 \mid 8$ ✓), $3^4 - 1 = 80 = 2^4 \cdot 5$ ($2^4 \mid 80$ ✓). So the solutions are $n \in \{1, 2, 4\}$.

Answer:

$n \in \{1, 2, 4\}$

Going Deeper

Generalization: there is a matching LTE for sums. For an odd prime $p$ with $p \mid a + b$, $p \nmid a, b$, and ODD $n$: $v_p(a^n + b^n) = v_p(a + b) + v_p(n)$. Both the difference and sum versions are really one statement about $v_p$ of $a^n \pm b^n$ once you account for the sign and parity.
Where it appears: pinning the exact prime power in $a^n \pm b^n$, solving exponential Diophantine equations (e.g. $a^x - b^y = c$) by comparing valuations on each side, proving order/period facts, and divisibility problems like '$2^n \mid 3^n - 1$'.
Pitfall: the $p = 2$ case is the classic trap. The clean formula $v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1$ requires $a, b$ ODD and $n$ EVEN; for $n$ odd it collapses to $v_2(a^n - b^n) = v_2(a - b)$. Applying the odd-prime formula at $p = 2$ gives wrong answers. Also always verify $p \mid a - b$ (for the difference) but $p \nmid a$ and $p \nmid b$ before invoking LTE at all.

Spot the Signal

Look for problems where the key step is computing prime valuations of expressions like $a^n-b^n$ under useful hypotheses.
You can describe the hard part as computing prime valuations of expressions like $a^n-b^n$ under useful hypotheses, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for lifting the exponent, then rewrite the givens around it.
Name the relation that makes Lifting the Exponent legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Lifting the Exponent just because the surface looks familiar; verify the required condition first.
Applying Lifting the Exponent because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let lifting the exponent reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is computing prime valuations of expressions like $a^n-b^n$ under useful hypotheses.