How Can We Prove the Extension of Bezout's Identity?

[Onias]

As a consequence of Bezout's identity, if a and b are coprime there exist integers x and y such that:

ax + by = 1

The extension states that, if a and b are coprime the least natural number k for which all natural numbers greater than k can be expressed in the form:

ax + by

Is a+b-1. (Where x and y are natural numbers)

I am trying to prove this extension. I have used C++ to test it for a few specific examples, but this does not cut the mustard. I need a rigorous proof. I looked up ideals and ring theory, but I am at a loss because I am doing a physics and applied maths degree, I have very little knowledge of pure mathematics. Any help would be greatly appreciated, thanks in advance.

 

[g_edgar]

Perhaps two parts:
a+b can be expressed that way
a+b-1 cannot

then the main third part

 

[Onias]

Well, any natural number greater than a+b-1, the first of which would be a+b

 

[JSuarez]

Sorry for the lenghty introduction but, either I'm misunderstanding your statement or it's simply not true:

Suppose gcd(a,b) = d, then Bezout's identity states that there are integers x and y, such that:

ax + by = d

In addition, x and y can be efficiently computed by the extended euclidean algorithm, and d is the smallest positive element of the set:

{ax + by: x,y integers}

All this is well-known.

Now, if a and b are coprime, then d = 1 and ANY natural number N may be written in that form (so the smallest natural with your property would be 1):

ax + by = 1 => a(xN) + b(yN) = N

On the other hand, if d > 1, then there are no consecutive naturals that can be written like that (only the multiples of d), because if:

ax + by = n and ax' + by' = n + 1

Then d would divide n and n + 1, which is impossible, because they are coprime.

 

[Onias]

I probably didn't explain the problem very well, my apologies. Perhaps an example would help:

3x+5y = n

where x, y and n are natural numbers (including zero), 3 and 5 are coprime (naturally).

As far as I can tell, every natural number n>7 can be expressed in this way. For example:

3(1) + 5(1) = 8
3(3) + 5(0) = 9
3(0) + 5(2) = 10
3(2) + 5(1) = 11
3(4) + 5(0) = 12
3(1) + 5(2) = 13
... and so on

My problem is trying to prove this to be true. Any ideas where I can start? Thanks in advance.

 

[dodo]

I think what you need is the realization that, given two fixed integers a,b, the set of all linear combinations ax + by is exactly the same set as the multiples of gcd(a,b). In your case, if a,b are coprime, the multiples of gcd(a,b)=1 are simply all integers.

A proof would follow the standard procedure to determine that two sets are equal: prove that one is included in the other, and then the opposite inclusion.

Indeed the concept of "ideals" is used in ring theory to abstract these combinations or multiples, but a proof on these grounds may require a lot of material to be learned first. (I'm a newbie, I know. :) What I outlined above I believe is more accesible.

Edit: by "I know", i meant "I know the size of the wall I have IN FRONT of me", of course.

 

[nomather1471]

(3,5)=1 so 3 and 5 coprime then 3x+5y=1, x=2, y=-1 then 3.2+5(-1)=1

2(3.2+5(-1))=2-->3.(4)+5.(-2)=2
3(3.2+5(-1))=3-->3.(6)+5.(-3)=3
4(3.2+5(-1))=4-->3.(8)+5.(-4)=4
.
.
.

Every natural numbers also integers can be written like this.

 

[Onias]

(3,5)=1 so 3 and 5 coprime then 3x+5y=1, x=2, y=-1 then 3.2+5(-1)=1

2(3.2+5(-1))=2-->3.(4)+5.(-2)=2
3(3.2+5(-1))=3-->3.(6)+5.(-3)=3
4(3.2+5(-1))=4-->3.(8)+5.(-4)=4
.
.
.

Every natural numbers also integers can be written like this.

In the extension, x and y are not integers, they are natural numbers.

 

[nomather1471]

you are true i will turn again...

 

[JSuarez]

I think the main point of discussion is being lost behind a confusion of integers and naturals.

So I'll assume this: you want to prove that, given a and b coprime, you want to prove that all natural numbers larger than a + b - 1 may be written as an + bm, where m and n are naturals.

Here is a partial answer: suppose that, given a natural k, you can write it as:

k = a(n1) + b(m1), n1 and m1 naturals, not integers.

Then, how could you write k + 1 in the same form?

Suppose that:

k + 1 = a(n2) + b(m2)

Then:

a(n2 - n1) + b(m2 - m1) = 1

This means that n2 - n1 and m2 - m1 are solutions to the problem:

a(x1) + b(y1) = 1, where x and y are INTEGERS.

Therefore:

n2 = n1 + x1 + xh

m2 = m1 + y1 + yh

Where xh and yh are integer solutions of the homogeneous equation:

a(xh) + b(yh) = 0

In fact, if gcd(a,b) = 1, then xh = cb and yh = ca, where c is an integer.

Now we want to assure that (n2,m2) are naturals and, as at least one of the x1, y1 is negative, we must choose the appropriate c, such that both sums above are positive.

As for the least element being a + b - 1, I still don't have a proof.

 

[dodo]

I suspect a and b have to be non-negative; otherwise ax + by has no lower bound (for example, if a is negative, by making x big you can go as negative as you wish).

 

[JSuarez]

Of course, a and b are assumed naturals; that's the usual assumption when you say they are coprime.

 

[Onias]

Thanks a million JSuarez, and I apologise again if I wasn't clear. I should have mentioned in my original post that, in all likelihood, there is no proof as of yet to this conjecture. My goal is to make a reasonable attempt at solving it. In any case, I am almost finished my project but JSuarez has provided me with a boost to finish off those last few difficult pages, thanks again.

 

[nomather1471]

That's conjecture is Ramanujan's problem and the problem haven't solved from anybody yet, i haven't too :)