Kap 2.3
DIOPHANTISCHE GLEICHUNGEN (2)

Gut vorbereitet können wir nun wieder das Problem der (linearen) Diohantischen Gleichungen ax+by=c angehen. Wir wollen zunächst einmal den Fall c=1 behandeln.

(I) ax+by=1 (*)

Wie man leicht einsieht, ist ax+by=1 nur dann lösbar, wenn a und b teilerfremd sind. Ist nämlich doch t>1 ein gemeinsamer Teiler von a und b, so gilt z.B. a=tA und b=tB, also ax+by=t(Ax+By)=1. Dann steht links ein Produkt ganzer Zahlen, bei dem zumindest der Faktor t>1 ist; das Produkt kann also nie 1 werden. Wir können also im Weiteren von teilerfremden Zahlen a und b ausgehen. Dann ist ggT(a,b)=1. Wir finden also mindestens eine Lösung von (*) mit dem Berlekamp-Algorithmus. Diese Lösung sei (x₀ï y₀). Dann sind auch (x₀+kbï y₀-ka), kÎ Z, Lösungen von (*) (Überprüfen durch Nachrechnen!). Das sind aber auch schon alle ganzzahligen Lösungen von (*). Denn ist (x₁ï y₁) irgendeine Lösung von (*), so gilt (1) ax₁+by₁=1 und (2) ax₀+by₀=1. Subtrahieren dieser beiden Gleichungen liefert:
a(x₀-x₁)+b(y₀-y₁)=0, also . Da rechts ein gekürzter Bruch steht, muß gelten x₁-x₀=kb und y₀-y₁=ka, was aber auf x₁=x₀+kb und y₁=y₀-ka führt. Also ist die Lösung (x₁ïy₁) von der angegebenen Art.

Beispiel: 47x-33y=1 Der Berlekamp-Algorithmus liefert

Damit haben wir eine spezielle Lösung mit x₀=-7 und y₀=-10. Alle Lösungen finden wir also durchx=-7+k·(-33) und y=10-k·47,also z.B.

(II) ax+by=c

Dieser Fall ist schnell erledigt, wenn wie oben die Zahlen a und b teilerfremd sind. Bleiben wir bei dem Beispiel 47x-33y=5. Wir haben die spezielle Lösung (-7ï -10) gefunden. Wenn aber 47·(-7)-33(-10)=1 ist , so muß man mit dem 5-fachen der Lösungen, also mit (-35ï-50) ja 5 erhalten. Probe: 47(-35)-33(-50)=5. Die anderen Lösungen der Gleichung erhält man wie oben durch x=-35+k(-33) und y=-50-k·47, wie man durch Einsetzen leicht nachprüft:
47(-35-33k)-33(-50-47k)=47·(-35)-33·47k+33·50+33·47k=47·(-35)-33·(-50)=5.

Wir fassen zusammen: Gilt ggT(a,b)=1, so findet man alle Lösungen der Gleichung ax+by=c durch x_r=x₀+r·b und y_r=y₀-r· a. Dabei ist x₀=c·x^* und y₀=c· y^*. x^* und y^* sind spezielle Lösungen der Gleichung ax+by=1, die man z.B. mit dem Berlekamp-Algorithmus erhält.

Wir geben ein Beispiel an:
151x+118y=60 liefert mit dem BA die Lösungen x^*=-25 und y^*=32. Damit ist x₀=-1500 und y₀=1920, was auf x_r=-1500+r× 118 und y_r=1920-r·151 führt. Damit könnte man zufrieden sein, jedoch hat man als Anfangslösungen lieber "in der Nähe" von Null liegende Zahlen. Wir berechnen deshalb 1500 DIV 118=12 und ersetzen r in beiden Lösungen durch 12+k:
x_k=-1500+(12+k)·118=-84+118k und y_k=1920-(12+k)·151=108-151k

AUFGABE 2.10
Löse die folgenden diophantischen Gleichungen. Gib jeweils 3 Lösungen an:
a) 17x-21y=22  b) 55x+91y=100   c) 100x-99y=81   
d) -35x-17y=99 e) 234x+457y=23  f) 1234x+2345y=3456  
g) -455x-223y=1000

Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zu Diophantischen Gleichungen starten.

Wir kommen nun zur Gleichung

(*) ax+by=c

mit g=ggT(a,b)¹1.
Klammert man g aus, so erkennt man aus g(Ax+By)=c Û Ax+By=c/g, dass die Gleichung in Z nur dann lösbar ist, wenn auch c durch g teilbar ist. Dann ist aber die Gleichung ax+by=c äquivalent zu der Gleichung

