Divisibillity Proof - what do I do next

spearfish · #1 $Old$ April 26th, 2009, 04:00 PM

I am trying to prove that if n is natural number, then 5^n - 3^n is divisible by 3.

Ok, so this is the work I have so far:

a / b iff a =bk
n mod 3 = 0,1, 2
so we have the following cases:
n=3k
n=3k+1
n=3k+2

Case 1: n = 3k
5^n - 3^n = 5^(3k) - 3^(3k)
??
??

From here, I don't know what to do next. What does this tell me and how do I prove divisibility by 3?

Plato · #2 $Old$ April 26th, 2009, 04:31 PM

Quote:

Originally Posted by spearfish $View Post$

I am trying to prove that if n is natural number, then 5^n - 3^n is divisible by 3.

It ain't true if $n=1$ .

spearfish · #3 $Old$ April 26th, 2009, 05:17 PM

You're right. I overlooked this.
Ok, so what if we had 5^n - 2^n. How would I prove divisibility by 3.

CaptainBlack · #4 $Old$ October 9th, 2009, 01:27 AM

Quote:

Originally Posted by spearfish $View Post$

You're right. I overlooked this.
Ok, so what if we had 5^n - 2^n. How would I prove divisibility by 3.

Start by observing that:

$5^{2n} \equiv 1 \text{ mod } 3$

$2^{2n} \equiv 1 \text{ mod } 3$

so:

$5^{2n}-2^{2n}\equiv 0 \text{ mod } 3$

Also

$5^{2n+1} \equiv 2 \text{ mod } 3$

$2^{2n+1} \equiv 2 \text{ mod } 3$

so:

$5^{2n+1}-2^{2n+1}\equiv 0 \text{ mod } 3$

So we see that for any integer $k$ :

$5^{k}-2^{2k}\equiv 0 \text{ mod } 3$

CB