3.1 Homomorphismen, Ideale und Faktorringealgebra/Algebra_2012/Skript/algeb… · Algebra I c Rudolf Scharlau, 2002 – 2012 123 3.1 Homomorphismen, Ideale und Faktorringe Aus dem

Algebra I c Rudolf Scharlau, 2002 2012 123

3.1 Homomorphismen, Ideale und Faktorringe

Aus dem Einleitungskapitel 1.5 sind uns folgende Begriffe bereits bekannt: Ring,kommutativer Ring mit Eins, Teilring (Unterrring), Einheiten eines Ringes, Ein-heitengruppe, Nullteiler, nullteilerfreier Ring, der Restklassenring Z/mZ. Untereinem Integritatsbereich wollen wir immer einen nullteilerfreien Ring, in dem 0 = 1ist, verstehen.

Beim weiteren Aufbau der Ringtheorie lauft vieles analog zum Fall der Grup-pen oder Vektorraume; die grundlegenden Begriffe und Konstruktionen sind diegleichen oder ahnlich. So werden Homomorphismen eingefuhrt als strukturerhal-tende Abbildungen. Jeder Homomorphsimus besitzt einen Kern, der ein

Unter-

objekt des Definitionsbereiches ist. Die Kerne von Ringhomomorphismen heienIdeale. Das sind genau diejenigen Unterobjekte von Ringen, nach denen eine Fak-torstuktur (Quotientenstruktur) gebildet werden kann. Sie entsprechen also denNormalteilern in Gruppen. Als Konsequenz dieses Sachverhaltes ergibt sich wiebei den Gruppen der Homomorphiesatz. Bei der Entwicklung dieser Grundlagenfassen wir uns generell etwas kurzer als fruher bei den Gruppen.

Im zweiten Teil dieses Unterkapitels folgen weitere Begriffe, die (grotenteils)spezifisch fur Ringe sind: Hauptideale, Schnitte und Summen von Idealen so-wie die Begriffe Primideal und maximales Ideal; diese Ideale kann man an ih-ren Faktorringen erkennen. Wir beschlieen diesen Abschnitt mit einer ausfuhr-lichen Diskussion des Chinesischen Restsatzes: fur die Restklassenringe Z/mZsetzt das nicht nur den Abschnitt 1.5 fort, sondern hat auch Beziehungen zuKapitel 2.1 (Zyklische Gruppen) sowie 2.7 (Semidirekte Produkte, Automorphis-men zyklischer Gruppen). Wir tragen an dieser Stelle auch die Behandlung derEulerschen Phi-Funktion nach, deren

Multiplikativitat aus dem Chinesischen

Restsatz folgt.

Die im folgenden betrachteten Ringe haben in aller Regel ein Einselement; wirwollen das aber nicht ausdrucklich voraussetzen. Letzlich haben wir kommutativeRinge im Auge, werden aber den nicht-kommutativen Fall mit behandeln, solangees keinen zusatzlichen Aufwand macht.

Definition 3.1.1 (Homomorphismus, Isomorphismus)

a) Es seien R und S zwei Ringe. Eine Abbildung : R S heit Ringhomo-morphismus, falls fur alle x, y R gilt

(x+ y) = (x) + (y) und (x y) = (x) (y) .

b) Ein Isomorphismus eines Ringes R auf einen Ring S ist ein bijektiver Ho-momorphismus : R S. Falls R = S ist, spricht man von einem Auto-morphismus dieses Ringes.

c) Zwei Ringe R und S heien isomorph, falls ein Isomorphismus von R auf Sexistiert.


Beispiele 3.1.2 (Ringhomomorphismen)

(1) Wir betrachten den Funktionenring F(M,R), fur eine beliebige MengeM , die als Definitionsbereich dient. Fur festes a M ist die Abbildunga : F(M,R) R, f f(a) ein Ringhomomorphismus, der sogenannteAuswertungs-Homomorphismus, kurz die Auswertung, an der Stelle a M .

(2) Die Abbildung Z Z/mZ, x [x]m := x +mZ ist ein surjektiver Ring-homomorphismus, der sogenannte kanonische Homomorphismus.

