Proving the impossible

[tegra97]

Prove that if there exist integers m and n such that 12m+15n=1 then m and n are both positive.

Hello I'm having some difficulties with this proof. First of all I know that there doesn't exist an integer for this to be true. Because the gcd of 12 and 15 is 3, and 3 divides the left but not the right. Since this is a if and then statement P=>Q if P is "there exist an integer that m and n such that 12m+15n=1" then P is false so that makes m and n are both positive???

 

[tkhunny]

Is part of the problem missing? Maybe a modulo something or other?

 

[tegra97]

No that is the problem word for word. The chapter is one Logic and Proofs and the section is Proofs Involving Quantifiers.

 

[daon]

tegra97, just because the statment is true, does not make the conclusion true. For example, here is another true statement: "If the world is flat then I'm very rich." Unfortunately, even though that statement is true, I have very little money.

Statements like these with a nosense hypothesis are said to be true "by default" even though they don't make much sense in every-day language.

 

[tegra97]

So the way I tried to prove it is incorrect? Can you give me some tips to prove this question?

 

[daon]

If you prove that the hypothesis is false then you've shown the statement to be true.

One way would be to prove the contrapositive: "If m and n are negative, then 12m + 15n \(\displaystyle \neq\) 1."

edit: Also, if you've ever delved into number theory, the term "relatively prime" might ring a bell. The linear combination you have suggests that 12 and 15 are relatively prime, which they are not.