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
    NoMoreExams,
    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)

Loading...