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ß