(**) Ax+By=C,

die man erhält, wenn man die Ausgangsgleichung durch g teilt. Da g der ggT von a und b ist, gilt ggT(A,B)=1. Aus dem letzten Abschnitt wissen wir aber bereits, wie man (**) löst!
Wir fassen zusammen:

SATZ 2.2
Die Gleichung ax+by=c mit a,b,cÎZ ist dann und nur dann in Z lösbar, wenn c durch g=ggT(a,b) teilbar ist. Es sei a=A·g, b=B·g und c=C·g. Ist irgendeine Lösung von Ax+By=1, so erhält man alle Lösungen von ax+by=c durch x_k=C·+k·B   und
y_k=C·-k·A.

Beispiel: 345x+525y=330 - ggT(345,525)=15 ; 15ï330
   Û 23x + 35y=22     A=23; B=35; C=22
   mit dem BA erhält man: =-3 und =2
also x_k=-66+35k und y_k=44-23k
Nun sind die "Anfangslösungen" - 66 und 44 schon relativ groß. Mit k=2 erhält man als "neue Anfangslösungen" die Zahlen 4 und -2 und damit
x_k=4+35k und y_k=- 2-23k
Für einige k erhält man damit:

Wir führen ein weiteres Beispiel vor: 1491x+2059y=12567
Wendet man den BA auf die Zahlen 2059 und 1491 an, so erhält man als letzte wesentliche Zeile: 71 8 -11 2, was uns zunächst verrät, daß ggt(2059;1491) = 71 ist und weiterhin-11·1491+8·2059=71 (*) ist. Da auch 12567 durch 71 teilbar ist, können wir zu der reduzierten Gleichung 21x+29y=177 übergehen. Nun müssen wir den BA nicht etwa nochmals auf 29 und 21 anwenden, um unsere Anfangslösungen zu bekommen: teilt man nämlich (*) durch 71, so erhält man: -11·21+8·29=1; d.h., die Löungen von (*) sind bereits die ersten Lösungen. Nun geht´s wie folgt weiter:

=-11	=8
=-11·177=-1947	=8·177=1416
=-1947+k·29	=1416-k·21

Wir gehen zu kleineren "Anfangslösungen" über (1416 div 21 =67)
=-4 =9  und damit endlich   x_k=-4+29k   y_k=9-21k

AUFGABE 2.11
Gib jeweils drei Lösungen der folgenden Gleichungen an:
a) 4914x+9597y=483      b) 897x-23y=457
c) 57x+36y=18             d) 2468x+4690y=6912
e) -6370x-3122y=14000   f) 48x+32y=160

Mit dem nebenstehenden Button kannst Du ein Übungsprogramm zu Diophantischen Gleichungen starten.

AUFGABE 2.12
a) Löse die diophantische Gleichung 3x+5y=c für c=7,15,20. Zeige, daß es nur für c=20 Lösungen (xïy) gibt, die beide gleichzeitig positiv sind.
b) Verfahre wie bei a) mit der Gleichung 9x+13y=c für c=50, 117,118.

AUFGABE 2.13
Bestimme x,y>0 in 13x+9y=1994 so, daß x+y minimal wird. Berechne die minimale Summe.
Bestimme x,y>0 in 23x+53y=5000 so, daß x+y maximal wird. Berechne die maximale Summe.

Ein Beispiel soll demonstrieren, wie man mit dem BA auf spezielle Lösungen von linearen Diophantischen Gleichungen mit mehr als zwei Variablen erhält:
Gleichung: 5x+7y+11z=1 (*)
Der BA liefert: -2·7+3·5=1=ggT(5;7)=u; also x_k=3-7k; y_k= -2+5k; in (*): 1u+11z=1
Ohne BA erhält man hier sofort die spezielle Lösung; mit Satz2.2 also u_l=-10-11l; z_l=1+l
Eingesetzt in (*): (-10- 11l)[5·x_k+7·y_k]+(1+l)·11
=(-10-11l)(3-7k)·5+(-10-11l)(-2+5k)·7+(1+l)·11=1

Mit k=l=0 erhält man als spezielle Lösung(-30½20½ 1); mit k=l=1 erhält man(84½-63½2); mit k=0 und l=1 ergibt sich (-63½42½2) als Lösung usw. usw.

Man versuche einmal, einige Lösungen von 6x+9y-5z-10u=7 herauszufinden.
z.B.: (28½-14½7½0); (28½-14½21½-7); (45½-27½12½-4)

Download Kap_2(64 KB)

Copyright © Michael Dorner, Nov. 2000.