Euclidean algorithm

int gcd(int a,int b) {
    if(b==0)
        return a;
    return gcd(b,a%b);
}

1. Make

$$c=gcd(a,b)$$

-

$$a=mc$$

-

$$b=nc$$

c is the biggest divisor

2. Got

$$r=a-kb=mc-knc=(m-kn)c$$

3. c is a divisor of r as well.

4. m-kn and n definitely has coprime relation

proof by contradiction

1. setting they are no coprime relation

   $$m-kn=xd$$

   -
   $n=yd$ (d>1)

2. then

   $$m=kn+xd=kyd+xd=(ky+x)d$$

   -

   $$a=mc=(ky+x)dc$$

   -

   $$b=nc=ydc$$
3. a and b ‘s biggest divisor is not c. so step 4 proved.

5. c is biggest divisor in b and r as well.

$$gcd(b, r)=c$$

-

$$gcd(a, b)=gcd(b, r)$$