Bloms Schema 


Mathematische Grundlagen

Natürliche Zahlen   Ganze Zahlen   - Restklassenring modulo   Übungen  

Im Folgenden werden einige für das Verständnis sinnvolle mathematische Definitionen und Sätze (teilweise mit Beweis) vorgestellt.

Natürliche Zahlen

Ganze Zahlen

Definition 17  (Teilbarkeit)
Seien .
Man sagt " teilt " (geschrieben: ), wenn es eine Zahl gibt, sodass gilt. In diesem Fall heißen und Teiler von .

Definition 18  (Division ganzer Zahlen)
Seien .
Dann ist und mit .

Definition 19  (Größter gemeinsamer Teiler)
Seien .
Eine Zahl nennt man den größten gemeinsamen Teiler von und , wenn und und keine Zahl mit und existiert. Man schreibt .

Bemerkung 20  (Eigenschaften des größten gemeinsamen Teilers)
Für gilt

(i)
(ii)
für
(iii)
für alle
(iv)
Es existieren mit

Definition 21  (Teilerfremd)
Seien .
Man sagt " ist teilerfremd (bzw. relativ prim) zu ", wenn gilt.

Definition 22  (Primzahlen)
Eine Zahl heißt Primzahl, wenn ihre einzigen positiven Teiler und sind.

Satz 23  (Primfaktorenzerlegung)
Jede Zahl lässt sich eindeutig (bis auf die Reihenfolge) als Produkt von Primzahlpotenzen darstellen:

wobei die paarweise verschiedene Primzahlen sind.

Definition 24  (Eulersche -Funktion)
Sei .
Dann bezeichnet die Anzahl der Zahlen in , die teilerfremd zu sind:

Satz 25  (Eigenschaften der Eulerschen -Funktion)

(i)
Für alle Primzahlen gilt .
(ii)
, falls ist.
(iii)
Wenn die Primfaktorenzerlegung von ist, dann gilt

PIC

Die Korrektheit des Euklidischen Algorithmus basiert auf den in Bemerkung 20 genannten Eigenschaften des größten gemeinsamen Teilers in leicht veränderter Form: .

PIC

- Restklassenring modulo

Definition 26  (Kongruenz)
Seien .
Man sagt " ist kongruent zu modulo " (geschrieben: ), wenn .

Definition 27  (Restklassenring modulo )
ist die Menge der natürlichen Zahlen. Addition, Subtraktion und Multiplikation in werden modulo durchgeführt.

Definition 28  (Multiplikatives Inverses)
Sei .
Das multiplikative Inverse von modulo ist die Zahl mit . Falls existiert, so ist es eindeutig und wird mit beschrieben; nennt man dann in invertierbar.

Definition 29  (Division in )
Seien .
In ist die Division von durch das Produkt von und und nur definiert, falls invertierbar in ist.

Satz 30  (Lösbarkeit von )
Sei .
Dann hat die Gleichung in genau dann eine Lösung , wenn gilt .

Beweis  
""

""
 

Aus Satz 30 folgt für :

Satz 31  (Invertierbarkeit)
Sei .
Die Zahl ist genau dann invertierbar, wenn gilt.

Satz 32  (Chinesischer Restsatz)
Seien paarweise teilerfremd und , .
Dann hat das System

eine eindeutige Lösung in mit .

Beweis Wir definieren mit . Da die paarweise teilerfremd sind, ist

und aus Satz 31 folgt, dass eindeutige Zahlen existieren mit
die sich mit dem erweiterten Euklidischen Algorithmus ermitteln lassen.
Außerdem ist für . Nun setzen wir
Für gilt unter der Voraussetzung deshalb:
Gäbe es ein weiteres Element mit obigen Eigenschaften, so folgt für und aufgrund der paarweisen Teilerfremdheit der auch , d.h. unser erfüllt alle Anforderungen und ist in eindeutig.

Definition 33  (Multiplikative Gruppe )
Die Menge der Zahlen aus , die zu teilerfremd sind, bezeichnet man als :

ist abgeschlossen bezüglich der Multiplikation in .

Definition 34  (Ordnung von )
Die Ordnung von ist die Anzahl der Elemente in dieser Menge und es gilt nach Definition 24:

Definition 35  (Ordnung von )
Sei .
Unter der Ordnung von einem Element versteht man die kleinste Zahl mit .

Definition 36  (Erzeugendes Element, zyklische Gruppe)
Sei .
Falls die Ordnung eines Elements gleich ist, so bezeichnet man als ein erzeugendes (bzw. primitives) Element. Enthält ein erzeugendes Element, dann nennt man die Gruppe zyklisch.

Satz 37  (Eigenschaften erzeugender Elemente)
Sei ein erzeugendes Element von .

(i)
existiert genau dann, wenn oder , wobei eine ungerade Primzahl und ist.
(ii)
(iii)
ist genau dann erzeugendes Element, wenn gilt .
Daraus folgt, dass, falls eine zyklische Gruppe ist, die Anzahl erzeugender Elemente gleich ist.
(iv)
ist genau dann erzeugendes Element, wenn für jeden Primfaktor von ist.

Definition 38  (Diskreter Logarithmus)
Sei ein erzeugendes Element von .
Dann gibt es zu jedem Element eine positive Zahl mit . Diese Zahl bezeichnet man als den diskreten Logarithmus von zur Basis in .

Satz 39  (Satz von Euler)
Für alle gilt:

Beweis Zuerst zeigen wir, dass aus folgt für . Dies gilt, denn

