Zum Inhalt springen

Kurs:Zahlentheorie (Osnabrück 2008)/Vorlesung 3




Der euklidische Algorithmus

Es seien Elemente a,b (mit b≠0) eines euklidischen Bereichs R mit euklidischer Funktion δ gegeben. Dann nennt man die durch die Anfangsbedingungen  r0=a  und  r1=b  und die mittels der Division mit Rest

ri=qiri+1+ri+2

rekursiv bestimmte Folge ri die Folge der euklidischen Reste.



Satz  

Es seien Elemente r0=a,r1=b≠0 eines euklidischen Bereiches R mit euklidischer Funktion δ gegeben. Dann besitzt die Folge ri,  i=0,1,2,…,  der euklidischen Reste folgende Eigenschaften.

  1. Es ist ri+2=0 oder δ(ri+2)<δ(ri+1).
  2. Es gibt ein (minimales)  k≥2  mit  rk=0. 
  3. Es ist
    ggT⁡(ri+1,ri)=ggT⁡(ri,ri−1).
  4. Es sei  k≥2  der erste Index derart, dass  rk=0  ist. Dann ist
    ggT⁡(a,b)=rk−1.

Beweis  

  1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
  2. Solange  ri≠0  ist, wird die Folge der natürlichen Zahlen δ(ri) immer kleiner, sodass irgendwann der Fall  ri=0  eintreten muss.
  3. Wenn t ein gemeinsamer Teiler von ri+1 und von ri+2 ist, so zeigt die Beziehung
    ri=qiri+1+ri+2,

    dass t auch ein Teiler von ri und damit ein gemeinsamer Teiler von ri+1 und von ri ist. Die Umkehrung folgt genauso.

  4. Dies folgt aus (3) mit der Gleichungskette
    ggT⁡(a,b)=ggT⁡(b,r2)=ggT⁡(r2,r3)=…=ggT⁡(rk−2,rk−1)=ggT⁡(rk−1,rk)=ggT⁡(rk−1,0)=rk−1.
◻


Als Beispiel zum Euklidischen Algorithmus lösen wir die folgende Aufgabe.


Aufgabe

Bestimme in ℤ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von 1071 und 1029.


Lösung


Der größte gemeinsame Teiler von 1071 und 1029 wird mit dem Euklidischen Algorithmus wie folgt berechnet:

1071=1⋅1029+42,
1029=24⋅42+21,
42=2⋅21+0.

Der größte gemeinsame Teiler von 1071 und 1029 ist somit 21.



Für ein weiteres Beispiel siehe hier.


Aufgabe

Bestimme in ℤ[i] mithilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von 7+4i und 5+3i.


Lösung


Wir setzen  a=7+4i  und  b=5+3i  und führen die Division mit Rest a/b durch. Es ist (in ℂ oder in ℚ[i])

ab=7+4i5+3i=(7+4i)(5−3i)(5+3i)(5−3i)=47−i34=4734−134i.

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist 1, sodass die Division mit Rest ergibt:

a=1⋅b+r mit r=a−b=2+i.

Die nächste durchzuführende Division ist somit

br=5+3i2+i=(5+3i)(2−i)(2+i)(2−i)=13+i5=135+15i.

Die beste Approximation für diese komplexe Zahl mit einer ganzen Gaußschen Zahl ist 3, sodass die Division mit Rest ergibt:

b=3⋅r+s mit s=b−3r=5+3i−3(2+i)=−1.

Da dies eine Einheit ist, sind a=7+4i und b=5+3i teilerfremd.





Satz  

Es sei R ein Hauptidealring. Dann gilt:

Elemente a1,…,an besitzen stets einen größten gemeinsamen Teiler d, und dieser lässt sich als Linearkombination der a1,…,an darstellen, d.h. es gibt Elemente  r1,…,rn∈R  mit  r1a1+r2a2+⋯+rnan=d. 

