Die Einheitengruppe im Restklassering Z_n

Inhaltsverzeichnis:

  Seite  

  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

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

(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:

x + y = y + x

2. Gesetze der Multiplikation

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

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

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)

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)

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 ∈ Ζ. 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.

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

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 .

•