拡張ユークリッド互除法 ax + by = gcd(a, b) の解

拡張ユークリッド互除法

Extended Euclidean algorithm - Wikipedia

を解くためのアルゴリズム。

モジュラ逆数を計算するために必要でした。

qiita.com

コード

// as + bt = gcd(a, b)
    static long[] extendedGCD(long a, long b) {
        long s = 0, old_s = 1;
        long t = 1, old_t = 0;
        long r = b, old_r = a;
        while(r != 0) {
            long q = old_r / r;
            long old_s0 = old_s, old_t0 = old_t, old_r0 = old_r;
            old_s = s;
            s = old_s0 - q * s;
            old_t = t;
            t = old_t0 - q * t;
            old_r = r;
            r = old_r0 - q * r;
        }
        return new long[] {old_s, old_t};
    }