TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 53

SS08 Beispiel 9

Man bestimme alle ganzen Zahlen x, y, welche die Gleichung $243x+198y=9$ erfüllen.

Angabe SS 08 geändert, sonst analog wie unten

Man finde 2 ganze Zahlen x, y, welche die Gleichung $451x+165y=11$ erfüllen.

Hapi

Dividieren durch 9 ergibt:

$27x+22y=1$

Gesucht ist also eine Linearkombination der Werte 27 und 22 mit dem Ergebnis 1. Da die beiden Zahlen 27 und 22 teilerfremd sind (ggT(27,22)=1), können wir den Euklidischen Algorithmus verwenden um Werte für für so eine Linearkombination zu erhalten.

Schritt 1:

27 = 1 * 22 + 5
22 = 4 *  5 + 2
 5 = 2 *  2 + 1
 2 = 2 *  1 + 0

Schritt 2:

Daraus folgt:

1 =  5 - 2 *  2
2 = 22 - 4 *  5
5 = 27 - 1 * 22

Schritt 3: Die vorletzte Zeile Euklidischen Algorithmus wird umgeformt:

1 = 5 - 2 * 2

Diese Gleichunge sieht unserer Angabe schon ähnlich, aber wir müssen die sie jetzt so umformen, dass auf der rechten Seite nur noch Vielfache von 27 und 22 stehen. Deshalb setzen wir jetzt nacheinander die Gleichungen aus Schritt 2 ein:

1 = 5 - 2 * 2
1 = 5 - 2 * (22 - 4 * 5)
1 = 5 - 2 * 22 + 8 * 5

umformen und zusammenfassen:

1 = 9 * 5           - 2 * 22
1 = 9 * (27-22)     - 2 * 22
1 = 9 * 27 - 9 * 22 - 2 * 22

ergibt:

1 = 9 * 27 - 11 * 22

Vergleichen mit der Angabe ergibt:

x =   9
y = -11

---

--PurpleHaze 20:59, 10. Nov 2008 (CET)

Bei dieser Lösung wird noch ignoriert, dass man alle ganzen Zahlen x, y finden muss, welche die Gleichung lösen

--> Hier sieht man wie man alle findet