Lemma von Bezout/Z/Einführung/Textabschnitt

Beispiel

Die Wasserspedition „Alles im Eimer“ verfügt über einen ${}7$- und einen ${}10$-Liter-Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Kann sie diesen Auftrag erfüllen?

Die Aufgabe ist lösbar: Man macht dreimal den ${}7$-Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach (oder gleichzeitig) macht man zweimal den ${}10$-Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann

${}3\cdot 7-2\cdot 10=1\,$

Liter transportiert (eine andere Möglichkeit ist ${}5\cdot 10-7\cdot 7=1$).

Die dieser Überlegung zugrunde liegende Aussage heißt Lemma von Bezout.

Satz

Es seien  ${}a,b\in \mathbb {N}$  zwei teilerfremde natürliche Zahlen.

Dann gibt es ganze Zahlen  ${}r,s\in \mathbb {Z}$  mit  ${}ra+sb=1$. 

Beweis

Dies ergibt sich als Korollar zu

Fakt, man kann es aber auch direkt durch Induktion über das Maximum von ${}a$ und ${}b$ beweisen, siehe

Aufgabe.

$\Box$

Man sagt auch, dass  ${}ra+sb=1$  eine Darstellung der ${}1$ als eine Linearkombination der ${}a$ und ${}b$ ist. Die ${}r,s$ heißen Koeffizienten der Darstellung.