Lemma von Bezout/N/Teilerfremd/Induktion/Fakt/Beweis/Aufgabe/Lösung

Wir beweisen die Aussage durch Induktion über das Maximum von ${}a$ und ${}b$, wobei wir ohne Einschränkung ${}a\leq b$ wählen können. Wenn das Maximum ${}0$ ist, so sind beide Zahlen ${}0$ und somit nicht teilerfremd. Wenn das Maximum ${}1$ ist, so ist ${}b=1$ und somit ergeben ${}r=0$ und ${}s=1$ eine Darstellung der ${}1$. Es seien nun ${}a\leq b$ teilerfremd, ${}b\geq 2$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als ${}b$ sind, schon bewiesen. Dann ist ${}a<b$, da bei ${}a=b$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ${}a=0$ ausschließen. Wir betrachten das Zahlenpaar ${}(a,b-a)$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als ${}b$. Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch ${}a$ und ${}b-a$ teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis.  Nehmen wir also an, dass ${}a$ und ${}b-a$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl ${}t\geq 2$, die sowohl ${}a$ als auch ${}b-a$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen ${}m,n$ mit ${}a=mt$ und ${}b-a=nt$ gibt. Doch dann ist

${}b=(b-a)+a=nt+mt=(n+m)t\,$

ebenfalls ein Vielfaches von ${}t$, im Widerspruch zur Teilerfremdheit von ${}a$ und ${}b$.  Die Induktionsvoraussetzung ist also auf ${}a$ und ${}b-a$ anwendbar und somit gibt es ganze Zahlen ${}r,s$ mit

${}ra+s(b-a)=1\,.$

Dann ist aber auch

${}(r-s)a+sb=ra+s(b-a)=1\,$

und wir haben eine Darstellung der ${}1$ mit ${}a$ und ${}b$

gefunden.

Zur gelösten Aufgabe