山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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

拡張ユークリッド互除法

Extended Euclidean algorithm - Wikipedia

 ax + by = gcd(a, b)

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

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

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};
    }