拡張ユークリッド互除法

ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解x,yを得ることができる 特にm,nが互いに素であるときmx+ny=1となり、この形でよく使われる

python

def extended_euclidean(a, b, test=False):
    """
    Extended Euclidean algorithm
    Given a, b, solve:
    ax + by = gcd(a, b)
    Returns x, y, gcd(a, b)

    Other form, for a prime b:
    ax mod b = gcd(a, b) = 1

    >>> extended_euclidean(3, 5, test=True)
    3 * 2 + 5 * -1 = 1 True
    >>> extended_euclidean(240, 46, test=True)
    240 * -9 + 46 * 47 = 2 True
    """
    init_a = a
    init_b = b
    s, u, v, w = 1, 0, 0, 1
    while b:
        q, r = divmod(a, b)
        a, b = b, r
        s, u, v, w = v, w, s - q * v, u - q * w

    if test:    
        print(f"{init_a} * {s} + {init_b} * {u} = {a}", init_a * s + init_b * u == a)
    else:
        return s, u, a