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!

Is this a valid proof? (proof that if 2|n and 3|n then 6|n)

  1. Jun 9, 2015 #1
    Hi, I wasn't sure whether to post this here or in the pre-calc forum, so apologies if this is in the wrong section. I'm working through Vellemans 'How to prove it' and he gives a proof that if 2|n and 3|n then 6|n (note that a|n means a divides n, just in case this is not standard notation). I think I proved it a different way, but as he did it differently, I'm half assuming my proof is incorrect. His proof is as follows:

    "Suppose 2 | n and 3 | n. Then we can choose integers j and k such that n=2j and n=3k.
    Therefore 6(j−k)=6j−6k=3(2j)−2(3k)= 3n − 2n = n, so 6 | n."

    My "proof" is as follows:

    "Suppose 2 | n and 3 | n. Then there is an integer k such that (2)(3)k=n. Thus, (6)k=n and therefore 6 | n."

    If my proof is wrong, then could you tell me why? I was wondering if it's because my proof has something to do with the fact that every number can be written as a product of prime numbers and maybe I need to state this or something. Thanks in advance.
     
  2. jcsd
  3. Jun 9, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    The definition of "2 | n" implies there is an integer k_a so that 2 k_a = n. The definition of "3 | n" implies there is an integer k_b such that 3 k_b = n. The compound statement "2 | n and 3 | n", doesn't assert anything about an integer k such that (2)(3)k = n.
     
  4. Jun 9, 2015 #3
    Hi, thanks for the reply. I'm not sure why "2 | n and 3 | n" does not assert there is an integer k such that (2)(3)k = n. I forgot to say at the beginning that n is an arbitrary integer. I would think that if 2 and 3 both divide n, then obviously n is not prime, but can be expressed as a product of primes (2)(3) and an integer k.
     
  5. Jun 9, 2015 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The fact that 2 and 3 divide n, and 2 and 3 are prime, that is a valid proof.
     
  6. Jun 9, 2015 #5
    Ah ok, so I have to say ""Suppose 2 | n and 3 | n. As 2 and 3 are both prime, then there is an integer k such that (2)(3)k=n. Thus, (6)k=n and therefore 6 | n."

    EDIT: Also, could this be generalised to "Suppose a | n and b | n. As a and b are both prime, then there is an integer k such that abk=n. Thus, (ab)k=n and therefore ab | n."?
     
    Last edited: Jun 9, 2015
  7. Jun 9, 2015 #6
    Actually, if 2 and 3 divide a number ##n##, then since ##gcd(2,3)=1##, ##n## also divides ##2\times 3=6##.
     
    Last edited: Jun 9, 2015
  8. Jun 9, 2015 #7
    Yes, this is correct. But ##a## and ##b## don't need to be prime. As long as, ##gcd(a,b)=1## and ##a|n## and ##b|n## then, ##ab|n##.
     
  9. Jun 9, 2015 #8
    It's actually that 2 divides n, and 3 divides n, not that n divides 2 and n divides 3.
     
  10. Jun 9, 2015 #9
    whoops, sorry i replied with a brainfart
     
  11. Jun 9, 2015 #10
    Ah, yes! silly error on my part. Edited post accordingly.
     
  12. Jun 9, 2015 #11

    Stephen Tashi

    User Avatar
    Science Advisor

    You can try an argument along those lines, but you have to state it! You can't just assert that there exists a k so that (2)(3)k = n without saying why.
     
  13. Jun 9, 2015 #12
    Ok thanks, this is my first dip into proof based mathematics, so im still learning how to formulate proofs and everything. This book is great though! Thanks for all the help
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Is this a valid proof? (proof that if 2|n and 3|n then 6|n)
  1. N^2 vs. mod 3 proof (Replies: 10)

Loading...