Divisibility Proofs

Printable View

July 7th 2012, 05:45 AM
GrigOrig99

Divisibility Proofs

Having a bit of trouble with this one. At the point marked A, I'm not sure I'm going in the right direction. Immediately after that line I have B, which I'm showing as a possible alternative, but I'm unsure of that approach as well. Can anyone help me work out which, if either, of the two methods is correct?

Many thanks.

Q. $9^n-5^n$ is divisible by 4, for $n\in\mathbb{N}_0$

Attempt: Step 1: For $n=1$ ...
$9^1-5^1=4$ , which can be divided by $4$ .
Therefore, $n=1$ is true...

Step 2: For $n=k$ ...
Assume $9^k-5^k=4\mathbb{Z}$ , where $\mathbb{Z}$ is an integer...1
Show that $n=k+1$ is true...
i.e. $9^{k+1}-5^{k+1}$ can be divided by $4$
$9^{k+1}-5^{k+1}$ => $9^1\cdot9^k-5^1\cdot5^k$ =>

A $(9-5)[9^k-5^k]$ => $4[4\mathbb{Z}]$ ...from 1 above => $4[4\mathbb{Z}]$ , which can be divided by 4

B $9[4\mathbb{Z}-5^k]-5[9^k-4\mathbb{Z}]$

Thus, assuming $n=k$ , we can say $n=k+1$ is true & true for $n=2,3,$ ... & all $n\in\mathbb{N}_0$
July 7th 2012, 06:04 AM
Plato

Re: Divisibility Proofs

Quote:

Originally Posted by GrigOrig99

Having a bit of trouble with this one. At the point marked A, I'm not sure I'm going in the right direction. Immediately after that line I have B, which I'm showing as a possible alternative, but I'm unsure of that approach as well. Can anyone help me work out which, if either, of the two methods is correct?
Q. $9^n-5^n$ is divisible by 4, for $n\in\mathbb{N}_0$

Attempt: Step 1: For $n=1$ ...
$9^1-5^1=4$ , which can be divided by $4$ .
Therefore, $n=1$ is true...

$9^{k+1}-5^{k+1}= 9^{k+1}-9\cdot 5^{k}+ 9\cdot 5^{k}-5^{k+1}.$
Now factor.
July 7th 2012, 08:22 AM
GrigOrig99

Re: Divisibility Proofs

Ok, this is what I end up with but I've basically gone around in a circle...
$9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $9.9^k-5.5^k$
July 7th 2012, 08:50 AM
Plato

Re: Divisibility Proofs

Quote:

Originally Posted by GrigOrig99

Ok, this is what I end up with but I've basically gone around in a circle...
$9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $9.9^k-5.5^k$

It is easy. $9^{k+1}-9\cdot 5^{k}+ 9\cdot 5^{k}-5^{k+1}=9(9^k-5^k)+5^k(9-5)$

You know that both $(9^k-5^k)~\&~(9-5)$ are divisible by $4$ .
July 7th 2012, 09:05 AM
GrigOrig99

Re: Divisibility Proofs

So $9(9^k-5^k)+5^k(9-5)$ => $9(4\mathbb{Z})+5^k(4)$ => $36\mathbb{Z}+5^k\cdot4$ => $4(9\mathbb{Z}+5^k)$

That leaves me with the 5^k though...Is that permitted, or am I still missing something?
July 7th 2012, 09:12 AM
richard1234

Re: Divisibility Proofs

An alternate solution: $9 \equiv 1 (\mod 4)$ so $9^n \equiv 1 (\mod 4)$ . Similarly, $5^n \equiv 1 (\mod 4)$ .

Therefore $9^n - 5^n \equiv 1 - 1 \equiv 0 (\mod 4)$ so it must be a multiple of 4.
July 7th 2012, 09:19 AM
Plato

Re: Divisibility Proofs

Quote:

Originally Posted by GrigOrig99

So $9(9^k-5^k)+5^k(9-5)$ => $9(4\mathbb{Z})+5^k(4)$ => $36\mathbb{Z}+5^k\cdot4$ => $4(9\mathbb{Z}+5^k)$

That leaves me with the 5^k though...Is that permitted, or am I still missing something?

The sum of two multiples of four is a multiple of four.
$9(9^k-5^k)+5^k(9-5)$ is the sum of two multiples of four.
July 7th 2012, 09:22 AM
GrigOrig99

Re: Divisibility Proofs

Ok. Thank you.