C language extends Euclid algorithm code

Given two positive integers m and n, we calculate their greatest common factor d and two integers a and b, such that a*m+b*n=d

Algorithm process
E1. Buy a '= b = 1; A = b '= 0; C = m, d = n;

E2. Calculate d and r so that c=q*d+r;

E3. If r = = 0; A *m+b*n=d;

E4. C = d. D = r; T = a '; A '= a; A = t - q * a; T = b '; B = b; B = t - q * b; Returns the E2.

prove

For existing m and n, suppose m > N; If I divide the variables a,b,a transpose,b transpose; The algorithm is exactly the same as Euclid's algorithm, the algorithm for calculating the greatest common divisor.

The final requirement is a*m+b*n=d=GCD(m,n); If the formula is true, a '* n + b' * (m % n) = GCD (n, m % n);

Because the GCD (m, n) = GCD (n, m % n);

So a * m + b * n = '* n + b * (m % n)

N + b = a '*' * (m - (m/n * n))

N + b = a '*' * 'm - b * * (m/n) n

* m + = b '(a' - b * (m/n)) * n

So a = b '; B = a '- b * (m/n);

It follows that a and b can be calculated according to a 'and b'.

Code implementation

void EGCD(int m,int n)
{
    int a,a1,b,b1,c,d,q,r,t;
    a1=b=1,a=b1=0,c=m,d=n;
    while(1)
    {
        q=c/d,r=c%d;
        if(r==0)
        {
            printf("(%d)*%d+(%d)*%d=%dn",a,m,b,n,d);
            return;
        }
        c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
    }
}