Proof that a number evenly divides the difference of two numbers to the nth power I have tried to prove that $9^n - 4^n \equiv 0 \pmod{5}$.
At first I started out with considering the cases when $n$ is even and when it's odd and then show that the resulting expressions are congruent with $0 \pmod{5}$, but i think the proof can be shortened even further:
$$
9^n - 4^n \equiv (-1)^n - (-1)^n
$$
No matter what value $n$ takes, $a - a = 0$ for all $a$, QED.
Is this reasoning solid?
 A: Your second proof is of course much better. It's actually enough to notice that $4=9\, ( \text{mod } 5)$ hence their n-th powers must also be equal.
A: Yes, your proof is valid.
But if in general one wishes to prove $a^n - b^n \equiv 0 \mod (a - b)$ ....
Well, $a - b \equiv 0 \mod (a-b)$
$a \equiv b \mod(a-b)$
$a^n \equiv b^n \mod(a-b)$
$a^n - b^n \equiv 0 \mod(a-b)$
Yeah, your proof is good... Really good.
Ultimately one will want to show $(a -b)\sum_{i=0}^{n-1} a^ib^{n-i-1} = a^n - b^n$. (i.e. not merely the divisor but that quotient as well.)  But in the meantime your proof is slick.
A: You can prove this by induction.

First, show that this is true for $n=1$:
$9^{1}-4^{1}=5$
Second, assume that this is true for $n$:
$9^{n}-4^{n}=5k$
Third, prove that this is true for $n+1$:
$9^{n+1}-4^{n+1}=$
$9\cdot9^{n}-4\cdot4^{n}=$
$5\cdot9^{n}+4\cdot9^{n}-4\cdot4^{n}=$
$5\cdot9^{n}+4\cdot(\color\red{9^{n}-4^{n}})=$
$5\cdot9^{n}+4\cdot\color\red{5k}=$
$5\cdot(9^{n}+4k)$

Please note that the assumption is used only in the part marked red.
A: This is a consequence of the identity
$$
a^n-b^n = (a-b)(a^{n-1}+a^{n-2}b + \cdots + ab^{n-1}+b^{n-2})
$$
It also follows from the binomial theorem. Take $d=a-b$. Then $d$ divides $a^n-b^n$ because
$$
a^n = (d+b)^n = du+b^n
$$
for some integer $u$.
The identity above gives $u$ explicitly but this is not needed to prove that $d$ divides $a^n-b^n$.