(3) Die Abbildung C C, x + iy = z z := x iy (x, y R), also diekomplexe Konjugation, ist ein Automorphismus von C.

(4) Fur jeden (nicht-kommutativen) Ring R und jede Einheit u R ist die Ab-bildung iu : R R, x uxu1 ein Automorphismus von R, ein sogenann-ter innerer Automorphismus. (Man denke insbesondere an R = End(V )bzw. R = Mn(K) fur einen Korper K und einen K-Vektorraum V .)

(5) Wenn B eine feste Basis des endlich-dimensionalen K-Vektorraumes V ist,so ist die Abbildung End(V ) Mn(K), f MBB (f) (Matrix von fbezuglich B) ein Ringisomorphismus.Diese Aussage fasst einige Satze der Linearen Algebra uber den Zusammen-hang zwischen Linearen Abbildungen und Matrizen zusammen (fur den Fallder Endomorphismen).

Der folgende Satz ist inzwischen reine Routine. Alles verlauft vollig analog zuden linearen Abbildungen zwischen Vektorraumen oder den Gruppenhomomor-phismen sowie dem Isomorphiebegriff fur Vektorraume bzw. Gruppen.

Satz 3.1.3 a) Es seien : R S und : S K Ringhomomorphismen.Dann ist auch : R K ein Homomorphismus.

b) Es sei : R S ein Ringisomorphismus. Dann ist auch 1 : S R einHomomorphismus und damit ein Isomorphismus.

c) Isomorphie R = S von Ringen ist eine Aquivalenzrelation.

Als nachstes widmen wir uns denjenigen Unterstrukturen eines Ringes, die alsKerne von Ringhomomorphismen auftauchen. Im Falle der Gruppen waren die-ses die normalen Untergruppen oder Normalteiler, aber keine beliebigen Unter-gruppen. Hier ist es ahnlich, wie wir gleich sehen werden. Ein Homomorphismuszwischen zwei Ringen ist insbesondere ein Homomorphismus der unterliegendenabelschen Gruppen, der Kern also insbesondere eine Untergruppe. (Normalitatspielt keine Rolle, da es sich um kommutativen Gruppen handelt.) Klar ist auch,dass ein Kern abgeschlossen ist unter der Multiplikation. Bezuglich der Multipli-kation gilt sogar noch mehr, und das ist Gegenstand der nachsten Definition.


Definition 3.1.4 Eine Teilmenge I eines Ringes R heit ein Ideal, falls folgendesgilt:

(I 1) I ist eine Untergruppe von (R,+).

(I 2) r R, a I = r a I, a r I.

Man spricht von einem Linksideal, falls statt (I 2) lediglich die folgende Bedingungerfullt ist:

(I 2) r R, a I = r a I.

Hier nun der Satz, der diese Definition motiviert:

Satz 3.1.5 Der Kern

Ker = {x R | (x) = 0} R

eines Ringhomomorphismus : R S ist ein Ideal.

Beweis: Da ein Ringhomomorphismus insbesondere ein Homomorphismus derunterliegenden additiven Gruppen ist, ist der Kern nach Satz 1.4.4 eine Unter-gruppe von (R,+), d.h. die erste Idealeigenschaft (I 1) gilt. Wenn r R, a Ker ist, so ist (r a) = (r) (a) = (r) 0 = 0, also r a Ker, wie fur(I 2) gewunscht. Das gleiche gilt fur a r.

Beispiele 3.1.6 (Ideale)

(1) Fur jeden kommutativen Ring R und jedes a R ist Ra = {ra | r R}ein Ideal in R, ein sogenanntes Hauptideal mit Erzeuger a. Es ist auch dieBezeichnung Ra =: (a) ublich.

(2) Im Ring Z sind die Ideale genau die Vielfachenmengen Zm = {zm | z Z},also samtlich Hauptideale. Jedes Ideal ist namlich eine Untergruppe, undjede Untergruppe von Z ist nach 2.1.5 von dieser Bauart, namlich zyklisch.Es ist ubrigens auch unabhangig von dieser expliziten Beschreibung klar,dass in Z jede Untergruppe sogar ein Ideal ist. Denn die Idealeigenschaft(I 2) folgt aus den Untergruppeneigenschaften, weil die Multiplikation in Zauf die fortgesetzte Addition und Bildung von Negativen (additiven Inver-sen) zuruckgefuhrt werden kann.

