Bezout's Lemma

Description

For given two numbers Bezout’s Lemma states the existence of a simple formula, which is way more important than initially thought.

Statement for $\mathbb{Z}$

Seien $m,n\in \mathbb{Z},(m,n)\ne (0,0)$. Dann gibt es $a,b\in \mathbb{Z}$ mit $am+bn=ggT(m,n)$ [^1]

Proof: Jede Subgroup einer Zyklischen Gruppe ist Zyklisch. Insbesondere ist auch die aus $⟨m,n⟩$ erzeugte Untergruppe von $(\mathbb{Z},+)$ zyklisch. Diese Gruppe besteht aus den Potenzen und des Erzeugendensystem: $\{am+bn:a,b\in \mathbb{Z}\}$ Zeichnet man diese Gruppe auf dem Zahlengerade auf, wird offensichtlich, dass die Gruppenelemente in gleichen Abständen auftauchen (bei einer Zyklischen Gruppe irgendwie offensichtlich) Dieser Abstand ist genau der Größter gemeinsamer Teiler (Natürliche Zahlen). Da $0$ als neutrales Element immer in der Group enthalten ist, ist auch $ggT(m,n)$ in der Gruppe.

Es gibt damit Potenzen $a,b$ sodass $ggT(m,n)=am+bm$

Using a more elaborate proof one can see that the statement only relies on the existence of the $ggT$, which can be calculated in an Euclidian ring. The euclidean algorithm even calculates the $x,y$ values:

Statement for general euclidian rings $R$ be a Euclidian ring and $a,b\in R$ with $d=gcd(a,b)$. Then there are $x,y\in R$ such that: $d=xa+yb$

Let