Expert: Paul Klarreich - 10/6/2008

Question
QUESTION: Prove by contradiction that there do not exist integers m and n such that 42m + 385n = 100.

ANSWER: Questioner:   Pete
Category:  Advanced Math
 
Subject:  Math Foundations-Proofs
Question:  Prove by contradiction that there do not exist integers m and n such that 42m + 385n = 100.
.................................
Hi, Pete,

It is hard for me to provide a suitable response if I don't know what you are studying.  If you don't understand the following, send me more details and I'll try again.

42m + 385n = 7(6m + 55n)

That should do it.


---------- FOLLOW-UP ----------

QUESTION: I'm not sure what further information you need. I am taking a Math Foundations class and we are doing proofs. Proofs by contradiction, contrapositive, etc... The book is called A Transition to Advanced Mathematics. I hope this helps.

Answer
Questioner:   Pete
Category:  Advanced Math
Private:  No
 
Subject:  Divisibility
Question:  QUESTION: Prove by contradiction that there do not exist integers m and n such that 42m + 385n = 100.

ANSWER: Questioner:   Pete
Category:  Advanced Math

Subject:  Math Foundations-Proofs
Question:  Prove by contradiction that there do not exist integers m and n such that 42m + 385n = 100.
.................................
Hi, Pete,

It is hard for me to provide a suitable response if I don't know what you are studying.  If you don't understand the following, send me more details and I'll try again.

42m + 385n = 7(6m + 55n)

That should do it.


---------- FOLLOW-UP ----------

QUESTION: I'm not sure what further information you need. I am taking a Math Foundations class and we are doing proofs. Proofs by contradiction, contrapositive, etc... The book is called A Transition to Advanced Mathematics. I hope this helps.
.......................................
Hi, Pete,

OK, sounds like a good book.  In case you were not able to fill in the details of the proof, it goes like this:

Assume there ARE integers m,n, satisfying  42m + 385n = 100

Then the left side:

42m + 385n = 7(6m + 55n)

is divisible by 7.  But the right side, 100, is not, so they cannot be equal.  

Note: The following is a standard theorem of number theory:

The equation  ax + by = 1 has integer solutions for x and y (which could be negative) if and only if gcd(a,b) = 1.

Proofs are fun.  Feel free to send more.