Proving Congruence Modulo 5 for Powers of 4 and 9

In summary: Back on topic, for the proof of 5^{2n} \equiv 1\mod 8, we can use induction.Base case: n=0, 5^{2(0)} = 5^0 = 1 which is congruent to 1 modulo 8.Inductive step:Assume 5^{2k} \equiv 1\mod 8 holds for some k \in \mathbf{N}, i.e. 5^{2k} = 8m + 1 for some m \in \mathbf{N}.Then we want to show that 5^{2(k+1)} \equiv 1\mod 8, i.e. 5
  • #1
saadsarfraz
86
1
Hi, how would you show that 4^(k)+4 * 9^(k) [tex]\equiv[/tex] 0 (mod 5)
 
Last edited:
Physics news on Phys.org
  • #2
Note that 9 is congruent to 4 mod 5.
 
  • #3
Checking a few small values of k shows it is not always true.
 
  • #4
robert Ihnot said:
Checking a few small values of k shows it is not always true.

I'm pretty sure that it is, in fact, always true.
 
  • #5
d_leet said:
I'm pretty sure that it is, in fact, always true.

It is? If we have

[tex] 4^{k+4} \cdot 9^{k} [/tex]

Then letting [tex] k = 0 [/tex] we get

[tex] 4^{0+4} \cdot 9^{0} = 256 [/tex]

That is certainly not 0 mod 5. Next letting [tex] k = 1 [/tex] we get

[tex] 4^{1+4} \cdot 9^{1} = 9216 [/tex]

Also not 0 mod 5?
 
  • #6
Actually, what he meant was [tex]4^k + 4*9^k \equiv 0 \text{mod} 5[/tex].

Hint. Try induction over [tex]k[/tex]. You may rephrase it to: for every [tex]k \in N[/tex], there's an [tex]n \in N[/tex] such that [tex]4^k + 4*9^k = 5n[/tex].
 
Last edited:
  • #7
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
would really appreciate if someone could help me on this.
 
Last edited:
  • #9
Define [tex]P(k)[/tex] as the statement: [tex]4^k + 4*9^k = 5n[/tex] for some [tex]n \in N[/tex]

For the inductive step.
Suppose [tex]P(k)[/tex] hold, i.e there is an [tex]n \in N[/tex] such that : [tex]4^k + 4*9^k = 5n[/tex].
Then you need to show that P(k+1) also holds, i.e there is an [tex]m \in N[/tex] such that [tex]4^{k+1} + 4*9^{k+1} = 5m[/tex].
 
  • #10
i know how induction works but i can't figure out what specific 4^k expression do i have to add/multiply to [tex]
4^{k+1} + 4*9^{k+1} = 5m
[/tex] make it work for m+1.
 
  • #11
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 [tex]4^k = 5n - 4*9^k[/tex]
Now [tex]4^{k+1} + 4*9^{k+1} = ...[/tex]

now, for P(k+1) to hold, you must show that [tex]4^{k+1} + 4*9^{k+1} = 5*m[/tex] for some integer m.
 
  • #12
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
I gave it to you in the earlier reply. Think harder, it should be quite obvious by now!
 
  • #14
You know that

[tex] 4^k + 4 \cdot 9^k = 5m, k,m \in \mathbb{Z} [/tex]

Now we want to show that

[tex] 4^{l+1} + 4 \cdot 9^{l+1} = 5n, l, n \in \mathbb{Z} [/tex]

So let's work with our expression

[tex] 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 [/tex]

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:
  • #15
I think holding the final answer to enable saadsarfraz to reach it would have been much better!
 
  • #16
NoMoreExams,
NoMoreExams said:
You know that
[tex] 4^k + 4 \cdot 9^k = 5k, k \in \mathbb{Z} [/tex]

This is incorrect, it is [tex] 4^k + 4 \cdot 9^k = 5m[/tex] where [tex]k,m \in \mathbb{Z} [/tex]
 
  • #17
Yes sorry I'll fix it
 
  • #18
ohhh, so this completes the proof. thank you so much.
 
  • #19
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.
 
  • #20
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
[tex]5^{2n} \equiv 1\mod 8[/tex]

It should be routine by now!
 
  • #21
Sorry for going off topic, but may I ask what mod stands for and how it works?
 
  • #22
Mentallic, you are on topic.

[tex]a \equiv b \mod m[/tex] is read "a is congruent to b modulo m". Mathematically, it means [tex]a - b = mk[/tex] (or a = mk +b) for a fixed [tex]m \in \mathbf{N}[/tex] and some [tex]k \in \mathbf{N}[/tex]. In other words, [tex]a-b[/tex] is divisible by [tex]m[/tex].
 
Last edited:
  • #23
wsalem said:
Mentallic, you are on topic.

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

Thank you wsalem :smile:
 

What is "Proof for k natural numbers"?

"Proof for k natural numbers" is a mathematical concept that involves providing evidence or logical reasoning to show that a statement is true for all natural numbers up to a given value, k.

Why is "Proof for k natural numbers" important?

"Proof for k natural numbers" is important because it allows us to establish the validity of a statement for a specific range of natural numbers, rather than just a few examples. This helps us to make generalizations and deductions about mathematical concepts.

What are some common techniques used in "Proof for k natural numbers"?

Some common techniques used in "Proof for k natural numbers" include mathematical induction, contradiction, and direct proof. Each of these methods involves using logical reasoning and mathematical principles to demonstrate the truth of a statement for all natural numbers up to k.

What are the challenges of "Proof for k natural numbers"?

One of the main challenges of "Proof for k natural numbers" is finding the most efficient and effective method to demonstrate the truth of a statement for all natural numbers up to k. This often requires creativity and a deep understanding of mathematical concepts.

How can "Proof for k natural numbers" be applied in real-world situations?

"Proof for k natural numbers" can be applied in various real-world situations, such as in computer programming, to ensure that a program will work properly for all possible inputs. It can also be used in scientific research to validate theories and hypotheses that involve natural numbers.

Similar threads

Replies
11
Views
366
  • Precalculus Mathematics Homework Help
Replies
5
Views
936
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
653
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
833
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
917
  • Precalculus Mathematics Homework Help
Replies
3
Views
713
  • Linear and Abstract Algebra
Replies
4
Views
948
Back
Top