# Proof for k natural numbers

1. Jan 19, 2009

Hi, how would you show that 4^(k)+4 * 9^(k) $$\equiv$$ 0 (mod 5)

Last edited: Jan 20, 2009
2. Jan 19, 2009

### d_leet

Note that 9 is congruent to 4 mod 5.

3. Jan 20, 2009

### robert Ihnot

Checking a few small values of k shows it is not always true.

4. Jan 20, 2009

### d_leet

I'm pretty sure that it is, in fact, always true.

5. Jan 20, 2009

### NoMoreExams

It is? If we have

$$4^{k+4} \cdot 9^{k}$$

Then letting $$k = 0$$ we get

$$4^{0+4} \cdot 9^{0} = 256$$

That is certainly not 0 mod 5. Next letting $$k = 1$$ we get

$$4^{1+4} \cdot 9^{1} = 9216$$

Also not 0 mod 5?

6. Jan 20, 2009

### wsalem

Actually, what he meant was $$4^k + 4*9^k \equiv 0 \text{mod} 5$$.

Hint. Try induction over $$k$$. You may rephrase it to: for every $$k \in N$$, there's an $$n \in N$$ such that $$4^k + 4*9^k = 5n$$.

Last edited: Jan 20, 2009
7. Jan 20, 2009

sorry for the typo i corrected it. so if i use induction than its easy for the base case K=0 which gives me 5 congruent 0 mod 5 which is true. Now, wsalem wrote that expression using the relationship a=mn+b with b=0. Now how am I supposed to use induction for k in this case when there is also n present.

8. Jan 20, 2009

would really appreciate if someone could help me on this.

Last edited: Jan 20, 2009
9. Jan 20, 2009

### wsalem

Define $$P(k)$$ as the statement: $$4^k + 4*9^k = 5n$$ for some $$n \in N$$

For the inductive step.
Suppose $$P(k)$$ hold, i.e there is an $$n \in N$$ such that : $$4^k + 4*9^k = 5n$$.
Then you need to show that P(k+1) also holds, i.e there is an $$m \in N$$ such that $$4^{k+1} + 4*9^{k+1} = 5m$$.

10. Jan 20, 2009

i know how induction works but i cant figure out what specific 4^k expression do i have to add/multiply to $$4^{k+1} + 4*9^{k+1} = 5m$$ make it work for m+1.

11. Jan 20, 2009

### wsalem

No, you are missing the point of induction here! It is k we want to run induction over, not m, so it is pointless to say "m+1". The existence of a such m is merely for the statement P(k) to hold at a particular case.

Inductive step:
Suppose P(k) holds, then $$4^k = 5n - 4*9^k$$
Now $$4^{k+1} + 4*9^{k+1} = ....$$

now, for P(k+1) to hold, you must show that $$4^{k+1} + 4*9^{k+1} = 5*m$$ for some integer m.

12. Jan 20, 2009

sorry i didnt mean m+1. What i'm saying is that there is some expression involving k which must be multiplied on either side of the equation. I don't know what that expression is.

13. Jan 20, 2009

### wsalem

I gave it to you in the earlier reply. Think harder, it should be quite obvious by now!

14. Jan 20, 2009

### NoMoreExams

You know that

$$4^k + 4 \cdot 9^k = 5m, k,m \in \mathbb{Z}$$

Now we want to show that

$$4^{l+1} + 4 \cdot 9^{l+1} = 5n, l, n \in \mathbb{Z}$$

So let's work with our expression

$$4^{l+1} + 4 \cdot 9^{l+1} = 4 \cdot 4^l + 4 \cdot 9 \cdot 9^l = 4 \cdot 4^l + 4 \cdot (4+5) \cdot 9^l = 4 \cdot 4^l + 4^{2} \cdot 9^l + 4 \cdot 5 \cdot 9^l = 4 \left(4^l + 4 \cdot 9^l) + 5 \cdot 4 \cdot 9^l$$

The first part you know is divisible by 5 from the hypothesis, the 2nd part has a factor of 5 so obviously it is too.

Last edited: Jan 20, 2009
15. Jan 20, 2009

### wsalem

I think holding the final answer to enable saadsarfraz to reach it would have been much better!

16. Jan 20, 2009

### wsalem

NoMoreExams,
This is incorrect, it is $$4^k + 4 \cdot 9^k = 5m$$ where $$k,m \in \mathbb{Z}$$

17. Jan 20, 2009

### NoMoreExams

Yes sorry I'll fix it

18. Jan 20, 2009

ohhh, so this completes the proof. thank you so much.

19. Jan 20, 2009

at wsalem. dude thanks soo much for the help but im doing this for the first time, i dont think i could have done it on my own.

20. Jan 20, 2009

### wsalem

No problem. But now that you have seen it done. I think you'd be better off rewriting the whole proof!

Here's another quite similar problem, for practice sake

Prove that
$$5^{2n} \equiv 1\mod 8$$

It should be routine by now!