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 <br /> 4^{k+1} + 4*9^{k+1} = 5m<br /> 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