1. Richtung ((i)->(ii))
Sei ggT(a,b)=g Somit gibt es natürlich Zahlen k und l mit a=gk und b=gl. Somi gilt c=ax+by=gkx+gly=g(kx+ly). Mit division durch g erhält man dann kx+ly=c/g.
Da auf der linken Seite nun nur ganze Zahlen stehen muss die linke und damit auch die rechte Seite eine ganze Zahl sein, weshalb g ein teiler von c sein muss.
2. Richtung ((ii)->(i))
Sei wieder ggT(a,b) =g Somit gibt es Natürliche Zahlen k, l und m, mit a=gk, b=gl und c=mg und ggT(k, l) =1.
Betrachten wir jetzt gkx+gly=ac+by=c=mg erhalten wir mit Division durch g
kx+ly=m.
Daraus ergibt sich kx=m-ly und dann x=(m-ly)/k.
Somit bleibt noch zu zeigen übrig, dass es ein y gibt, sodass m-ly ≡ 0, also m ≡ ly mod k.
Dazu führe ich einen Beweis mit Widerspruch:
Angenommen es gibt kein y für das m≡ ly mod k gilt.
Da es genau k Restklassen mod k gibt, und wir angenommen haben das ly niemals m als restklassen annimmt, kann ly höchstens k-1 restklassen annehmen. Folglich gibt es zwei verschiedene ganze Zahlen p und q beide größer gleich 0 und kleiner k für die pl≡ ql mod k gilt. Da wir wisse das ggT(k, l) =1 dürfen wir diese gleichung durch l teilen, was p≡ g mod k ergibt und somit ein Widerspruch bring.
Folglich gibt es ein y, sodass m≡ ly mod k gilt, wodurch die gleichung ax+by=c Lösungen in den ganzen Zahlen besitzt.
Schüler, Punkte: 80