Elementare Zahlentheorie
Protokoll der Sitzung
vom 16.12.03 (SM)
[Zurück zur
Protokollübersicht]
[Das Protokoll ist noch nicht redigiert.]
Euklidischer Algorithmus (EA): Schema und Durchführung
Fragen:
F10: Wenn rn+1= 0 ist, ist dann xn+1 ≠ 0?
F11: Ist Z Lösungsmenge von g= xa+ yb ?
F12: Haben xi und yi die gleichen Vorzeichen?
F13: Sind alle Paare (xi,yi) teilerfremd ?
F14: Konvergiert die Folge A2, A3... gegen a/b ?
A13: Ja, da die Determinante immer gleich [(xi, yi),(xi+1, yi+1)](2x2) +- 1 ist.
zu F10 und F12: F10': Wie "wachsen" die |xi|, |yi| mit i?
( Die Determinationsformel lautet: xi-1 - Qixi = xi+1, für yi+1 analog.)
| i |
x |
y |
| -1 |
1 |
-0 |
| 0 |
-0 |
1 |
| 1 |
1 |
-Q0 |
| 2 |
-Q1 |
1+Q0Q1 |
Betrachte den EA für a,b ∈ N mit Qi isin N (üblicher EA).
Zu zeigen ist, dass xi und xi+1 verschiedene Vorzeichen haben.
Induktions Verankerung: xi und xi+1 haben verschiedene Vorzeichen.
Induktion: xk+1 und xk+2 sind zu vergleichen.
Es ergibt sich aus der Definition: xk- Qk+1xk+1= xk+2 und xk-1- Qkxk= xk+1
Da die Voraussetzung nicht ausreicht muß sie verschärft werden:
Es sei xi > 0 für i > 1 ungerade und xi < 0 für i >2 gerade.
Es folgt, dass wenn k ungerade ist, k+1 gerade ist.
xk+1 = xk-1 - Qkxk < 0 da xk-1 kleiner und Qk und xk größer 0 sind.
Analog folgt, dass wenn k gerade ist, ist k+1 ungerade.||
Folgerung:
|xk+1| = |xk-1| + Qk*|xk| > |xk-1| + |xk| = fk+1.
"Alle Qi = 1" ergibt:
| -1 |
1 |
0 |
| 0 |
0 |
1 |
| 1 |
1 |
Q0 |
| 2 |
1 |
1+Q0Q1 |
| 3 |
2 |
|
| 4 |
3 |
|
| 5 |
5 |
|
Wobei die Fibonacci- Folge so definiert ist: f1 := 1, f0 := 0, fi-1 + fi =: fi+1.
A10:
xk ist größer 0 für alle k > 1. Analog folgt für die yi :
Mit dem gleichen Beweis ergibt sich: yi < 0 für i > 1 ungerade und yi > 0 für i > 0 gerade.
Die Folgerung lautet: |yk+1| = |yk+1| + Qk|yk| > |yk-1| + |yk| = fk+2.
zu F11:
A)
Zum allgemeinen Teil betrachtet man die Lösungsmenge einer linearen Gleichung über Z mit zwei Unbekannten (aus Z).
Mit ax + by = c (a, b, c aus Z gegeben)
und gesucht L:= {(x, y) ∈ Z x Z | ax + by = c }.
A11:
Betrachte zuerst H (homogen): H:= {(x, y) ∈ Z xZ | ax + by = 0 }.
H ist ein Z-Teilmodul von Z1x2.
Im Fall (a, b) = (0, 0) ist H = Z1x2.
Im Fall(a, b) ≠ (0, 0) ergibt sich (-b, a) ∈ H \ (0, 0), es folgt ∈ H, es folgt φ*(-b/g, a/g) ∈ H.
Somit ergibt sich Z*(-b/g, a/g) < H.
Wenn b ≠ 0 ist, so folgt für (x, y) ∈ H:
y = -a/b*x = -a/g / b/g *x in Q.
Frage: Für welche x ∈ Z ist y ∈ Z ?
Aus (b/g)*y = (a/g)*x (in Z) folgt (mit (b/g) und (a/g) teilerfremd):
x = (b/g)*φ und y = (a/g)*β = -(a/g)*φ (φ und β aus Z).
Also folgt: -φ = β.
Somit ergibt sich: (x,y) = (b/g, a/g)*φ.
Das Fazit lautet: H = Z* (-b/g, a/g) = Z* (b/g, -a/g).
Zusatzfrage: Existieren weitere (x0, y0) mit H = Z*
(x0, y0) ? NEIN!
B)
Anwendung auf den ggT mit g = axn + byn bei üblichen EA (xn+1 = 0).
Wenn der übliche EA mit rn+1 = 0 endet, ist rn = g ein ggT von (a, b).
Also sind rn : g = axn + byn und (xn+1, yn+1) ∈ H : 0 = ax + by teilerfremd.
Daraus folgt: (xn, yn) = (-b/g, a/g) oder (b/g, -a/g).
![5]()
Nach F10 und F12 ist |xn+1| > |xn| und |yn+1| > |yn|. Also berechnet der Algorithmus die optimale Lösung.
L = H + (x, y) für jede beliebige (spezielle) Lösung in L.
Beweis:
(>)
Gilt für (x', y') ∈ H (x+x', y+y') ∈ L ?
a*(x + x') + b*(y + y') = (ax + by) + (ax' + by') = c + 0 = c .
(<) selbst... ||.
zu F14:
Gegeben seien ein ä (> 0) ∈ R []. Der übliche EA breche nicht ab, also ä ∈ R\ Q.
Für a:= ä und b:= 1 mache EA mi Qi ∈ N.
Definition. A = - yn+1 / xn+1.
[Motivation:
Vergleiche EA für a,b,ä mit EA für ä, a = ä, b = 1, wobei die Qi bis i < n (aber rn+1 = 0) gleich sind.
Also sind xi = xi und yi = yi, für i < n+1.
Jetzt ist ri = axi + byi, wie immer für i < n+1, insbesondere i = n+1 und 0 = axi + byi,
also a/b = -yn+1 / -xn+1 = ä = - yn+1 / xn+1 =: An .]
§ 7 (Eukl. Algorithmus und Kettenbrüche) wird später fortgesetzt.
Zur vorangehenden
Stunde (12.12.03),
zur nächsten
Stunde (18.12.03) (§ 8: PZT),
zur Protokollübersicht.