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