Results 1 to 7 of 7

Math Help - Two Discrete Problems

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    44

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MathStudent1 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MathStudent1 View Post
    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!!!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,739
    Thanks
    645
    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.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    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!*****
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,739
    Thanks
    645
    Hello again, MathStudent1!

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

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Math problems
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 5th 2010, 10:05 PM
  2. Discrete Word Problems...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 13th 2008, 06:17 PM
  3. discrete probability problems
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 4th 2007, 01:32 PM
  4. another discrete math problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 22nd 2007, 03:03 PM
  5. Need Help on these Discrete Problems
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 30th 2006, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum