0 Daumen
706 Aufrufe
a,b = natürliche Zahlen. Zeigen Sie, dass für eine beliebige natürliche Zahl c die beiden folgende Eigenschaften äquivalent sind:
(i)  Die Gleichung xa + yb = c ist in ganzen Zahlen x; y E Z lösbar.
(ii) c ist ein Vielfaches von ggT( a; b ).
Avatar von

1 Antwort

+1 Daumen

(i)  Die Gleichung xa + yb = c ist in ganzen Zahlen x; y E Z lösbar.

und sei g = ggT( a; b )

Dann gilt g|a und g|b d.h. es gibt m und n aus Z mit

g*n=a und g*m=b   einsetzen in die Gleichung

x*g*n + y*g*m = c

g * ( x*n + y*m) = c

und laut Vor. sind  x,y auch ganze Zahlen und damit die

ganze Klammer eine ganze Zahl

also gilt:   c ist ein Vielfaches von ggT( a; b ).

umgekehrt:

(ii) c ist ein Vielfaches von ggT( a; b )  = g ,

also gibt es k aus Z mit c = k*g.

Nach dem Lemma von Bézout lässt sich ggt(a,b) darstellen

als x*a + y*b = g mit ganzen Zahlen x und y  

also  k*x*a + k*y*b = k*g = c     q.e.d.

Avatar von 289 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
Gefragt 21 Jul 2017 von Gast
0 Daumen
2 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community