algebra precalculus - Prove that $(n-m) mid (n^r - m^r)$

In respect to a larger proof I need to prove that $(n-m) \mid (n^r - m^r) $ (where $\mid$ means divides, i.e., $a \mid b$ means that $b$ modulus $a$ = $0$). I have played around with this for a while now but to no avail and would be grateful if you could help me.

Answer

There are several ways of proving this. For example, one can use the binomial theorem $(a+b)^r=\sum_{k=1}^r\binom{k}ra^kb^{n-k}$ with $a=n-m$ and $b=m$. (The change of variables from $n,m$ to $a,b$ is in itself a good idea in problems like this, since it tends to reduce the size of some of the expressions.)

Another way is to use the identity $$n^r-m^r=(n-m)\sum_{k=0}^{r-1}n^{r-1-k}m^k=(n-m)(n^{r-1}+n^{r-2}m+\dots+nm^{r-2}+m^{r-1}).$$

Both of these identities are proved by induction on $r$.

Or, one can do directly an inductive argument: The result is clear if $r=0$, since $n^r-m^r=0$. Given the result for $r$, prove it for $r+1$ using, for example, that $n^{r+1}-m^{r+1}=n(n^r-m^r)+m^r(n-m)$.