= Lifting-the-exponent lemma
{wiki}
For an odd prime $p$, integers $x,y$ with $p\mid x-y$ and $p\nmid xy$, and a positive integer $n$ with $x^n\ne y^n$, the lifting-the-exponent lemma gives
$$
v_p(x^n-y^n)=v_p(x-y)+v_p(n).
$$
Here $v_p$ is the <prime valuation>. The divisibility and unit hypotheses cannot be dropped.
Write $x=y+a$ with $v_p(a)\geq1$. In the binomial expansion of $(y+a)^p-y^p$, the first term $py^{p-1}a$ has valuation $v_p(a)+1$, while every later term has greater valuation. Thus raising to the $p$th power increases the difference valuation by exactly one. An exponent coprime to $p$ leaves it unchanged; factoring $n=p^rm$ proves the formula.
For example, $v_3(4^9-1)=v_3(3)+v_3(9)=3$. At $p=2$ a separate rule is needed: for odd $x,y$ and even $n$, $v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1$. It gives $v_2(3^4-1)=1+2+2-1=4$, showing why the odd-prime formula alone is insufficient.
Back to article page
