11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your proof is better. $\endgroup$ – Qing Zhang Sep 19 '16 at 17:52
  • $\begingroup$ There are many good answers, and I'm not sure which one to accept yet. I'll wait a day or so and let the upvotes influence my decision. $\endgroup$ – sara Sep 19 '16 at 18:42
  • $\begingroup$ Don't let the upvotes influence my decision. Choose the answer that best explains it to you. $\endgroup$ – lhf Sep 19 '16 at 19:13
8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It's cool that there are several approaches, but I think I like the modular arithmetic proofs more, they seem more elegant. $\endgroup$ – sara Sep 19 '16 at 18:39
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.