Code: Alles auswählen
def extended_euclid(a, b):
#liefert (ggt, mul_a, mul_b) mit ggt==mul_a*a+mul_b*b
if b==0:
print( "\nggT = %(a)d" %vars() )
print( "Linearkombination des ggT aus Ausgangszahlen:\n" )
#
return (a, 1, 0) #a==1*a+0*b
else:
(faktor, rest) = divmod(a,b) #a==faktor*b+rest
print( "%(a)4d = %(faktor)4d * %(b)4d + %(rest)4d"%vars() )
#
(ggt, inn_mul_a, inn_mul_b) = extended_euclid(b, rest) #innere mul
(mul_a, mul_b) = (inn_mul_b, inn_mul_a-faktor*inn_mul_b)
print("%(ggt)4d = (%(mul_a)4d) * %(a)4d + (%(mul_b)4d) * %(b)4d"%vars())
#
return (ggt, mul_a, mul_b) #ggt==mul_a*a+mul_b*b
(a,b) = (374, 230)
extended_euclid(a, b)