拡張ユークリッド互除法について
ax + by = cが整数a, b, cを求める必要がある場合、必ずaとbの最大公約数gの倍数にcはなる
つまり、少なくとも１つの値x, yで以下が成立する
pythonでの実装例
再帰を使う
def egcd(a, b):
# Base Case
if a == 0 :
return b, 0, 1
gcd, x1, y1 = egcd(b%a, a)
x = y1 - (b//a) * x1
y = x1
return gcd, x, y
- 戻り値
x,y,gcdが方程式の一つの解になる - MODINTを用いるときは合わなくなるので注意する
再帰を使わない
def egcd(a,b):
x, y, u, v = 1, 0, 0, 1
while b:
k = a // b
x -= k * u
y -= k * v
x, u = u, x
y, v = v, y
a, b = b, a % b
return x, y