Lifting the Exponent

The Key Result

Why It Works

1. 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. 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. 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. 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. 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

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