(3) Im Funktionenring F(M,R) ist fur jede Teilmenge N M des Definitions-bereichs die Menge {f F(M,R) | f|N = 0} der auf N verschwindendenFunktionen ein Ideal. Fur einelementiges N = {a} ist das der Kern desAuswertungs-Homomorphismus a aus Beispiel 3.1.2 (1).


(4) Im (nicht-kommutativen) Endomorphismenring End(V ) eines Vektorraumsder Dimension 2 ist fur jeden Unterraum U V die Teilmenge {f End(V ) | f|U = 0} der auf U verschwindenden Endomorphismen ein Links-ideal, aber fur {0} = U = V kein zweiseitiges Ideal.

Die folgende Definition ist nach den Beipielen (1) und (2) naheliegend:

Definition 3.1.7 Ein Hauptidealring ist ein Integritatsbereich R, in dem jedesIdeal I ein Hauptideal ist, d.h. es existiert ein a R mit I = Ra.Man beachte, dass ein Hauptidealring nach Definition (zusatzlich) nullteilerfreiist. Wie wir in Beispiel 3.1.6 (2) gesehen haben, ist der Ring Z der ganzen Zah-len ein Hauptidealring. Das gleiche gilt (mit einem analogen Grund, namlich derDivision mit Rest) fur den Polynomring uber einem Korper. Wir werden Haupt-idealringe in Abschnitt 3.3 weiter studieren.

Wir machen noch ein paar Bemerkungen uber den Zusammenhang zwischen den Be-griffen

Ideal und

Teilring. Bei den von uns gewahlten Definitionen ist jedes Ideal

ein Teilring (siehe Definition 1.5.4), denn die Eigenschaft (I 2) ist eine Verscharfungvon (TR2). Wenn wir allerdings, und dafur gibt es gute Grunde, von einem Teilringvon R verlangen, dass er das Einselement 1R enthalt, so bleibt fur ein Ideal I, dasauch Teilring sein soll, nur noch die Moglichkeit I = R ubrig. Denn es ist nach (I 2)r = r1R I fur jedes r R.Es macht ubrigens Sinn, von einem Ideal I ausdrucklich zu verlangen, dass I = R ist.Denn fur I = R besteht der Faktorring R/I nur aus der Null, und das sollte eigentlichinnerhalb der von uns betrachteten Klasse der Ringe mit Einselement ausgeschlossensein. Zumindest in einem Korper gilt jedenfalls 1 = 0. Trotzdem bleiben wir dabei,auch ganz R als Ideal anzusehen, weil das letztlich fur viele Formulierungen etwasbequemer ist.

Nun kommen wir zu den Faktorringen. Diese entstehen durch Aquivalenzklassen-bildung nach einem Ideal. Da jedes Ideal I in einem Ring R insbesondere eine Un-tergruppe von (R,+) ist, ist die Menge R/I der Nebenklassen a+I, a R, durch2.2.1 bereits definiert. Da (R,+) eine abelsche Gruppe ist, tragt R/I nach Satz2.2.12 sogar die Struktur einer Gruppe. In einer abelschen Gruppe ist namlichjede Untergruppe ein Normalteiler. (Erinnerung: in Wirklichkeit kannten wir dieGruppe R/I schon vor der allgemeinen Behandlung in 2.2.12, namlich aus derKonstruktion von Z/mZ sowie ggf. von Quotientenvektorraumen.) Es muss jetztalso noch die Multiplikation von Nebenklassen definiert werden, was vollig analogzur Addition, und vollig analog zum Fall von Z/mZ (siehe 1.2.11) geschieht. DieNebenklassen werden in Ringen oft auch als Restklassen bezeichnet, in Verallge-meinerung der Restklassen ganzer Zahlen (also der Elemente von Z/mZ).Satz 3.1.8 (Faktorring)

