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.

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?

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.

Powered by vBulletin® Version 4.2.2 Copyright © 2014 vBulletin Solutions, Inc. All rights reserved.