| Autor |
Beitrag |
    
dakir
| | Veröffentlicht am Montag, den 30. Oktober, 2000 - 10:12: | 
|
Hallo,
gegeben sei eine Gleichung mit ganzzahligen Koeffizenten a, b, c.
ax + by = c.
Gesucht werden die ganzzahligen Lösungen dieser Gleichung.
Ich suche nun einen Beweis dafür, daß folgende Prozedur die Lösungen dieser Gleichung liefert:
Man schreibe die Zahl a / b in der Form
a / b = a0 + 1 / (a1 + 1 / (a2 + 1 / (a3 + 1 / ... + 1 / an)...)). Diese Darstellung heißt im Englischen "continued fractions", den deutschen Begriff kenn ich leider nicht(vielleicht Kettenbruch). Eine kurze Schreibweise dieser Zahl ist [a0; a1, a2, ..., an]. Die ganzen Zahlen Pk, Qk seien definiert durch Pk / Qk = [a0; a1, ..., ak]. Man bestimme P(n-1) sowie Q(n-1). Die Lösungen der Gleichung sind dann gegeben durch:
x = (-1)^(n+1) * c * Q(n-1) + bt
y = (-1)^n * c * P(n-1) - at
Danke schon mal im voraus!
Daniel |
Matroid (Matroid)
| | Veröffentlicht am Dienstag, den 31. Oktober, 2000 - 20:46: |
|
Hi dakir,
das ist ja mal ganz etwas anderes.
Ich habe mir mal ein Beispiel gemacht:
3x+4y=5
Der Kettenbruch dazu ist [0;1,3]
also n=2
Pn-1/Qn-1 = P1/Q1 = [0;1] = 0 + 1/1 = 1.
Mit P1=1 und Q1=1
bekommt man
x = (-1}3 * 5 * 1 + 4*t
y = (-1}2 * 5 * 1 - 3*t
und kürzer:
x = -5 + 4*t
y = 5 - 3*t
Tatsächlich stelle ich fest, daß für alle teZ die Gleichung 3x+5y=5 erfüllt ist.
Aber hätte ich nicht auch P1=2 und Q1=2
wählen können? Dann hätte ich
x = (-1}3 * 5 * 2 + 4*t
y = (-1}2 * 5 * 2 - 3*t
also
x = -10 + 4*t
y = 10 - 3*t
Doch diese x und y sind keine Lösungen.
Dann noch ein Beispiel:
2x+4y=5
Dieses hat offensichtlich keine (ganzzahligen) Lösungen.
Der Kettenbruch für 2/4 ist [0;2] = 0 + 1/2
Also n=1 und nun kann man P0=0 und Q0=1
setzen damit P0/Q0 = 0 ist.
Dann ist
x = (-1}2 * 5 * 1 + 4*t
y = (-1}1 * 5 * 0 - 2*t
kürzer
x = 5 + 4*t
y = - 2*t
Diese x,y ergeben aber keine Lösungen, denn es ist hierfür immer 2x+4y=10.
Nicht überraschend, denn ich hatte auch keine Lösungen erwartet. In diesem Beispiel war mit der Wahl von P und Q ja schon etwas falsch.
Ich nehme daher an, daß zu dem Kettenbruchverfahren noch folgende zwei Regeln ergänzt werden müssen:
A) Wähle Pn-1 und Qn-1 teilerfremd
B) wenn an-1 = 0, dann gibt es keine Lösung.
Wie könnte man nun den Beweis führen?
Vorschlag: Induktion über n, also die Länge des Kettenbruchs.
Wenn a/b durch einen Kettenbruch der Länge 1 dargestellt werden kann .... (mal genau hinschreiben).
Sei nun a/b durch einen Kettenbruch der Länge n+1 dargestellt, dann ...
Versuch doch mal ...
Dadurch kann man evtl. zeigen, daß die so berechneten x und y Lösungen sind.
Dadurch wird aber nicht gezeigt, daß es so eine Kettenbruchdarstellung für alle a/b gibt. Und es wird auch nicht gezeigt, daß für eine rationale Zahl stets nur genau eine Kettenbruchdarstellung endlicher Länge existiert. Schließlich wird dadurch auch nicht gezeigt, daß man mit diesen x und y wirklich alle Lösungen der Ausgangsgleichung hat.
Da wäre also noch viel zu tun.
Darüber wurden vor 20 Jahren noch Dissertationen geschrieben.
Gruß
Matroid |
|
