1. ## 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.

2. ## 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:

4. ## 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.

5. ## 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

6. ## 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??

7. ## Re: Greatest Common Divisors

Originally Posted by johng
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.

8. ## 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.

9. ## Re: Greatest Common Divisors

Why the flood of ads immediateley after my last response?

10. ## Re: Greatest Common Divisors

Originally Posted by Hartlw
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.