Inhaltsverzeichnis:

  Der Restklassenring Ζ n  

I.   1

II.  Die Einheitengruppe  4

  Die Einheiten von Ζ n  

III.   7

  Die Eulersche ϕ-Funktion  

IV.   9

IV.1  Eigenschaften der Eulerschen ϕ-Funktion  

   9

IV.2  Berechnung der Eulerschen ϕ-Funktion  

  12  

IV.3  Die Struktur der Einheitengruppe E(Ζ n )  17

V.  Zusammenfassung  22

2

I. Der Restklassenring Z n

Definition I.1:

Ein Ring-mit-1 besteht aus einer Menge R von Elementen zusammen mit zwei Verknüpfungen + und *, die je zwei Elementen x, y aus R wieder ein Element x + y bzw. x * y von R zuordnen. Damit eine solche Struktur Ring genannt wird, müssen die folgenden drei Gruppen von Gesetzen für alle Elemente x, y, z ` R erfüllt sein:

1. Gesetze der Addition

• Assoziativität: (x + y) + z = x + (y + z)

• Existenz und Eindeutigkeit des neutralen Elementes: Es gibt genau ein Element 0 von R, für das gilt: 0 + x = x

• Existenz und Eindeutigkeit inverser Elemente: Zu jedem Element x aus R gibt es genau ein Element -x aus R, für das gilt: x + (-x) = 0

• Kommutativität:

2. Gesetze der Multiplikation

• Assoziativität: x * (y * z) = (x * y) * z

• Existenz und Eindeutigkeit des neutralen Elementes: Es gibt genau ein Element 1 von R, für das gilt: 1 * x = x = x * 1

3. Distributivgesetze x * (y + z) = x * y + x * z (x + y) * z = x * z + y * z

Die Menge Ζ der ganzen Zahlen ist zusammen mit der gewöhnlichen Addition und Multiplikation ein kommutativer Ring-mit-1.

Ausgehend von den ganzen Zahlen kann man nun zu einer natürlichen Zahl n die Restklassen in Ζ bilden.

Dazu sei x ` Ζ, dann ist

x = {x + m * n  m ` Ζ}

die zugehörige Restklasse modulo n.

Die Menge aller Restklassen {x  x ` Ζ} bezeichnet man mit Ζ n .

Auf dieser Menge ist nun eine Addition und Multiplikation erklärt durch: ⊕: Ζ n % Ζ n → Ζ n

x ⊕ y := z, falls x + y ` z, wenn x ` x und y ` y für x, y ` Ζ. •: Ζ n % Ζ n → Ζ n

x • y := z, falls x * y ` z, wenn x ` x und y ` y für x, y ` Ζ.

3

Beweis:

Es seien x und y Elemente aus Ζ n . Außerdem seien x, x‘ ` x und y, y‘ ` y und Repräsentanten aus den jeweiligen Restklassen.

Da x, x‘ ` x bzw. y, y‘ ` y sind, existiert ein m ` Ζ bzw. ein k ` Ζ mit x‘ = x + m * n, bzw. y‘ = y + k * n.

a) Es sei x‘ + y‘ = z’. Dann ist x‘ ⊕ y‘ = z’.

Es folgt somit: x ⊕ y = x + y = (x‘ + m * n) + (y‘ + k * n) = x‘ + y‘ + n * (m + k) = x‘ + y‘ (da n * (m + k) = 0 nach Definition) = x‘ ⊕ y‘ = z’.

Damit ist die Addition in Ζ n wohldefiniert.

b) Es sei x‘ * y‘ = z’. Dann ist x‘ • y‘ = z’. Es folgt somit: x • y = x * y = (x‘ + m * n) * (y‘ + k * n)

= x‘ • y‘ = z’.

Damit ist auch die Multiplikation in Ζ n wohldefiniert.

•

Beweis:

Es seien x, y und z Elemente aus Ζ n .

a) Assoziativgesetz der Addition:

