Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Extension of Bezout's identity

  1. Nov 27, 2009 #1
    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.
  2. jcsd
  3. Nov 27, 2009 #2
    Perhaps two parts:
    a+b can be expressed that way
    a+b-1 cannot

    then the main third part
  4. Nov 30, 2009 #3
    Well, any natural number greater than a+b-1, the first of which would be a+b
  5. Dec 2, 2009 #4
    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.
    Last edited: Dec 2, 2009
  6. Dec 5, 2009 #5
    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.
  7. Dec 5, 2009 #6
    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.
    Last edited: Dec 5, 2009
  8. Dec 5, 2009 #7
    (3,5)=1 so 3 and 5 coprime then 3x+5y=1, x=2, y=-1 then 3.2+5(-1)=1


    Every natural numbers also integers can be written like this.
  9. Dec 6, 2009 #8

    In the extension, x and y are not integers, they are natural numbers.
  10. Dec 13, 2009 #9
    you are true i will turn again...
  11. Dec 13, 2009 #10
    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)


    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.


    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.
  12. Dec 13, 2009 #11
    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).
  13. Dec 13, 2009 #12
    Of course, a and b are assumed naturals; that's the usual assumption when you say they are coprime.
  14. Dec 21, 2009 #13
    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.
  15. Dec 22, 2009 #14
    That's conjecture is Ramanujan's problem and the problem haven't solved from anybody yet, i haven't too :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook