(i) Die Gleichung xa + yb = c ist in ganzen Zahlen x; y E Z lösbar.
und sei g = ggT( a; b )
Dann gilt g|a und g|b d.h. es gibt m und n aus Z mit
g*n=a und g*m=b einsetzen in die Gleichung
x*g*n + y*g*m = c
g * ( x*n + y*m) = c
und laut Vor. sind x,y auch ganze Zahlen und damit die
ganze Klammer eine ganze Zahl
also gilt: c ist ein Vielfaches von ggT( a; b ).
umgekehrt:
(ii) c ist ein Vielfaches von ggT( a; b ) = g ,
also gibt es k aus Z mit c = k*g.
Nach dem Lemma von Bézout lässt sich ggt(a,b) darstellen
als x*a + y*b = g mit ganzen Zahlen x und y
also k*x*a + k*y*b = k*g = c q.e.d.