Da das Assoziativgesetz der Addition in Ζ gilt, folgt im Restklassenring Ζ n : x ⊕ (y ⊕ z) = x + (y + z) = (x + y) + z = (x ⊕ y) ⊕ z.

b) Kommutativgesetz der Addition:

Da das Kommutativgesetz der Addition in Ζ gilt, folgt im Restklassenring Ζ n : x ⊕ y = x + y = y + x = y ⊕ x

c) Neutrales Element der Addition:

Da x + 0 = x für alle x ` Ζ ist, so ist auch x ⊕ 0 = x + 0 = x. Also ist 0 das neutrale Element der Addition in Ζ n . (*) Beweis der Eindeutigkeit:

Es sei 0 = e das nach (*) existierende neutrale Element der Addition. Es sei nun e’ ein Element, für das ebenfalls e’ ⊕ x = x für alle x ∈ Ζ n gilt. Dann ist insbesondere: e’ ⊕ e = e. Aus (*) folgt nun aber auch: e ⊕ e’ = e’. Aus b) folgt dann: e = e’ ⊕ e = e ⊕ e’ = e’, also e = e’. Damit ist die Eindeutigkeit des neutralen Elementes der Addition bewiesen.

4

d) Inverse Elemente der Addition:

Da zu jedem x ` Ζ ein Element (-x) ` Ζ existiert mit x + (-x) = 0, so ist auch x ⊕ (-x) = x + (-x) = 0. Also ist (-x) das inverse Element zu x ` Ζ n . (**) Beweis der Eindeutigkeit:

Es sei (-x) das nach (**) existierende inverse Element der Addition zu x ∈ Ζ n . Es sei nun (-x)’ ein Element, für das ebenfalls x ⊕ (-x)’ = 0 gilt. Mit a), b), c) und (**) folgt:

(-x)’ = (-x)’ ⊕ 0 = (-x)’ ⊕ (x ⊕ (-x)) = ((-x)’ ⊕ x) ⊕ (-x) = 0 ⊕ (-x) = (-x). Damit ist die Eindeutigkeit inverser Elemente der Addition bewiesen.

e) Assoziativgesetz der Multiplikation:

Da das Assoziativgesetz der Multiplikation in Ζ gilt, folgt im Restklassenring Ζ n : x • (y • z) = x * (y * z) = (x * y) * z = (x • y) • z

f) Kommutativgesetz der Multiplikation:

Da das Kommutativgesetz der Multiplikation in Ζ gilt, folgt im Restklassenring Ζ n : x • y = x * y = y * x = y • x

g) Neutrales Element der Multiplikation: Da 1 * x = x für alle x ` Ζ, so ist auch 1 • x = 1 * x = x. Also ist 1 das neutrale Element der Multiplikation in Ζ n . (***) Beweis der Eindeutigkeit:

Es sei 1 das nach (***) existierende neutrale Element der Multiplikation. Es sei nun 1’ ein Element, für das ebenfalls 1’ • x = x gilt für alle x ∈ Ζ. 1’ = 1’ • 1 = 1 • 1’ = 1. Mit f) und (***) folgt:

Damit ist die Eindeutigkeit des neutralen Elementes der Multiplikation gezeigt.

•

Um diesen Satz zu beweisen, benötige ich im voraus noch eine Definition, die aus der Vorlesung „Algebra I“ bekannt ist.

5

Beweis zu Satz I.5:

Es sei p eine Primzahl, und es sei a eine natürliche Zahl mit 1 [ a < p. Es ist zu zeigen, daß es eine natürliche Zahl a‘ < p gibt mit a • a‘ = 1. Dazu betrachte ich die Produkte 0 • a, 1 • a, 2 • a, ..., (p - 1) • a. (*)

Behauptung: Diese Elemente sind paarweise verschieden. Angenommen, es wäre h • a = k • a mit h ! k. Das bedeutet, daß h * a und k * a den gleichen Rest bei Division durch p haben. Also ist h * a - k * a = (h - k) * a durch p teilbar. Da p das Produkt (h - k) * a teilt, folgt, daß p einen der Faktoren teilt. Da jedoch a < p laut Voraussetzung ist, teilt p die Zahl h - k. Ferner gilt aber auch, daß diese Zahl zwischen - (p - 1) und + (p - 1) liegt, denn es gilt h [ p - 1 und k [ p - 1.

Die einzige Zahl in diesem Intervall, die durch p teilbar ist, ist aber die Zahl 0. Daher ist h - k = 0, also h = k. Dies ist aber ein Widerspruch zur Annahme. Also sind die Elemente von (*), die von 0 (= 0 • a) verschieden sind, verschiedene Elemente von Ζ p \ {0}. Da dies aber p - 1 Elemente sind und da Ζ p \ {0} nur p - 1 Elemente hat, sind das alle Elemente von Ζ p \ {0}.

Daraus folgt, daß jedes Element von Ζ p \ {0} eine Darstellung der Form (*) hat. Insbesondere hat die Zahl 1 eine solche Darstellung. Daher gibt es eine Zahl h ` {1, ..., p - 1} mit 1 = h • a.

