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. $\displaystyle 9^n-5^n$ is divisible by 4, for $\displaystyle n\in\mathbb{N}_0$

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

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

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

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

Thus, assuming $\displaystyle n=k$, we can say $\displaystyle n=k+1$ is true & true for $\displaystyle n=2,3,$... & all $\displaystyle 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. $\displaystyle 9^n-5^n$ is divisible by 4, for $\displaystyle n\in\mathbb{N}_0$

Attempt: Step 1: For $\displaystyle n=1$...
$\displaystyle 9^1-5^1=4$, which can be divided by $\displaystyle 4$.
Therefore, $\displaystyle n=1$ is true...
$\displaystyle 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...
$\displaystyle 9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $\displaystyle 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $\displaystyle 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 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...
$\displaystyle 9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $\displaystyle 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $\displaystyle 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 9.9^k-5.5^k$
It is easy. $\displaystyle 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 $\displaystyle (9^k-5^k)~\&~(9-5)$ are divisible by $\displaystyle 4$.

5. ## Re: Divisibility Proofs

So $\displaystyle 9(9^k-5^k)+5^k(9-5)$ => $\displaystyle 9(4\mathbb{Z})+5^k(4)$ => $\displaystyle 36\mathbb{Z}+5^k\cdot4$ => $\displaystyle 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: $\displaystyle 9 \equiv 1 (\mod 4)$ so $\displaystyle 9^n \equiv 1 (\mod 4)$. Similarly, $\displaystyle 5^n \equiv 1 (\mod 4)$.

Therefore $\displaystyle 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 $\displaystyle 9(9^k-5^k)+5^k(9-5)$ => $\displaystyle 9(4\mathbb{Z})+5^k(4)$ => $\displaystyle 36\mathbb{Z}+5^k\cdot4$ => $\displaystyle 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.
$\displaystyle 9(9^k-5^k)+5^k(9-5)$ is the sum of two multiples of four.

8. ## Re: Divisibility Proofs

Ok. Thank you.