Results 1 to 10 of 10
Like Tree3Thanks
  • 2 Post By emakarov
  • 1 Post By johng

Math Help - Greatest Common Divisors

  1. #1
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Greatest Common Divisors

    Show that, for any positive integers a,b the set of all ma+nb (m,n positive integers) includes all multiples of (a,b) larger than ab.

    This problem is from a section on the integers in Ch 1 of Birkhoff and MacLane which covers:

    (a,b), gcd of a,b
    [a,b], lcm of a,b
    Division algorithm, a=bq+r, 0<=r<b
    p prime: p|ab → p|a or p|b
    (c,a)=1 and c|ab → c|b
    (a,c)=1, a|m, and c|m → ac|m
    There are s and t such that (a,b)=sa+tb, and for all s and t, sa+tb is a multiple of (a,b).

    An answer within the context of the section would be appreciated. My apologies for posting this stickler: I violated one of my cardinal rules: NEVER, NEVER, look back at the problems. Like Lot’s wife, it turned me into a pillar of salt and stopped me dead in my tracks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    643
    Thanks
    258

    Re: Greatest Common Divisors

    Hi,
    I'm betraying my age, but I first ran into this problem 35+ years ago when I was teaching an elementary number theory course. I'm still amazed at the result -- more startling in case a and b are relatively prime. That is, when a and b are relatively prime, any integer x > ab is a linear combination of a and b with positive coefficients. I'm almost positive the attached solution is not what I gave all those years ago, but I can't remember my original proof. Any way, here's a solution:

    Greatest Common Divisors-mhfnumbertheory.png
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Greatest Common Divisors

    This page from StackExchange may also be helpful.
    Thanks from johng and Hartlw
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    643
    Thanks
    258

    Re: Greatest Common Divisors

    Hi again,
    I was glad to see Emakarov's link to a proof. My memory was jogged; this proof was exactly what I'd previously done.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Greatest Common Divisors

    The (incorrect) proof referenced in post 3 is reproduced here for purposes of convenient discussion.

    ------------------------------------------
    “Theorem: Let a and b be relativeley prime positive integers. If c > ab, then there exist positive integers x and y such that ax + by = 0.

    There are integers x0,y0, such that ax0 + by0 = c. Consequently, all integer solutions of the equation ax + by = c have the shape x = x0 + bt, y = y0 - at, where t ranges over the integers. To produce a positive solution, we want to find t such that x > 0 and y > 0.

    So we need y0 – at > 0, x0 + at > 0, or equivalently
    -x0/b < t < y0/a.*
    The interval (-x0/b,y0/a) has width y0/a + x0/b which simplifies to (ax0 + by0)/ab, that is c/ab. If c/ab >1, then the interval is guaranteed to contain the integer t, and we are finished.”
    -----------------------------------

    The conclusion is that a solution exists if c/ab > 1, or c> ab. c = ab + 1 satisfies this requiremment but leads to a contradiction by the above proof:

    ax + by = ab + 1, and there exist x0 and y0 st ax0 + by0 = ab + 1.
    x = x0 + bt and y = y0 –at satisfy ax + by = ab + 1 for all t and are a solution if x > 0 and y > 0, or x0 + bt > 0 and y0 –at > 0 or ax0 + abt > 0 and by0 –abt > 0 →
    -ax0 < abt < by0, and so abt has to be in the interval by0 – (–ay0) = ab +1 which is impossible.

    Repeating the same thing for arbitrary c leads to the conclusion that abt has to be in the interval c which is only satisfied if c is a multiple of ab, which is not the answer to the problem.
    __________________________

    * Just noticed there is also a problem with -x0/b < t < y0/a, aside from leaving integer arithmetic. Since either x0 or y0 can be negative, this inequality can not in general be satisfied. For example, with y0 neg, -2 < t < -4. The problem is that x = x0 + bt, y = y0 –at do not exhaust the possibilities for x and y. For example, if b=5, x could be x0 + 2.

    Another problem with * is that if, say, -3 < t > 2, the conclusion that t has to be in the interval 2-(-3) = 5 is incorrect. t = 3 is in the interval 5 but doesn’t satisfy -3 < t > 2
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    643
    Thanks
    258

    Re: Greatest Common Divisors

    Hi,

    I think you have an error in your thinking. The cited proof is correct. Here's what you posted:

    The conclusion is that a solution exists if c/ab > 1, or c> ab. c = ab + 1 satisfies this requiremment but leads to a contradiction by the above proof:

    ax + by = ab + 1, and there exist x0 and y0 st ax0 + by0 = ab + 1.
    x = x0 + bt and y = y0 –at satisfy ax + by = ab + 1 for all t and are a solution if x > 0 and y > 0, or x0 + bt > 0 and y0 –at > 0 or ax0 + abt > 0 and by0 –abt > 0 →
    -ax0 < abt < by0, and so abt has to be in the interval by0 – (–ay0) = ab +1 which is impossible.

    Take a=2 and b=3 with x0=-7 and y0=7. t must be such that t>(-x0)/b and t<(y0)/a; i.e. t>7/3 and t<7/2, namely t=3. Now you say -ax0 < abt < by0 is impossible. What's impossible about 14 < 18 < 21??
    Thanks from Hartlw
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Greatest Common Divisors

    Quote Originally Posted by johng View Post
    Hi,

    I think you have an error in your thinking. The cited proof is correct. Here's what you posted:
    johng. You are right. My apologies and thanks for finding it out.

    Sorry, I missed a crucial point:

    If I can find a t in the interval (e,f), then the theorem is proved. I can find a t in the interval if |t| < | e-f |.

    And yet, what if the interval is 1.7,2.3? t is in this interval but not in the interval 1.3,1.9*

    And there still remains the question, if t has to satisfy -x0/b < t < y0/a, where a,b positive and relativeley prime but otherwise arbitrary, and all we know is x0 and y0 can not both be negative, then how do you eliminate a possibility such as x0 positive and y0 negative and, say
    -2 < t < -4

    * OK on this point. c/ab > 1 is sufficient but not necessary. That leaves the remaining question.
    Last edited by Hartlw; May 20th 2013 at 12:54 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Greatest Common Divisors

    The proof from post 3 is corrrect. Thanks emakorov and johnq. If I might rephrase it in a manner which makes me more comfortable:

    Given (a,b) =1 and a,b,c > 0.
    Find x,y > 0 st xa+by=c.

    There are x0 and y0 st
    x0a+y0b=c.
    If x0 and y0 are both positive, finished. Otherwise they must be of opposite sign because they can’t both be negative.
    x=x0 +bt and y=y0-at also satisfy xa+by=c, and satisfy required conditions if x>0 and y>0, which gives
    -x0a<abt<y0b.
    In order for this interval to be meaningful it is necessary that y0b>-x0a, or
    x0a+y0b>0, which indeed is the case since x0a+y0b=c>0. Finally, a t can be found st
    -x0a<abt<y0b if abt is in the interval c, ie, if c>ab. For example if c=ab+1, ab(1) is in the interval.

    Comment: I couldn’t have solved this if I worked on it for the rest of my life. It was all I could do to understand the solution. Frankly, to give a problem like this in an elementary section introducing number theory is, in my opinion, quite nasty. Never, Never, look at the problems.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Greatest Common Divisors

    Why the flood of ads immediateley after my last response?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Greatest Common Divisors

    Quote Originally Posted by Hartlw View Post
    The proof referenced in post 3 is reproduced here for convenient reference.

    ------------------------------------------
    “Theorem: Let a and b be relativeley prime positive integers. If c > ab, then there exist positive integers x and y such that ax + by = c.

    There are integers x0,y0, such that ax0 + by0 = c. Consequently, all integer solutions of the equation ax + by = c have the shape x = x0 + bt, y = y0 - at, where t ranges over the integers. To produce a positive solution, we want to find t such that x > 0 and y > 0.

    So we need y0 – at > 0, x0 + at > 0, or equivalently
    -x0/b < t < y0/a.*
    The interval (-x0/b,y0/a) has width y0/a + x0/b which simplifies to (ax0 + by0)/ab, that is c/ab. If c/ab >1, then the interval is guaranteed to contain the integer t, and we are finished.”
    Where in the proof is the assumption that (a,b)=1 used? A natural starting point in this case would be that x0 and y0 exist st ax0+by0=1.

    EDIT: Never mind. If (a,b)=d, divide ax0+by0=c by d. since d divides a and b it has to divide c.
    Last edited by Hartlw; May 21st 2013 at 01:52 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 13th 2012, 02:51 PM
  2. greatest common divisors
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 18th 2012, 08:19 AM
  3. common divisors of p^3q^2 and p^2qr?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 19th 2011, 10:25 AM
  4. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  5. Norms and common divisors
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: May 27th 2010, 07:51 AM

Search Tags


/mathhelpforum @mathhelpforum