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

  • Thread starter Thread starter TalkOrigin
  • Start date Start date
  • Tags Tags
    Proof
TalkOrigin
Messages
32
Reaction score
0
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.
 
Physics news on Phys.org
TalkOrigin said:
Suppose 2 | n and 3 | n. Then there is an integer k such that (2)(3)k=n.

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.
 
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.
 
The fact that 2 and 3 divide n, and 2 and 3 are prime, that is a valid proof.
 
HallsofIvy said:
The fact that 2 and 3 divide n, and 2 and 3 are prime, that is a valid proof.

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:
Stephen Tashi said:
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.
Actually, if 2 and 3 divide a number ##n##, then since ##gcd(2,3)=1##, ##n## also divides ##2\times 3=6##.
 
Last edited:
TalkOrigin said:
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."?
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##.
 
certainly said:
Actually it does. If a number ##n## divides 2 and also divides 3, then since ##gcd(2,3)=1##, ##n## also divides ##2\times 3=6##.
It's actually that 2 divides n, and 3 divides n, not that n divides 2 and n divides 3.
 
certainly said:
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##.
whoops, sorry i replied with a brainfart
 
  • #10
Ah, yes! silly error on my part. Edited post accordingly.
 
  • #11
TalkOrigin said:
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.

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.
 
  • #12
Stephen Tashi said:
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.
Ok thanks, this is my first dip into proof based mathematics, so I am still learning how to formulate proofs and everything. This book is great though! Thanks for all the help
 
Back
Top