Prove $n-m \mid n^r - m^r\,$ [Factor Theorem, monomial case]

Solution 1:

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)$.

Solution 2:

Hint $\bmod\, n-m\!:\,\ \color{#c00}{n\equiv m}\ \Rightarrow\ \color{#c00}n^r \:\equiv\: \color{#c00}m^r\ $ by Congruence Power Rule (iterated Product Rule)