1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof for k natural numbers

  1. Jan 19, 2009 #1
    Hi, how would you show that 4^(k)+4 * 9^(k) [tex]\equiv[/tex] 0 (mod 5)
    Last edited: Jan 20, 2009
  2. jcsd
  3. Jan 19, 2009 #2
    Note that 9 is congruent to 4 mod 5.
  4. Jan 20, 2009 #3
    Checking a few small values of k shows it is not always true.
  5. Jan 20, 2009 #4
    I'm pretty sure that it is, in fact, always true.
  6. Jan 20, 2009 #5
    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?
  7. Jan 20, 2009 #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: Jan 20, 2009
  8. Jan 20, 2009 #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.
  9. Jan 20, 2009 #8
    would really appreciate if someone could help me on this.
    Last edited: Jan 20, 2009
  10. Jan 20, 2009 #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].
  11. Jan 20, 2009 #10
    i know how induction works but i cant 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.
  12. Jan 20, 2009 #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.
  13. Jan 20, 2009 #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.
  14. Jan 20, 2009 #13
    I gave it to you in the earlier reply. Think harder, it should be quite obvious by now!
  15. Jan 20, 2009 #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: Jan 20, 2009
  16. Jan 20, 2009 #15
    I think holding the final answer to enable saadsarfraz to reach it would have been much better!
  17. Jan 20, 2009 #16
    This is incorrect, it is [tex] 4^k + 4 \cdot 9^k = 5m[/tex] where [tex]k,m \in \mathbb{Z} [/tex]
  18. Jan 20, 2009 #17
    Yes sorry I'll fix it
  19. Jan 20, 2009 #18
    ohhh, so this completes the proof. thank you so much.
  20. Jan 20, 2009 #19
    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.
  21. Jan 20, 2009 #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!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Proof for k natural numbers
  1. Natural numbers (Replies: 10)