December 17th, 2011, 05:48 AM

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.
December 17th, 2011, 03:08 PM

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 01:44 AM.
December 17th, 2011, 11:10 PM

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 + (12)*3 = 2*2 + (1)*3 = 4  3 = 1
(13)*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 03:27 AM.
December 19th, 2011, 01:59 AM

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?
December 19th, 2011, 03:04 AM

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.
December 22nd, 2011, 01:45 AM

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.
December 23rd, 2011, 01:05 AM

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.
December 23rd, 2011, 05:06 AM

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.
December 23rd, 2011, 03:17 PM

By "easier" I meant requiring less steps of computation, which of course excludes any bruteforce method.
January 1st, 2012, 03:34 AM

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.
January 3rd, 2012, 05:52 PM

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.
January 3rd, 2012, 10:27 PM

Just to see EA from many different angles.
Pure mathematical curiosity ...
According to Knuth : "EA is the grandfather of all the algorithms".