拡張ユークリッド互除法
ユークリッドの互除法を用いて、mx + ny = gcd(m, n) の解x,yを得ることができる
特にm,nが互いに素であるときmx+ny=1となり、この形でよく使われる
pythondef 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"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]