Proof that a number evenly divides the difference of two numbers to the nth power

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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