拡張ユークリッド互除法

特にm,nが互いに素であるときmx+ny=1となり、この形でよく使われる

code: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