Äquivalenz beider Aussagen: Grösster gemeinsamer Teiler und ax + by = c

Question

Wie zeige ich die Äquivalenz der beiden Aussagen ?

Answer 1

ax +by = c mit a,b,c aus ℕ und x,y aus ℤ.

Sei  t ein gemeinsamer Teiler von a und b

==>    t | ax   und   t | by

==>   t |  ( ax+by )

==>  t | c   .

Wenn jeder gem. Teiler con a und b das c teilt,

dann tut es auch der ggT.

Comments

Muss man nicht beide Richtungen zeigen ?

---

Doch, hast du eine Idee ?

---

Könnte vielleicht so gehen mit Lemma von Bezout:

g=ggT(a,b)

==>   ggT ( a/g ; b/g) = 1

==> Es gibt u,v aus Z mit

                (a/g)*u + (b/g)*v = 1      | *g

                a*u + b*v = g

und wenn g ein Teiler von c ist, dann ist c/g = n aus Z

und damit wird aus        a*u + b*v = g    |  n

                                 a*u*n + b*v*n = g*n  = c

und  un und vn sind die ganzzahligen Lösungen von

              ax +by = c