Insbesondere besitzen teilerfremde Elemente a1,…,an eine Darstellung der 1.

Beweis  

Es sei  I=(a1,…,an)  das von den Elementen erzeugte Ideal. Da wir in einem Hauptidealring sind, handelt es sich um ein Hauptideal; es gibt also ein Element d mit  I=(d).  Wir behaupten, dass d ein größter gemeinsamer Teiler der a1,…,an ist. Die Inklusionen  (ai)⊆I=(d)  zeigen, dass es sich um einen gemeinsamen Teiler handelt. Es sei e ein weiterer gemeinsamer Teiler der a1,…,an. Dann ist wieder  (d)=I⊆(e),  was wiederum e∣d bedeutet. Die Darstellungsaussage folgt unmittelbar aus  d∈I=(a1,…,an). 

Im teilerfremden Fall ist  I=(a1,…,an)=R. 

◻



Lemma  

Es sei R ein Hauptidealbereich und  a,b,c∈R.  Es seien a und b teilerfremd und a teile das Produkt bc.

Dann teilt a den Faktor c.

Beweis  

Da a und b teilerfremd sind, gibt es nach dem Lemma von Bézout Elemente  r,s∈R  mit  ra+sb=1.  Die Voraussetzung, dass a das Produkt bc teilt, schreiben wir als  bc=da.  Damit gilt

c=c1=c(ra+sb)=cra+csb=acr+ads=a(cr+ds),

was zeigt, dass c ein Vielfaches von a ist.

◻



Satz  

Es sei R ein Hauptidealbereich. Dann ist ein Element genau dann prim,

wenn es irreduzibel ist.

Beweis  

Ein Primelement in einem Integritätsbereich ist nach Lemma 1.15 stets irreduzibel. Es sei also umgekehrt p irreduzibel, und nehmen wir an, dass p das Produkt ab teilt, sagen wir  pc=ab.  Nehmen wir an, dass a kein Vielfaches von p ist. Dann sind aber a und p teilerfremd, da eine echte Inklusionskette  (p)⊂(p,a)=(d)⊂R  der Irreduzibilität von p widerspricht. Damit teilt p nach dem Lemma von Euklid den anderen Faktor b.

◻



Lemma  

In einem Hauptidealbereich lässt sich jede Nichteinheit  a≠0  als ein Produkt von irreduziblen Elementen darstellen.

Beweis  

Angenommen, jede Zerlegung  a=p1⋯pk  enthalte nicht irreduzible Elemente. Dann gibt es in jedem solchen Produkt einen Faktor, der ebenfalls keine Zerlegung in irreduzible Faktoren besitzt. Wir erhalten also eine unendliche Kette a1=a,a2,a3,…, wobei an+1 ein nicht-trivialer Teiler von an ist. Somit haben wir eine echt aufsteigende Idealkette

(a1)⊂(a2)⊂(a3)⊂⋯.

Die Vereinigung dieser Ideale ist aber nach Aufgabe ***** ebenfalls ein Ideal und nach Voraussetzung ein Hauptideal. Dies ist ein Widerspruch.

◻



Satz  

In einem Hauptidealbereich lässt sich jede Nichteinheit  a≠0  darstellen als ein Produkt von Primelementen. Diese Darstellung ist eindeutig bis auf Reihenfolge und Assoziiertheit. Wählt man aus jeder Assoziiertheitsklasse von Primelementen einen festen Repräsentanten p, so gibt es eine bis auf die Reihenfolge eindeutige Darstellung  a=u⋅p1r1⋅p2r2⋯pkrk,  wobei u eine Einheit ist und die pi Repräsentanten sind.

Beweis  

Die erste Aussage folgt direkt aus Lemma 3.6 und Satz 3.5.

Die behauptete Eindeutigkeit bis auf Umordnung bedeutet, dass, wenn

a=u⋅p1⋯pk=v⋅q1⋯qm