a) Es sei I ein Ideal im Ring R. Dann wird auf R/I durch

(a+ I) (b+ I) := a b+ I (a, b R)

eine Verknupfung sinnvoll definiert.


b) R/I zusammen mit der Restklassen-Addition und der unter a) definiertenRestklassen-Multiplikation ist ein Ring, der sogenannte Faktorring von Rnach I.

c) Die AbbildungI : R R/I, x x+ I

ist ein Ringhomomorphismus, der sogenannte kanonische Homomorphis-mus. Sein Kern ist gleich I.

Beweis: Zum Beweis von a) muss man bekanntlich folgendes zeigen: Wenn a, b

zwei weitere Ringelemente sind mit aa I, bb I, so ist auch abab I.Dieses rechnet man unmittelbar nach. Nachdem nun die Multiplikation auf R/Iwohldefiniert ist, rechnet man sofort nach, dass sich das Assoziativgesetz hierfursowie die beiden Distributivgesetze unmittelbar von R auf R/I ubertragen. Somitist b) gezeigt. Teil c) schlielich gilt nach Definition und wird lediglich zur Abrun-dung aufgefuhrt. Man sieht hier, dass jedes Ideal als Kern eines Homomorphismusauftaucht.

Wir kommen nun zu einem der grundlegenden Satze der allgemeinen Ringtheorie,dem Homomorphiesatz. Er ist vollig analog zum entsprechenden Satz fur Gruppenund kann in der Tat als eine Erganzung oder Weiterfuhrung des Homomorphie-satzes fur Gruppen in der speziellen Situation der Ringe, Ringhomomorphismenund Ideale angesehen werden.

Satz 3.1.9 (Homomorphiesatz fur Ringe)

a) Es sei : R S ein Ringhomomorphismus. Weiter sei I R ein Idealmit I Ker. Mit I bezeichnen wir weiterhin die kanonische ProjektionR R/I. Dann gibt es einen eindeutig bestimmten Ringhomomorphismus : R/I S mit = I , d.h. das Diagramm

R S

R/I

I

ist kommutativ.

b) Unter den Voraussetzungen von a) ist Bild = Bild. Insbesondere ist

surjektiv genau dann, wenn surjektiv ist.

c) Unter den Voraussetzungen von a) ist Ker = (Ker)/N . Insbesondereist injektiv genau dann, wenn N = Ker ist.


Beweis: zu a): Aus dem Homomorphiesatz fur Gruppen 2.2.13 folgt die Existenzeines eindeutigen Gruppenhomomorphismus : R S mit = I . Ausder Definition der Multiplikation auf R/I folgt unmittelbar, das sogar einRinghomomorphismus ist. Die Aussagen b) und c) stehen bereits in 2.2.13. Genau wie bei Gruppen ist der Homomorphiesatz ein Standard-Werkzeug, umIsomorphismen zu konstruieren. Hierfur wird der folgende Spezialfall des Satzesbenutzt:

Korollar 3.1.10 (Isomorphiesatz fur Ringe) Jeder surjektive Ringhomomor-phismus : R S induziert einen Isomorphismus R/Ker = S.

Der Homomorphiesatz und seine Folgerung, der Isomorphiesatz, werden uns mitweiterem Aufbau der Ringtheorie immer wieder begegnen, und wir werden nachund nach eine Fulle unterschiedlicher Anwendungen sehen. Hier ist eine ersteAnwendung. Wir erinnern an folgende Bezeichnung: Fur a Z und m N ist

[a]m := a+mZ Z/mZ .

die Restklasse (Kongruenzklasse) modulo m der Zahl a.

Beispiel 3.1.11 Fur m,n N mit m|n ist die Abbildung

Z/nZ Z/mZ, [x]n [x]m

wohldefiniert und ein surjektiver (Ring-)Homomorphismus.

Beweis: Es sei : Z Z/mZ die Abbildung x [x]m, also die kanonischeProjektion, und I = nZ. Dann sind alle Voraussetzungen des Homomorphiesatzeserfullt, und er liefert die gewunschte Aussage.

