Ganzzahlige Gleichung < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:09 Sa 28.01.2006 | | Autor: | cloe |
| Aufgabe | Beweise:
Die ganzzahlige Gleichung ax+by=m ist in [mm] \IZ [/mm] lösbar [mm] \gdw [/mm]
m ist Vielfaches vom ggt(a,b). |
Ich komm bei dieser Aufgabe leider überhaupt nicht weiter.
Könnte mir da bitte jemand helfen. Ich brauch den Beweis dringnd für die Klausur :-/
Danke im voraus
|
|
| |
|
Hallo cloe,
betrachte die Gleichung $ax + by = m$. Alle auftretenden Variablen sind ganze Zahlen. Ist $d = [mm] \ggT(a,b)$, [/mm] dann ist die linke Seite stets durch $d$ teilbar. Damit die Gleichung also überhaupt lösbar ist, muss auch $m$ durch $d$ teilbar sein. Das ergibt eine Implikation deiner Behauptung:
Wenn die Gleichung lösbar ist, dann ist $m$ durch [mm] $\ggT(a,b)$ [/mm] teilbar.
Nun betrachte die Gleichung $ax + by = d$, wobei $d$ immernoch der ggT von a und b ist. Nach dem Lemma von Bezout ist diese Gleichung lösbar (eine Lösung kann man z.B. mit dem erweiterten euklidischen Algorithmus berechnen). Nach Voraussetzung ist m ein Vielfaches von d, es gibt also ein $n$ mit $nd = m$. Multipliziere die gelöste Gleichung mit $n$, und du erhältst $a(nx) + b(ny) = m$, damit ist die Ausgangsgleichung lösbar.
Gruss,
SirJective
|
|
|
|
