#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0

    Around Euclid algorithm ...


    This is probably OT (Off Topic) question ...

    The Euclidean algorithm, for given positive integers u,v,
    produces integers X and Y such that :

    u*X + v*Y = gcd(u,v) = greatest common divisor of u and v.

    Question: is there any simple way to describe ALL such X and Y ?

    ...

    Thanks in advance for any comments, suggestions, citations etc.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    50
    Question: is there any simple way to describe ALL such X and Y ?
    Yes! For any given (u, v), there exists only one (X, Y) satisfying the equation.
    ________________________________________________
    Wrong answer! See below.
    Last edited by mah$us; December 19th, 2011 at 02:44 AM.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0
    There are infinitely many solutions.

    Finally, the description is very easy:

    Let x0, y0 be some solution of u*X + v*Y = gcd(u,v).
    For example, the one given by EA.

    Then every solution of the above equation is of the form:

    X = x0 + x, Y = y0 + y,

    where x, y is any solution of equation: u*x + v*y = 0 (zero).

    For example: u=2,v=3. gcd(2,3) = 1.

    -1*2 + 1*3 = 1
    (-1+3)*2 + (1-2)*3 = 2*2 + (-1)*3 = 4 - 3 = 1
    (-1-3)*2 + (1+2)*3 = (-4)*2 + 3*3 = -8 + 9 = 1

    X = -1 + 3*z, Y = 1 - 2*z, z arbitrary integer.
    Last edited by leszek31417; December 18th, 2011 at 04:27 AM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    50
    So much for my quick answer! gcd(u, v) is the least positive linear combination uX+vY (a fairly simple theorem), and as such is unique.

    But it didn't occur to me that the (X, Y) forming the least positive linear combination are not unique.

    Conjecture: For gcd(u, v) = 1 and v>u, the (X, Y) computed by extended Euclid is that with smallest positive X (that is, v > X > 0). Can you prove or disprove this conjecture?
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0
    Interesting question. I'll think about it ...

    My conjecture is that X,Y given by EA minimize
    the sum of squares : X^2 + Y^2.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0
    Originally Posted by mah$us
    ...
    Conjecture: For gcd(u, v) = 1 and v>u, the (X, Y) computed by extended Euclid is that with smallest positive X (that is, v > X > 0). Can you prove or disprove this conjecture?
    I think your conjecture needs a small correction,
    because X may be negative.

    Example: For (u,v) = (5,8) EA gives (X,Y) = (-3,2).
    But the solution with smallest positive X is (X,Y) = (5,-3).

    Conjecture: For gcd(u,v) = 1 the (X,Y) computed by EA is that
    with the smallest absolute value of X.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    50
    Now that I took a little time to think about it, the (X, Y) found by extended Euclid probably has no property as simple as I conjectured.

    If it did, there would probably be an easier way to find this (X, Y) than the extended Euclid algorithm -- and as far as I know, there is no easier way.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0
    Originally Posted by mah$us
    ...
    If it did, there would probably be an easier way to find this (X, Y) than the extended Euclid algorithm ...
    There is always a "brute force" approach:
    find any pair (X,Y) such that |X|<=v and |Y|<=u and
    uX + vY is a common divisor of u,v.

    Anyway, I believe that your conjecture
    (with the above minor correction) is true.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    50
    By "easier" I meant requiring less steps of computation, which of course excludes any brute-force method.
  18. #10
  19. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0

    Slow EA


    Let me recall the "slow" version of EA, which computes
    simultaneously gcd and lcm (least common multiple).
    Code:
    void slowEA ( int a, int b, int &gcd, int &lcm )
    { int x,y,u,v;
    
       // assume a,b > 0   
    
       x = a; y = b;
       u = b; v = a; 
    
       while ( x!=y ) // invariant : xu + yv = 2ab
       {
    
          if ( x<y ) { y = y - x; u = u + v; }
          else       { x = x - y; v = v + u; }
    
       }
    
       gcd = x;
       lcm = (u + v)/2;
    
    }
    I have two problems :

    1. How to modify the above algorithm to get integers
    X,Y (note the uppercase) such that aX + bY = gcd ?

    2. In EA, the formula aX + bY = gcd is a "witness" for gcd.
    What is the analogous "witnessing" formula for lcm ?

    ...

    Thanks in advance for any comments, citations and links.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2009
    Posts
    191
    Rep Power
    50
    What is the motivation for the "slow EA" algorithm?

    Because gcd(a, b) X lcm(a, b) = | a X b |, Euclid can be used to compute gcd, and then one multiplication and one division yields lcm.
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2011
    Posts
    313
    Rep Power
    0
    Just to see EA from many different angles.

    Pure mathematical curiosity ...

    According to Knuth : "EA is the grandfather of all the algorithms".

IMN logo majestic logo threadwatch logo seochat tools logo