# Math Help - Divisibility Proofs

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

2. ## Re: Divisibility Proofs

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.

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

4. ## Re: Divisibility Proofs

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

5. ## 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?

6. ## 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.

7. ## Re: Divisibility Proofs

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.

8. ## Re: Divisibility Proofs

Ok. Thank you.