1. Euclidean Algorithm

• 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 빠르게 구할 수 있는 알고리즘이다.
• a를 b로 나눈 나머지가 0일때, b가 최대 공약수(GCD)이다.
• gcd(a,b) = gcd(b,a%b) = gcd(a%b,b%(a%b)) = ... = gcd(d,0) = d

int gcd(int a, int b) {
    while (b > 0){
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

2. Extended Euclidean Algorithm

• modulo m에서 a의 곱의 역인 a^-1 mod m을 구한다.
• a와 m이 서로소인 경우 a^-1이 존재한다.
• 역이 존재하지 않으면 0을 리턴한다.

gcd(a,b) = gcd(b,a%b) = gcd(a%b,b%(a%b)) = ... = gcd(d,0)
= d =ax + by 형태로 아래와 같이 나타낼 수 있다.
d0 = a = ax0 +by0 ← x0=1, y0=0
d1 = b = ax1 + by1 ← x1=0, y1=1
d2 = d0 -(d0/d1)*d1 = ax2 + by2
d3 =d1 -(d1/d2)d2 = ax3 +by3
...
If dk+1 = 0, then gcd(a,b) = dk = axk + byk

이때 a와 b가 서로소이므로, 1 = axk + byk가 된다.
양변에 modulo b를 하면 1 = axk mod b가 되고, a^-1 mod b = xk 가 된다.

int mul_inv(int a, int m) {
    int d0 = a, d1 = m;
    int x0 = 1, x1 = 0;

    while (d1){
        int q = d0 / d1;
        int tmp;
        tmp = d0;
        d0 = d1;
        d1 = tmp - q * d1;

        tmp = x0;
        x0 = x1;
        x1 = tmp - q * x1;
    }
    if (d0 == 1)
        return (x0 > 0 ? x0 : x0 + m);
    else
        return 0;
}