Lifting The Exponent Lemma

**Step 1: Reduce to the case $n=p$ via multiplicativity.** Write $n = p^{v_p(n)} \cdot m$ with $p \nmid m$. Repeated application of the $n=p$ case (proved below) to $a^m, b^m$ in place of $a,b$ shows $v_p(a^n-b^n) = v_p((a^m)^{p^{v_p(n)}} - (b^m)^{p^{v_p(n)}}) = v_p(a^m-b^m) + v_p(n)$, so it suffices to prove $v_p(a^m - b^m) = v_p(a-b)$ whenever $p \nmid m$, and to prove the base step $v_p(a^p-b^p) = v_p(a-b)+1$.

Step 2: Prove the base step using the factorization. Factor $a^p - b^p = (a-b)(a^{p-1}+a^{p-2}b+\cdots+b^{p-1})$. We must show the second factor $S = \sum_{j=0}^{p-1} a^{p-1-j}b^j$ has $v_p(S) = 1$.

**Step 3: Show $p \mid S$.** Since $p \mid a-b$, we have $a \equiv b \pmod p$, so each term $a^{p-1-j}b^j \equiv b^{p-1-j}b^j = b^{p-1} \pmod p$. Summing all $p$ terms, $S \equiv p\cdot b^{p-1} \equiv 0 \pmod p$ (using $p \nmid b$), so $p \mid S$.

**Step 4: Show $p^2 \nmid S$.** Write $a = b + pt$ for integer $t$ (possible since $p\mid a-b$). Expand each term $a^{p-1-j}b^j = (b+pt)^{p-1-j}b^j \equiv b^{p-1-j}b^j + (p-1-j)pt\, b^{p-2-j}b^j \pmod{p^2}$ (binomial expansion, dropping terms with $p^2$ or higher). Summing over $j=0,\dots,p-1$: the leading terms sum to $p\,b^{p-1}$ as before, and the correction terms sum to $pt\,b^{p-2}\sum_{j=0}^{p-1}(p-1-j) = pt\,b^{p-2}\cdot\frac{p(p-1)}{2}$, which is divisible by $p^2$ (since $p$ is odd, $\frac{p-1}{2}$ is an integer, so this correction is $p^2\cdot(\text{integer})$, hence $\equiv 0 \pmod{p^2}$). So $S \equiv p\,b^{p-1} \pmod{p^2}$, and since $p \nmid b$, $p\,b^{p-1}$ is divisible by $p$ but not $p^2$, giving $v_p(S)=1$.

Step 5: Combine. From Steps 2–4, $v_p(a^p-b^p) = v_p(a-b) + v_p(S) = v_p(a-b)+1$. Combined with the reduction in Step 1 (and the fact $v_p(a^m-b^m)=v_p(a-b)$ when $p\nmid m$, provable the same way since then $S \equiv m\,b^{m-1} \not\equiv 0 \pmod p$), induction on $v_p(n)$ gives $v_p(a^n-b^n) = v_p(a-b)+v_p(n)$ for all positive integers $n$.