ggT und erweiterter euklidischer Algorithmus

Question

folgende Frage:

Seien a,b,c ∈ ℤ beliebig. Zeigen Sie:

∃ x,y ∈ ℤ mit ax + by = c ⇔ ggT(a,b)|c

Ich gehe davon aus, dass das über den erweiterten euklidischen Algorithmus bewiesen werden kann, aber ich habe leider keinen Ansatz.

Answer 1

die Hinrichtung überlass ich dir.

Für die Rückrichtung: Sei $d = ggT(a,b)$. Dann gilt $d|c$ also $\exists z \in \mathbb{Z}: zd = c$.

Nach dem EEA weißt du: $\exists x',y' \in \mathbb{Z}: ax'+by' = c$. Ab hier ist es nur noch ein Katzensprung um die Rückrichtung abzuschließen.

Gruß