(i)
(folgt aus für ) und
(ii)
für , denn aus folgt sofort
und mit erhält man .

Mit erhalten wir dann

Da für , gilt auch und es folgt mit Satz 31 die Behauptung .

Satz 40  (Kleiner Satz von Fermat)
Für alle Primzahlen und gilt:

Beweis Für Primzahlen erhalten wir und . Die Behauptung folgt nun aus dem Satz von Euler.

Satz 41
Für und gilt:

Beweis .

Bemerkung 42
Der Satz 41 ermöglicht es in manchen Fällen, die Lösung des Problems für auf die Lösung des Problems zurückzuführen.

Satz 43
Für und ist

falls , wobei und verschiedene Primzahlen sind.

Beweis Falls , so folgt die Behauptung aus Satz 41 und im Falle gilt sie trivialerweise. Damit bleiben die Möglichkeiten entweder oder .
O.B.d.A. wollen wir den ersten Fall betrachten. Für ist offenbar für jedes , also . Mit für ein und Satz 25 ergibt sich folglich wegen mit dem Satz von Euler

und wie schon gezeigt
Also gilt und und, da und verschieden sind, also , ergibt sich somit die Behauptung .

Bemerkung 44

(i)
gilt auch für Zahlen der Form , falls alle Primzahlen paarweise teilerfremd sind.
(ii)
Satz 43 ist eine Variante von Satz 41 für Elemente aus .

Satz 45  (Eulersches Kriterium, quadratischer Rest)
Sei eine Primzahl und .
Die Kongruenz ist genau dann lösbar, wenn gilt

Falls die Kongruenz lösbar ist, so nennt man einen quadratischen Rest modulo p, andernfalls einen quadratischen Nichtrest modulo p.

Beweis  
"" Ist lösbar, und damit , dann gilt:

nach dem Satz von Fermat.
"" Wir nehmen an, dass gilt. Die multiplikative Gruppe besitzt ein erzeugendes Element und, da , gibt es eine natürliche Zahl mit . Damit folgt
Der Satz von Fermat und die Voraussetzung, sei erzeugendes Element, liefern, dass ein ganzzahliges Vielfaches von ist und damit gerade sein muss, etwa . Dies bedeutet aber und für erhalten wir die Behauptung .

Satz 46
Sei eine Primzahl.
In ist die Anzahl der quadratischen Reste gleich der Anzahl der quadratischen Nichtreste.

Beweis Die Behauptung folgt unmittelbar aus folgendem Lemma.

Lemma 47
Sei eine Primzahl.
Für ein erzeugendes Element ist genau dann quadratischer Rest, wenn gerade ist.

Beweis  
"" Ist gerade, dann ist natürlich eine Quadratwurzel von und somit quadratischer Rest modulo .
"" Sei nun ungerade, d.h. . Angenommen, es gibt ein mit . Da erzeugendes Element in ist, muss ein mit existieren. Also ist und nach Bemerkung 42 auch . Dies würde jedoch implizieren, aber da gerade und ungerade ist, erhalten wir mit der Annahme, sei ungerade, einen Widerspruch.

Übungen

Aufgabe 1
Bestimmen Sie alle Parameter, für welche die Gleichung genau Lösungen hat.

(Hinweis: Ist , so existieren ganze Zahlen mit , vgl. Bemerkung 20 (iv).)

 

Aufgabe 2
Seien mit und .

  1. Warum existiert in das multiplikative Inverse von ?
  2. Warum existiert in nicht das multiplikative Inverse von ?
  3. Warum gibt es immer eine natürliche Zahl mit ?

 

Aufgabe 3

  1. Begründen Sie, warum für teilerfremde natürliche Zahlen und für die Eulersche -Funktion gilt
  2. Zeigen Sie, dass für natürliche Zahlen mit Primfaktorzerlegung mit gilt:

 

Aufgabe 4
Lösen Sie die beiden folgenden Systeme simultaner Kongruenzen:

 

Aufgabe 5
Gegeben ist eine zyklische Gruppe mit .

Wie kann man schnell entscheiden, welche Ordnung ein gegebenes Element hat?

 

Aufgabe 6
Sei . Zeigen Sie, dass eine Primzahl ist, genau dann, wenn gilt

 

Aufgabe 7
Bestimmen Sie mit dem erweiterten Euklidischen Algorithmus die Inversen von

sofern diese existieren.

 

Aufgabe 8
Für genau welche Primzahlen ist die Kongruenz lösbar?

 

Aufgabe 9
Versuchen Sie in Analogie zum Eulerschen Kriterium ein hinreichendes und notwendiges Kriterium für die Lösbarkeit der Kongruenz für Primzahlen und zu bestimmen und zu verifizieren.

 

Aufgabe 10
Für sei die -te Primzahl. Begründen Sie, warum die (schlechte) obere Schranke für alle gilt.

 

Aufgabe 11
Wie prüft man bei einer gegebenen -stelligen Binärzahl algorithmisch in maximal Schritten, ob diese durch , oder ohne Rest teilbar ist?

 

Aufgabe 12
Man weiß, dass für für die Anzahl der Primzahlen kleiner gleich gilt

Zeigen Sie, dass für jede natürliche Zahl gilt:

Zwischen und liegt immer eine Primzahl.

 

Aufgabe 13
Sei ein Primteiler von und mit mit

für verschiedene Paare und mit .

Zeigen Sie, dass dann eine Potenz von ist.

Link zu den Lösungen