Wenn ein Ideal I in einem Ring R das Einselement 1R enthalt, so ist offensichtlichI = R, wie sofort aus Axiom (I 2) folgt. Allgemeiner gilt dieses, sobald I eineEinheit a enthalt. Denn dann gilt wieder nach (I 2) auch 1R = a1 a I.Insbesondere sind in einem Korper K die einzigen Ideale {0} und K selbst. Dieseswiederum hat folgende Konsequenz:

Satz 3.1.12 Jeder Ringhomomorphismus : K R, wobei K ein Korper ist,ist injektiv oder identisch Null.

Als nachstes halten wir einige einfache Konstruktionsprinzipien fur Ideale fest,die vollig analog dem Fall der Teilraume von Vektorraumen sind. Das folgendeubertragt sich ubrigens sofort auf Untergruppen von additiv geschriebenen abel-schen Gruppen, allgemeiner auf

Moduln uber Ringen, wie sie im zweiten Teil

der Vorlesung betrachtet werden.


Bemerkung und Definition 3.1.13 Es sei R ein Ring, I und J Ideale in R.

a) I J ist ein Ideal in R. Allgemeiner ist der Durchschnitt einer beliebigenMenge von Idealen wieder ein Ideal.

b) I + J ist ein Ideal in R.

c) Sei R kommutativ, und seien a1, . . . , ak R. Dann ist

Ra1 +Ra2 + . . .+Rak =

k

i=1

riai | r1, . . . rk R

ein Ideal in R, das von a1, . . . , ak erzeugte Ideal.

Die unter c) betrachtete Menge ist offenbar ein Analogon des Spanns (der linearenHulle) endlicher vieler Elemente eines Vektorraums. Der Begriff

erzeugt wird

unter c) im ublichen Sinn benutzt: es handelt sich um das kleinste Ideal, das dieMenge {a1, . . . , ak} enthalt. Dass ein solches existiert, kann man auch an Teil a)sehen: im Prinzip kann man den Schnitt aller Ideale betrachten, die die gegebeneMenge enthalten; allerdings liefert das keine konstruktive Beschreibung.

Das Summenideal unter b) ist das kleinste Ideal, das I und J enthalt; es kannalso als das Erzeugnis von I J aufgefasst werden.

Die Hauptideale sind genau die von einem Element erzeugten Ideale; sie ent-sprechen also den zyklischen Untergruppen. Die in c) betrachteten Ideale heienendlich erzeugt. Spater, wenn wir mehr Beispiele von Ringen genauer kennen,werden wir Ideale sehen, die als Erzeugnis von zwei Elementen gegeben sind,aber nicht von einem Element erzeugt werden konnen, d.h. keine Hauptidealesind. (Man kann den Polynomring Z[X] nehmen.)

Beispiele 3.1.14 (Schnitt und Summe von Idealen)

(1) Der Durchschnitt Za Zb zweier Hauptideale in Z besteht aus den Zah-len, die sowohl Vielfache von a als auch von b sind, d.h. den gemeinsamenVielfachen von a und b. Dass diese Menge wieder ein Hauptideal ist bedeu-tet, dass es einen sinnvollen Begriff des

kleinsten gemeinsamen Vielfachen

gibt, und zwar in allen Hauptidealringen. Fur Z hatten wir dieses bereitsoben im Kontext zyklischer Gruppen als Hilfssatz 2.1.14 festgehalten.

(2) Wir wissen aus Satz 2.1.11, dass von zwei Elementen a und b erzeugte Idea-le (=Untergruppen) in Z zur Definition des groten gemeinsamen Teilersbenutzt werden konnen:

Za+ Zb = Zg, wobei g = ggT(a, b).

(Erinnerung: Dieses folgt leicht aus den Lemma von Bezout.)


Als nachstes betrachten wir Ideale mit zusatzlichen Eigenschaften.

Definition 3.1.15 Es sei R ein kommutativer Ring und I ein Ideal in R.

a) I heit Primideal, falls I = R ist und gilt:

a, b R, a b I = a I oder b I .

b) I heit maximal, falls I = R ist und gilt:

J Ideal in R, J I = J = I oder J = R .

