1 #include "egcd.h"
3 /*Computes the coefficients of the smallest positive linear combination of two
4    integers _a and _b.
5   These are a solution (u,v) to the equation _a*u+_b*v==gcd(_a,_b).
6   _a: The first integer of which to compute the extended gcd.
7   _b: The second integer of which to compute the extended gcd.
8   _u: Returns the coefficient of _a in the smallest positive linear
9        combination.
10   _v: Returns the coefficient _of b in the smallest positive linear
11        combination.
12   Return: The non-negative gcd of _a and _b.
13           If _a and _b are both 0, then 0 is returned, though in reality the
14            gcd is undefined, as any integer, no matter how large, will divide 0
15            evenly.
16           _a*u+_b*v will not be positive in this case.
17           Note that the solution (u,v) of _a*u+_b*v==gcd(_a,_b) returned is not
18            unique.
19           (u+(_b/gcd(_a,_b))*k,v-(_a/gcd(_a,_b))*k) is also a solution for all
20            k.
21           The coefficients (u,v) might not be positive.*/
22 int egcd(int _a,int _b,int *_u,int *_v){
23   int a;
24   int b;
25   int s;
26   int t;
27   int u;
28   int v;
29   /*Make both arguments non-negative.
30     This forces the return value to be non-negative.*/
31   a=_a<0?-_a:_a;
32   b=_b<0?-_b:_b;
33   /*Simply use the extended Euclidean algorithm.*/
34   s=v=0;
35   t=u=1;
36   while(b){
37     int q;
38     int r;
39     int w;
40     q=a/b;
41     r=a%b;
42     a=b;
43     b=r;
44     w=s;
45     s=u-q*s;
46     u=w;
47     w=t;
48     t=v-q*t;
49     v=w;
50   }
51   /*u and v were computed for non-negative a and b.
52     If the arguments passed in were negative, flip the sign.*/
53   *_u=_a<0?-u:u;
54   *_v=_b<0?-v:v;
55   return a;
56 }