Proving Congruence Modulo 5 for Powers of 4 and 9

[saadsarfraz]

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

 

[d_leet]

Note that 9 is congruent to 4 mod 5.

 

[robert Ihnot]

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

 

[d_leet]

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

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

 

[NoMoreExams]

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

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?

 

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

 

[saadsarfraz]

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.

 

[saadsarfraz]

would really appreciate if someone could help me on this.

 

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

 

[saadsarfraz]

i know how induction works but i can't 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.

 

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

 

[saadsarfraz]

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.

 

[wsalem]

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

 

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

 

[wsalem]

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

 

[wsalem]

NoMoreExams,

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

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

 

[NoMoreExams]

Yes sorry I'll fix it

 

[saadsarfraz]

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

 

[saadsarfraz]

at wsalem. dude thanks soo much for the help but I am doing this for the first time, i don't think i could have done it on my own.

 

[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!

 

[Mentallic]

Sorry for going off topic, but may I ask what mod stands for and how it works?

 

[wsalem]

Mentallic, you are on topic.

$$a \equiv b \mod m$$ is read "a is congruent to b modulo m". Mathematically, it means $$a - b = mk$$ (or a = mk +b) for a fixed $$m \in \mathbf{N}$$ and some $$k \in \mathbf{N}$$. In other words, $$a-b$$ is divisible by $$m$$.

 

[Mentallic]

Mentallic, you are on topic.

$$a \equiv b \mod m$$ is read "a is congruent to b modulo m". Mathematically, it means $$a - b = mk$$ (or a = mk +b) for a fixed $$m \in \mathbf{N}$$ and some $$k \in \mathbf{N}$$. In other words, $$a-b$$ is divisible by $$m$$.

Thank you wsalem