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.