1 Attachment(s)

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:

Attachment 28373

Re: Greatest Common Divisors

This page from StackExchange may also be helpful.

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.

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 x_{0},y_{0}, such that ax_{0} + by_{0} = c. Consequently, all integer solutions of the equation ax + by = c have the shape x = x_{0} + bt, y = y_{0} - 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 y_{0} – at > 0, x_{0} + at > 0, or equivalently

-x_{0}/b < t < y_{0}/a.*

The interval (-x_{0}/b,y_{0}/a) has width y_{0}/a + x_{0}/b which simplifies to (ax_{0} + by_{0})/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 x_{0} and y_{0} st ax_{0} + by_{0} = ab + 1.

x = x_{0} + bt and y = y_{0} –at satisfy ax + by = ab + 1 for all t and are a solution if x > 0 and y > 0, or x_{0} + bt > 0 and y_{0} –at > 0 or ax_{0} + abt > 0 and by_{0} –abt > 0 →

-ax_{0} < abt < by_{0}, and so abt has to be in the interval by_{0} – (–ay_{0}) = 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 -x_{0}/b < t < y_{0}/a, aside from leaving integer arithmetic. Since either x_{0} or y_{0} can be negative, this inequality can not in general be satisfied. For example, with y_{0} neg, -2 < t < -4. The problem is that x = x_{0} + bt, y = y_{0} –at do not exhaust the possibilities for x and y. For example, if b=5, x could be x_{0} + 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

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??

Re: Greatest Common Divisors

Quote:

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 -x_{0}/b < t < y_{0}/a, where a,b positive and relativeley prime but otherwise arbitrary, and all we know is x_{0} and y_{0} can not both be negative, then how do you eliminate a possibility such as x_{0} positive and y_{0} negative and, say

-2 < t < -4

* OK on this point. c/ab > 1 is sufficient but not necessary. That leaves the remaining question.

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 x_{0} and y_{0} st

x_{0}a+y_{0}b=c.

If x_{0} and y_{0} are both positive, finished. Otherwise they must be of opposite sign because they can’t both be negative.

x=x_{0} +bt and y=y_{0}-at also satisfy xa+by=c, and satisfy required conditions if x>0 and y>0, which gives

-x_{0}a<abt<y_{0}b.

In order for this interval to be meaningful it is necessary that y_{0}b>-x_{0}a, or

x_{0}a+y_{0}b>0, which indeed is the case since x_{0}a+y_{0}b=c>0. Finally, a t can be found st

-x_{0}a<abt<y_{0}b 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.

Re: Greatest Common Divisors

Why the flood of ads immediateley after my last response?

Re: Greatest Common Divisors

Quote:

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 x_{0},y_{0}, such that ax_{0} + by_{0} = c. Consequently, all integer solutions of the equation ax + by = c have the shape x = x_{0} + bt, y = y_{0} - 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 y_{0} – at > 0, x_{0} + at > 0, or equivalently

-x_{0}/b < t < y_{0}/a.*

The interval (-x_{0}/b,y_{0}/a) has width y_{0}/a + x_{0}/b which simplifies to (ax_{0} + by_{0})/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 x_{0} and y_{0} exist st ax_{0}+by_{0}=1.

EDIT: Never mind. If (a,b)=d, divide ax_{0}+by_{0}=c by d. since d divides a and b it has to divide c.