1. Euclidean Algorithm

これは

に与えられた2つの数の間に存在する最大公約数(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

モードmでaの積の逆a^−1モード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 + by2d3 =d1 -(d1/d2)d2 = ax3 +by3...
If dk+1 = 0, then gcd(a,b) = dk = axk + bykこのときaとbは、1 = axk + bykである.
両側のモジュールbは1 = axk mod ba^-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;
}