Den größten gemeinsamen Teiler von zwei Zahlen mit Python ermitteln
Hier ein kleines Script, mit dem man sich den größten gemeinsamen Teiler zweier Zahlen ermitteln lassen kann. Gleichzeitig liefert der erweiterte euklidische Algorithmus die Lösung für das Lemma von Bézout: \(ggT(a,b) = s \cdot a + t \cdot b\)
Der Code ist auch mit Python 3 lauffähig und liefert ein Tupel zurück, wobei gilt:
-
- Wert: Der größte gemeinsame Teiler
-
- Wert: s aus dem Lemma von Bézout
-
- Wert: t aus dem Lemma von Bézout
def matrixMult(a, b):
newMatrix = [[0 for i in range(len(b[0]))] for j in range(len(a))]
for i in range(len(a)):
for j in range(len(b[0])):
for c in range(len(a[0])):
newMatrix[i][j] += a[i][c] * b[c][j]
return newMatrix
def euklid(a, b):
matrix = [[1,0],[0,1]]
stop = False
while not stop:
r = a % b
q = int(a / b)
a = b
b = r
matrix = matrixMult([[0,1],[1,-q]], matrix)
if r == 0:
stop = True
return (a, matrix[0][0], matrix[0][1])
print(euklid(210, 231))