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:

Der Code ist auch mit Python 3 lauffähig und liefert ein Tupel zurück, wobei gilt:

    1. Wert: Der größte gemeinsame Teiler
    1. Wert: s aus dem Lemma von Bézout
    1. 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))
I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to stefan@eliteinformatiker.de.