Thread: Two Discrete Problems

Hello,

I am needing some help on the two problems below. Thank you in advance.

1) Prove by contradiction that there do not exist integers m and n such that 14m + 21n = 101.

and

2) Using the fact that an integer n, either n >= 14 or n <= 15, or otherwise prove 7 does not divide 100.

Originally Posted by MathStudent1

Hello,

I am needing some help on the two problems below. Thank you in advance.

1) Prove by contradiction that there do not exist integers m and n such that 14m + 21n = 101.
.

gcd(14,21)=7
Thus,
7 divides 101 which is false.

Thank you ThePerfectHacker. I made a typo when I first made my post. Sorry about that. So, it should be 14m + 21n = 100 not 101.

I am beening taught to turn this into a if/then statement and go from there.

If m and n are integers, then 14m + 21n = 100
Factor out a 7 givng us 7(2n +3m) = 100

From here I have trouble. Also, should the if/then statement be not equal to 100 instead of equal to? I haven't had that much experience with proof by contradiction. Thank You.

Originally Posted by MathStudent1

Thank you ThePerfectHacker. I made a typo when I first made my post. Sorry about that. So, it should be 14m + 21n = 100 not 101.

I am beening taught to turn this into a if/then statement and go from there.

If m and n are integers, then 14m + 21n = 100
Factor out a 7 givng us 7(2n +3m) = 100

From here I have trouble. Also, should the if/then statement be not equal to 100 instead of equal to? I haven't had that much experience with proof by contradiction. Thank You.

Let,
p= (there exists n,m such that 14m+21n=100).

Now if "p" is true we shown that 7 divides 100.

Thus,
q=(7 divides 100).
But this is false.

Meaning, (modens ponens)
[(p--> q) and (~q)]--> ~p
Thus,
~p=(there do not exists n,m such that 14m+21n=100)

This is mine 46th Post!!!

Hello, MathStudent1!

Here;s the first one . . .

1) Prove by contradiction that there do not exist integers m and n
. . .such that: .14m + 21n .= .101

Assume that there are integers m and n such that: .14m + 21n .= .101

. . . . . . . . . . . . . . . . . . .100
Divide by 7: . 2m + 3n .= .----
. . . . . . . . . . . . . . . . . . . .7


In the left side: m is an integer, so 2m is an integer. *
. . . . . . . . . . . . n is an integer, so 3n is an integer. *
Hence, 2m + 3n (the sum of two integers) is an integer. *

But the right side is an irreducible fraction (or decimal 14.2857...)

We have reached a contradicition, hence our assumption was incorrect.

. . There are no integers m and n that satisfy 14m + 21n .= .101

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

*
Reasons: The set of integers is closed under multiplication and addition.

Thank you Soroban. One question for you. When orginally I posted my thread I made a typo in that 14m + 21n = 100 NOT 101. Does that change the proof at all or does the logic remain the same. Following your proof, am I correct by stating this below:

Prove that there do not exist integers m and n such that: 14m + 21n = 100

Restating the problem - If m and n are integers, then 14m + 21n = 100

Factor out a 7 and we get 7(2m + 3n) = 100
Divide both sides by 7 and we get 2m + 3n = (100/7)
Since m is an integer then 2*m is an integer and since n is an integer then 3*n is and integer.
However, the RHS (100/7) is not an integer and therefore,
2m + 3n (IS NOT EQUAL TO) (100/7)

Hence, we have reached a contradiction of our assumption that m and n are integers.

Therefore, there do not exist integers m and n such that 14m + 21n = 100.

*****Thank you!*****

Hello again, MathStudent1!

Yes, the modified proof is still valid . . .
. . and you did an excellent job!