Lifting-the-exponent lemma

Statement

Let $p$ be an odd prime, let $x$ and $y$ be integers with $p \nmid x$, $p \nmid y$ and $p \mid x - y$, and let $n$ be a positive integer. Then $\nu_p(x^n - y^n) = \nu_p(x - y) + \nu_p(n)$, where $\nu_p$ is the p-adic valuation.

Remarks

For $p = 2$ the formula needs a stronger hypothesis. If $x$ and $y$ are odd and $4 \mid x - y$, then $\nu_2(x^n - y^n) = \nu_2(x - y) + \nu_2(n)$. For $p = 2$, odd $x$ and $y$, and even $n$, the general formula is $\nu_2(x^n - y^n) = \nu_2(x - y) + \nu_2(x + y) + \nu_2(n) - 1$. For example, $\nu_3(10^9 - 1) = \nu_3(9) + \nu_3(9) = 4$, and indeed $10^9 - 1 = 3^4 \cdot 37 \cdot 333667$.

History

Édouard Lucas had some of the ideas by 1878. Mihai Manea published the modern form in 2006.

Explanations

L1 human

When $p$ divides $x - y$, the lemma tells you exactly how many factors $p$ are in $x^n - y^n$. You add the factors $p$ of $x - y$ and the factors $p$ of $n$. Olympiad problems often use the lemma.