Vorlesung Elementare Zahlentheorie WS 2003/04
Donnerstag, den 11.12.03 (AK)


[Zurück zur Protokollübersicht]
[Das Protokoll ist noch nicht redigiert.]


§8 Analyse des EA/XEA

Teil I: Größen

Teil II: Algebraische Analyse


Schema des EA und XEA:
ri = xi a + yi b

a:=r-1 1=:x-1 0=:y-1
b:=r0 0=:x0 1=:y0
r-1-Q0r0=:r1 x-1-Q0x0=:x1 y-1-Q0y0=:y1
r0-Q1r1=:r2 x0-Q1x1=:x2 y0-Q1y1=:y2
... ... ...
rn-2-Qn-1rn-1=:rn xn-2-Qn-1xn-1=:xn yn-2-Qn-1yn-1=:yn
rn-1-Qnrn=:rn+1 xn-1-Qnxn=:xn+1 yn-1-Qnyn=:yn+1
rn-Qn+1rn+1=:rn+2 xn-Qn+1xn+1=:xn+2 yn-Qn+1yn+1=:yn+2


Fragen
F1: Gilt ri=xia+yib für "alle" i?
F2: Was heißt hier "alle"?
F3: Konvergiert die Folge (r-1,r1,r2,...)? Gegen Null?
F4: Spielt die Reihenfolge von a,b eine Rolle bei diesen Fragen, d.h. vgl. Schema zu (a,b) mit Schema zu (b,a).
F5: Was sind die ri,Qi,xi,yi für Elemente? Was wird vorgeschreiben und was wird dann definiert?
F6: Was bedeutet es (was folgt), wenn rn+1=0 ist (eventl. "erstmals")

A6: Sind a,b,Qi,riÎN0 für i=-1,...,n im Schema für EA und ist rn+1=0, so ist g:=rn ein ggT in N0 von a und b.
Beweis

i)Von unten: Letzte Zeile:rn| rn und 0(=rn+1). Daraus folgt, dass auch rn|rn-1 .

Vorletzte Zeile: rn | rn-1 und rn, d.h. auch rn|rn-2
...
rn | a=r-1 und b=r0.

ii)Es sei h|a und h|b in N0. Z.z. h|rn.
Von oben: Erste Zeile: h|r-1 und ro d.h. auch h|r1

Zweite Zeile: h|r1 und r0, d.h. h|r2
...
h|rn


Erinnerung:

Definition: g ist ein ggT in M von (a,b) wenn g|a und g|b gilt und für ein weiteres k mit k|a und k|b gilt: k|g.

F:Wo bin ich?
A:In einem Kommutativen Monoid M (.,1) mit Kürzungsregel.

F:Wie eindeutig ist ein ggT?
A:Es seinen g,k ggT's von (a,b) in M.
Es folgt g|k und k|g,d.h. k=gx und g=ky für gewisse (es existieren) x,yÎM.
Einsetzten ergibt: k=kyx und g=gxy
Kürzungsregel ergibt: 1=yx und 1=xy
d.h. x,yÎE(M)

Ergebnis: In einem kommutativen Monoid mit Kürzungsregel unterscheiden sich ggT's nur um Einheiten: ggT(a,b)=gE(M)

Bemerkung: In N nur 1ÎE(N)
In Z nur -1,1ÎE(Z)

[Beispiel mit Kürzungsregel: Intergritätsbereiche (d.h. komm. R-m-1 ohne Nullteiler.): Z,K[x] ]

F:Dasselbe ohne Kürzungsregel? Gegenbeispiel? Ring mit Nullteiler?
(z.B. Matritzen, Innere direkte Summe zweier Ringe)

F.7.1: Gilt A6 für a,b,Qi,riÎR: kommutativer R-m-1?
A.7.1: Durch die Wahl der QiÎR sind die ri+1ÎR festgelegt!


[Bemerkung: Im üblichen EA für IN werden die Qi so gewählt, dass 0£ri+1<ri ist. (D.h. EA bricht ab.)
Für den EA in IR ist im Fall: a=Ö2ÎIR, b=1ÎIR, QiÎIN, 0£ ri+1 <riÎIR der EA nicht abbrechend.]

F8:Wann bricht der EA ab?

F9: Betrachte 1.Schema mit a,b,Q0,Q1,Q2,...,Qn. (für festes n)
Betrachte 2.Schema mit a',b',Q0,Q1,Q2,...,Qn aber rn+1=0 (für festes n)

F.9.1: Gibt es solche a',b'ÎR? Wie errechnen sich "diese"?

A.9.1:Wenn rn vorgegeben, so a',b' eindeutig bestimmt (errechenbar von unten her).

F.9.2:Formel?

F.9.3:Wie ändern sich a',b' bei Änderung von rn? Was bleibt invariant bei Änderung von rn? Der Quotient a'/b'?

A.9.2:Antwort-Versuche

1)r-1-Q0r0=r1, a'/b'=r-1/r0=Q0+r1/r0=Q0+1/(r0/r1)=Q0+1/(Q1+1/(r1/r2))
r0-Q1r1=r2, ro/r1=Q1+r2/r1=Q1+1/(r1/r2)
r1-Q2r2=r3, r1/r2=Q2+r3/r2=Q2+1/(r2/r3)
...


2)F1 wird (wohl) mit Ja beantwortet. Also gilt 0=rn+1=xn+1a'+yn+1b' für dieselben xi,yi (i£n+1) wie für (a,b). D.h. a'/b'=-yn+1/xn+1.


Zur vorangehenden Stunde (09.12.03),
zur nächsten Stunde (12.12.03),
zur Protokollübersicht.