Lemma von Bézout

Das Lemma von Bézout (nach Étienne Bézout (1730-1783)) in der Zahlentheorie besagt, dass sich der größte gemeinsame Teiler $\operatorname {ggT} (a,b)$ zweier ganzer Zahlen $a$ und $b$ als Linearkombination von $a$ und $b$ mit ganzzahligen Koeffizienten darstellen lässt:

$\operatorname {ggT} (a,b)=s\cdot a+t\cdot b$ mit $s,t\in \mathbb {Z}$.

Sind $a$ und $b$ teilerfremd, dann existieren $s,t\in \mathbb {Z}$, sodass

$1=s\cdot a+t\cdot b$

gilt.

Die Koeffizienten $s$ und $t$ können mit dem erweiterten euklidischen Algorithmus effizient berechnet werden.

Allgemeiner gilt das Lemma von Bézout in jedem Hauptidealring, sogar in einem nicht-kommutativen; für die genauen Aussagen siehe dort.

Beweis

Der Beweis des Lemmas basiert darauf, dass die ganzen Zahlen bezüglich der Addition eine zyklische Gruppe bilden. Das hat zur Folge, dass jede Untergruppe von $\mathbb {Z}$ von der Form

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle r\Z=\left\{ rs \mid s \in \Z \right\}}

mit einer geeigneten ganzen Zahl $r$ ist. Demnach gibt es auch für die Untergruppe

$a\mathbb {Z} +b\mathbb {Z} =\left\{ax+by\mid x,y\in \mathbb {Z} \right\}$

eine ganze Zahl $r$ mit

$r\mathbb {Z} =a\mathbb {Z} +b\mathbb {Z}$.

Es lässt sich zeigen, dass $r=\operatorname {ggT} (a,b)$ gilt und das Lemma von Bezout somit eine Folgerung der allgemeineren Aussage

$\operatorname {ggT} (a,b)\mathbb {Z} =a\mathbb {Z} +b\mathbb {Z}$

ist.

Literatur

• Kurt Meyberg: Algebra - Teil 1. Hanser 1980, ISBN 3-446-13079-9, S. 43