Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
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$.