Dann ist aber dieses Element h ` Ζ p \ {0} invers zu a.

•

II. Die Einheitengruppe

Um nun auf die Einheitengruppe eines Ringes zu sprechen zu kommen, stelle ich vorweg die benötigten Definitionen zusammen.

Definition II.1:

Eine Gruppe besteht aus einer Menge G zusammen mit einer Verknüpfung Û, die je zwei Elementen aus G wieder ein Element aus G zuordnet, so daß folgende Axiome erfüllt sind:

(G1) Assoziativgesetz Die Verknüpfung Û ist assoziativ: (g Û h) Û k = g Û (h Û k) für alle g, h, k ` G.

(G2) Existenz eines linksneutralen Elementes: Es gibt ein Element e aus G, für das gilt: e Û g = g für alle g ` G.

(G3) Existenz linksinverser Elemente: Für jedes g ` G gibt es ein Element g -1 aus G, für das gilt: g -1 Û g = e,

wobei e das in b) geforderte neutrale Element ist.

In diesem Fall ist g -1 ein zu g linksinverses Element. Es läßt sich jedoch zeigen, daß g -1 auch rechtsinvers ist, indem man die Eindeutigkeit des neutralen Elements und der inversen Elemente nachweist, wie es im Beweis von Satz II.2. noch folgen wird.

6

Wenn zusätzlich das folgende Axiom (G4) gilt, nennt man die Gruppe G kommutativ oder abelsch:

(G4) Für je zwei Elemente g, h ` G gilt: g Û h = h Û g.

Beweis:

Es sei e das nach (G2) existierende linksneutrale Element.

1. Behauptung: Es gilt g Û g -1 = e, d. h., jedes zu g linksinverse Element ist auch zu g rechtsinvers. Dazu sei h = g -1 . Dann ist:

g Û g -1 = e Û (g Û g -1 ) = (h -1 Û h) Û (g Û g -1 ) = h -1 Û ((h Û g) Û g -1 ) = h -1 Û ((g -1 Û g) Û h) = h -1 Û (e Û h) = h -1 Û h = e.

2. Behauptung: Es gilt g Û e = g für alle g ` G, d. h., e ist auch rechtsneutral. Es ist:

g Û e = g Û (g -1 Û g) = (g Û g -1 ) Û g = e Û g = g.

3. Behauptung: Es gibt nur ein neutrales Element in G.

Es sei e‘ ein Element, für das ebenfalls e‘ Û g = g für alle g ` G gilt. Dann ist insbesondere e‘ Û e = e. Aus 2. folgt e‘ Û e = e‘. Also ist e‘ = e‘ Û e = e.

4. Behauptung: Für jedes g ` G gibt es nur ein zu g inverses Element. Es sei h ein weiteres zu g inverses Element. Dann gilt h Û g = e. Mit 2. und 1. folgt also

h = h Û e = h Û (g Û g -1 ) = (h Û g) Û g -1 = e Û g -1 = g -1 .

•