PDA

View Full Version : Proving the impossible

tegra97
04-10-2007, 10:06 PM
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
04-11-2007, 09:39 AM
Is part of the problem missing? Maybe a modulo something or other?

tegra97
04-11-2007, 01:49 PM
No that is the problem word for word. The chapter is one Logic and Proofs and the section is Proofs Involving Quantifiers.

daon
04-11-2007, 02:28 PM
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
04-11-2007, 02:45 PM
So the way I tried to prove it is incorrect? Can you give me some tips to prove this question?

daon
04-11-2007, 03:13 PM
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 \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.