zwei Primfaktorzerlegungen sind, dann  k=m  ist und es eine Permutation τ auf {1,…,k} derart gibt, dass pi und qτ(i) für alle  i∈{1,…,k}  assoziiert sind. Wir beweisen diese Aussage durch Induktion über k. Es sei zuerst  k=0  (das sei zugelassen). Dann steht links eine Einheit, also muss auch rechts eine Einheit stehen, was  m=0  bedeutet.

Es sei also  k>0  und die Aussage sei für alle kleineren k bewiesen. Die Gleichung (∗) bedeutet insbesondere, dass pk das Produkt rechts teilt. Da pk prim ist, muss pk einen der Faktoren rechts teilen. Nach Umordnung kann man annehmen, dass qm von pk geteilt wird. Da qm ebenfalls prim ist, sind qm und pk assoziiert. Also ist

qm=wpk

mit einer Einheit w und man kann die Gleichung (∗) nach pk kürzen und erhält

u⋅p1⋯pk−1=(vw)⋅q1⋯qm−1.

Die Induktionsvoraussetzung liefert dann  k−1=m−1  und dass jedes pi zu einem qj assoziiert ist.

◻


Diesen Satz kann man auch so ausdrücken, dass Hauptidealbereiche faktoriell sind im Sinne der folgenden Definition. Für solche Bereiche gilt ganz allgemein, dass die Primfaktorzerlegung eindeutig ist.


Ein Integritätsbereich heißt faktorieller Bereich, wenn die beiden folgenden Eigenschaften erfüllt sind.

  1. Jedes irreduzible Element in R ist prim.
  2. Jedes Element a∈R, a≠0, ist ein Produkt aus irreduziblen Elementen.



Korollar  

Jede positive natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen.

Beweis  

Dies folgt sofort aus Satz 3.7.

◻



Korollar  

Es sei R ein Hauptidealbereich und seien a und b zwei Elemente ≠0 mit Primfaktorzerlegungen

a=u⋅p1r1⋅p2r2⋯pkrk und b=v⋅p1s1⋅p2s2⋯pksk

(wobei die Exponenten auch 0 sein können und u,v Einheiten sind). Dann gilt a∣b genau dann, wenn  ri≤si  für alle Exponenten  i=1,…,k  ist.

Beweis  

Wenn die Exponentenbedingung erfüllt ist, so ist  si−ri≥0,  und man kann

b=a(vu−1p1s1−r1⋯pksk−rk)

schreiben, was die Teilbarkeit bedeutet. Die Umkehrung folgt aus der Eindeutigkeit der Primfaktorzerlegung in Hauptidealbereichen (siehe Satz 3.7).

◻



Satz  

Es sei R ein Hauptidealbereich und  p≠0  ein Element. Dann sind folgende Bedingungen äquivalent.

  1. p ist ein Primelement.
  2. R/(p) ist ein Integritätsbereich.
  3. R/(p) ist ein Körper.

Beweis  

Die Äquivalenz (1) ⇔ (2) gilt in jedem kommutativen Ring (auch für p=0), siehe Aufgabe *****, und (3) impliziert natürlich (2). Es sei also (1) erfüllt und sei  a∈R/(p)  von 0 verschieden. Wir bezeichnen einen Repräsentanten davon in R ebenfalls mit a. Es ist dann  a∉(p)  und es ergibt sich eine echte Idealinklusion  (p)⊂(a,p).  Ferner können wir  (a,p)=(b)  schreiben, da wir in einem Hauptidealring sind. Es folgt  p=cb.  Da c keine Einheit ist und p prim (also nach Lemma 1.15 auch irreduzibel) ist, muss b eine Einheit sein. Es ist also  (a,p)=(1),  und das bedeutet modulo p, also in R/(p), dass a eine Einheit ist. Also ist R/(p) ein Körper.

◻


<< | Kurs:Zahlentheorie (Osnabrück 2008) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)