```
/* Uses the Euclidean algorithm to compute d=gcd(a,b). Here, a and b MUST be
positive. Also finds m and n with ma+nb=d. In the code below,
a1=m0*a+n0*b and b1=m1*a+n1*b is a loop invariant of the while loop. So
the correct return is m0,n0.
*/
int gcd(int* m,int *n,int a,int b) {
int a1=a;
int b1=b;
int m0=1,n0=0,m1=0,n1=1,r,q,m2,n2;
while (b1!=0) {
r=a1%b1;
q=a1/b1;
m2=m0-m1*q;
n2=n0-n1*q;
m0=m1;
n0=n1;
m1=m2;
n1=n2;
a1=b1;
b1=r;
}
*m=m0;
*n=n0;
return(a1);
}
```