Der Begriff der Maximalitat unter b) ist der ubliche, auch in anderen Zusam-menhangen nutzliche: ein Ideal ist maximal, wenn es als Teilmenge von R maxi-mal bezuglich der Inklusions-Relation ist unter allen echten Teilmengen von R,die Ideale sind. D.h. jede echte Obermenge gehort nicht mehr zu der betrachtetenKlasse von Mengen. Die Primideale bzw. maximalen Ideale kann man an ihrenFaktorringen erkennen, wie der folgende Satz zeigt.

Satz 3.1.16 Es sei I ein Ideal in einem kommutativen Ring R.

a) I ist Primideal R/I ist Integritatsbereich.

b) I ist maximal R/I ist ein Korper.

Beweis: siehe Vorlesung.

Da jeder Korper ein Integritatsbereich ist, haben die beiden Aquivalenzen desSatzes die folgende Konsequenz:

Korollar 3.1.17 Jedes maximale Ideal ist ein Primideal.

Im Ring Z sind von {0} verschiedene Primideale und maximale Ideale das gleiche;es sind die Hauptideale Zp, wobei p eine Primzahl ist. Das folgt aus Satz 1.5.14zusammen mit Satz 3.1.16.

Wir notieren noch eine letzte algebraische Standardkonstruktion auch fur Ringe;sie baut, wenn man so will, auf 1.3.13 fur Gruppen auf.

Definition und Bemerkung 3.1.18 (Direktes Produkt von Ringen)

a) Wenn R und S zwei Ringe sind, dann ist RS mit komponentenweiser Ad-dition und Multiplikation ebenfalls ein Ring, das sogenannte direkte Produktvon R und S.

b) R S ist kommutativ genau dann, wenn R und S es sind.

c) Wenn R und S beide ein Einselement besitzen, dann gilt dieses auch furR S. In diesem Fall gilt fur die Einheitengruppen (R S) = R S.


d) Die Faktoren R {0} und {0} S sind Ideale in R S.

e) Die beiden Projektionen prR: R S R, (x, y) x, pr

S: R S

S, (x, y) y sind Ringhomomorphismen mit Kern {0} S bzw. R {0}.

Wir wollen R{0} und {0}S nicht ausdrucklich als Teilringe auffassen, denn siebesitzen (ggf. ) ein anderes Einselement als RS, und die Inklusionen {0}S RS und R {0} RS sind keine Ringhomomorphismen, die Eins auf Einsabbilden.

Nachdem die allgemeine Theorie nun ein Stuck weit entwickelt ist, kehren wirzum Ring der ganzen Zahlen und seinen Restklassen zuruck. Der folgende Satz,der sogenannte Chinesische Restsatz, ist einer der Eckpfeiler der ElementarenZahlentheorie.

Satz 3.1.19 (Chinesischer Restsatz fur Z) Es seienm1,m2, . . . ,mr paarwei-se teilerfremde naturliche Zahlen, d.h. ggT(mi,mj) = 1 fur i = j, und m :=m1m2 . . .mr. Dann ist die Abbildung

Z/mZ Z/m1Z Z/m2Z . . . Z/mrZ[x]m ([x]m1 , [x]m2 , . . . , [x]mr)

ein Isomorphismus von Ringen.

Als Satz uber zyklische Gruppen ist uns dieser Satz aus 2.2.16 bereits bekannt;wir mussen nur bemerken, dass der dort konstruierte Isomorphismus wegen 3.1.9sogar ein Ringisomorphismus ist. Auerdem haben wir bei dieser Gelegenheitdie Verallgemeinerung auf mehr als zwei Faktoren notiert, die man leicht durchInduktion uber r beweist. Siehe auch den unten folgenden Zusatz 3.1.21. Wenn man vom Chinesischen Restsatz alle algebraische Terminologie abstreift,handelt er davon, dass mehrere gleichzeitig betrachtete Kongruenzen fur teiler-fremde

Moduln immer eine gemeinsame Losung x haben. In der alteren Litera-

tur wird er deshalb auch als Hauptsatz uber simultane Kongruenzen bezeichnet.Der Satz sieht dann wie folgt aus:

