拡張ユークリッドの互除法

ユークリッドの互除法の商を使って、 $ax + by = \gcd(a, b)$ を満たす $(x, y)$ を再帰を使わずに求めます。

• ext_gcd(a, b): $ax + by = g$ を満たす $(g, x, y)$ を返す。 $g = \gcd(a, b) \ge 0$ で、 $a, b$ は負でもよい。 $O(\log \max(\lvert a \rvert, \lvert b \rvert))$
• linear_congruence(a, b, m): $ax \equiv b \pmod{m}$ の解全体を $x \equiv x_0 \pmod{m’}$ と表して $(x_0, m’)$ を返す（ $0 \le x_0 < m’$、 $m’ = m / \gcd(a, m)$）。解がなければ None。 $O(\log m)$

$ax + by = c$ の整数解は、 $c$ が $g$ の倍数のときだけあります。ext_gcd の $(x, y)$ を $c / g$ 倍したものが 1 つの解で、すべての解は整数 $t$ を使って $(x c / g + t b / g, y c / g - t a / g)$ と表せます。

$a$ と $m$ が互いに素なときの $a$ の逆元は、Python 3.8 以降なら pow(a, -1, m) でも求められます。

コード

def ext_gcd(a, b):
    # a x + b y = g（g = gcd(a, b) >= 0）となる (g, x, y)
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b:
        q = a // b
        a, b = b, a - q * b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    if a < 0:
        return -a, -x0, -y0
    return a, x0, y0


def linear_congruence(a, b, m):
    # a x ≡ b (mod m) の解を x ≡ x0 (mod m') として (x0, m') で返す。解がなければ None
    g, x, _ = ext_gcd(a % m, m)
    if b % g:
        return None
    m //= g
    return x * (b // g) % m, m