Es sei Ma,b := {ax + by | x, y ∈ Z}, also die Menge mit allen Elementen der Form ax + by, wobei a, b fest gewa ̈hlt sind und x, y ∈ Z beliebig sind. Somit ist zum Beispiel a·2+b·4∈Ma,b undaucha·(−1)+b·0∈Ma,b.
Die Aufgabe ist, zu zeigen, dass (Ma,b = dZ) ⇒ (d = ggT(a,b)) gilt. Dafu ̈r betrach- te man zuna ̈chst einmal die Mengengleichheit genauer. Eine Mengengleichheit besitzt immer zwei “Richtungen”:
(Ma,b =dZ)⇔(Mab ⊆dZ)∧(dZ⊆Ma,b).
Man betrachte diesen beiden Teilaussagen auf Elementeebene, zuna ̈chst ganz allgemein: A ⊆ B ⇔ ∀p ∈ A : p ∈ B, fu ̈r Mengen A,B. Damit lassen sich die Teilaussagen umformulieren:
(Ma,b ⊆dZ)⇔∀p∈Ma,b :p∈dZ, (dZ⊆Ma,b)⇔∀p∈dZ:p∈Ma,b.
Was bedeutet es nun, wenn p ∈ Ma,b? Nun, eben dass p von obiger Form ist, also das x,y ∈ Z existieren, so dass p = ax+by. Und p ∈ dZ? Dass ein k ∈ Z existiert, so dass p = dk. Somit wird aus der ersten Teilaussage:
∀x, y ∈ Z : ∃k ∈ Z : ax + by = dk.
(Macht euch in Ruhe klar, wieso das gerade Ma,b ⊆ dZ ist!) Wie ist die analoge Aussage fu ̈r die zweite Teilaussage?
Nun betrachte man die andere Seite der Implikation, welche zu zeigen ist: d = ggT (a, b). Was bedeutet dies per Definition? d ist gr ̈oßter gemeinsamer Teiler von a und b, d.h. zuna ̈chst einmal: d teilt a und d teilt b und weiter: fu ̈r alle anderen c ∈ Z, fu ̈r welche auch gilt, dass sie a und b teilen, welche also auch mo ̈gliche Kandidaten fu ̈r den ggT (a, b) sind, muss folgen, dass sie d teilen. Nochmals formal, wobei ich hier x teilt y als x | y schreibe:
d = ggT (a, b) ⇔ (d | a) ∧ (d | b) ∧ [∀c ∈ Z : ((c | a) ∧ (c | b)) ⇒ (c | d)] .
Als letzte Vorbemerkung braucht man nun noch zu wissen, was es bedeutet, dass x | y. Dies ist na ̈mlich genau dann der Fall, wenn man y ohne Rest durch x teilen kann, also wenn ein z ∈ Z existiert, so dass xz = y.

Damit hat man alles an der Hand, um die Aufgabe zu bewa ̈ltigen, die etwas struktu- riert, in etwa so ist: Es gelte die Mengengleichheit Ma,b := {ax + by | x, y ∈ Z}. Durch diese Gleichheit muss dann gelten:
(d|a)und(d|b) und ∀c∈Z:(c|a)und(c|b), dann(c|d).
Also sind im Grunde zwei Aussagen aus der Mengengleichheit zu folgern. Und die Men- gengleichheit selbst besteht ja aus zwei Teilaussagen ...Man betrachte nochmals die erste dieser Teilaussagen: fu ̈r beliebige x, y ∈ Z finde ich ein k ∈ Z, so dass ax + by = dk . . . na das ist doch mit geeigneter Wahl schon fast ein Teil der Lo ̈sung.
Beachtet bitte, dass ihr den ganzen Vorbau, welchen ich hier erarbeite habe, nur bedingt als gegeben ansehen ko ̈nnt. Entwickelt nach Mo ̈glichkeit euer eigenes Versta ̈ndnis fu ̈r die Aufgabe und benutzt meine U ̈berlegungen als Inspiration.