Satz 3.1.20 (Hauptsatz uber simultane Kongruenzen)Es seien m1,m2, . . . ,mr paarweise teilerfremde naturliche Zahlen und m ihr Pro-dukt. Dann existiert zu je r vorgegebenen ganzen Zahlen x1, . . . , xr eine ganze Zahlx mit

x xi (mod mi) fur alle i = 1, . . . , r .Wenn x eine weitere solche Zahl ist, dann gilt x x (mod m).Als algorithmische Aufgabe stellt sich nun die Frage, wie man zu gegebenem xii = 1, . . . , r ein x Z mit x xi (mod mi) fur i = 1, . . . , r explizit berechnet.Mit anderen Worten, man mochte einen Algorithmus fur die Umkehrabbildungder Abbildung aus dem Beweis des chinesichen Restsatzes angeben. Dieses gehtwie folgt:


Zusatz 3.1.21 In der Situation von 3.1.19 setze man Mi =j =i

mj und bestimme

fur i = 1, . . . , r jeweils ai mit aiMi 1 (mod mi). Dann ist das gesuchte x beigegebenen xi gleich

x =r

i=1

aiMixi .

Man beachte, dass mi und Mi jeweils teilerfremd sind; deswegen existiert dasgewunschte ai (man erinnere sich an 1.5.8). Der Rest des Beweises ergibt sichnunmehr durch direkte Uberprufung der gewunschten Kongruenzen.

Vom algorithmischen Standpunkt aus reduziert sich der Chinesische Restsatzsomit auf die Inversenberechnung in Ringen Z/mZ, also auf das Lemma vonBezout, und damit letztlich auf den erweiterten euklidischen Algorithmus.

Wir wollen nun den Chinesischen Restsatz auf die Bestimmung der Ordnung derGruppe (Z/mZ) anwenden. Die entsprechende Zahlfunktion ist eine bekanntezahlentheoretische Funktion und hat einen eigenen Namen.

Definition 3.1.22 Die Eulersche -Funktion : N N ist definiert durch

(n) = |(Z/nZ)| = {k N | 0 < k < n, ggT(k, n) = 1}.

Mit anderen Worten, (n) ist die Ordnung der primen Restklassengruppe modulon.

Satz 3.1.23 a) Die Eulersche -Funktion ist multiplikativ , d.h. es gilt

(mn) = (m)(n) fur alle m,n N mit ggT(m,n) = 1.

b) Fur eine Primzahlpotenz pl gilt (pl) = pl pl1 = pl1(p 1).Beweis: zu a): Der Isomorphismus Z/mnZ = Z/mZ Z/nZ induziert wiejeder Ringisomorphismus offenbar einen Isomorphismus der Einheitengruppen:(Z/mnZ) = (Z/mZZ/nZ). Nach Bemerkung 3.1.18 c) ist die zweite Gruppeisomorph zu (Z/mZ) (Z/nZ). Betrachtung der Machtigkeiten liefert unmit-telbar die Behauptung.

zu b): dieses ist elementar: die zu pl teilerfremden Zahlen zwischen 0 und pl

sind genau die nicht durch p teilbaren unter diesen Zahlen. Nun ist aber genaujede p-te Zahl, also 0, p, 2p, . . . durch p teilbar, von den pl Zahlen von 0 bis pl 1sind also genau pl1 durch p teilbar. Man beachte, dass sich aus a) und b) eine explizite Formel fur (n) ergibt (aller-dings nur, wenn man die Primfaktorzerlegung kennt, diese Einschrankung ist furdas RSA-Verfahren der Public-Key-Kryptographie von groer Bedeutung). Furjede multiplikative Funktion f : N C gilt offenbar

f(n) =r

i=1

f(pkii), wobei n =

r

i=1

pkii

mit verschiedenen Primzahlen pi.

Documents

3.1 Homomorphismen, Ideale und Faktorringealgebra/Algebra_2012/Skript/algeb… · Algebra I c Rudolf Scharlau, 2002 – 2012 123 3.1 Homomorphismen, Ideale und Faktorringe Aus dem