### Thread: Around Euclid algorithm ...

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 ?

...

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

Join Date
Feb 2009
Posts
191
Rep Power
51
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.
________________________________________________
Last edited by mah\$us; December 19th, 2011 at 01:44 AM.
3. 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 03:27 AM.
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
51
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?
5. 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.
6. 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.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
51
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.
8. 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.
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
51
By "easier" I meant requiring less steps of computation, which of course excludes any brute-force method.
10. 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 ?

...

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

Join Date
Feb 2009
Posts
191
Rep Power
51
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.
12. 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".