- Titel: Angewandte Diskrete Mathematik
- Organisation: UNI ULM
- Seitenzahl: 34
Inhalt
- Skript zur Vorlesung
- Angewandte Diskrete Mathematik
- Prof Dr Helmut Maier DiplMath Hans Peter Reck
- Institut fur Zahlentheorie und Wahrscheinlichkeitstheorie Universitt Ulm a
- Polynomkongruenzen und Potenzreste Polynomkongruenzen Potenzreste
- Teilbarkeit ganzer Zahlen
- Eindeutigkeit der Primfaktorzerlegung
- Berechnung von ggT und kgV anhand der Primfaktorzerlegung
- Der Euklidische Algorithmus
- rn qn rn rn
- Das multiplikative Inverse
- Das Rechnen mit Kongruenzen
- mod mod mod mod mod
- Denition Unter der Quersumme einer Zahl n
- ak k mit Ziern ak versteht man
- Unter der alternierenden Quersumme versteht man AQn
- Beweis Wir nehmen n
- ak k ak m und am an
- a Wegen k b Wegen k
- mod Damit ist n
- mod durch Konm
- Restsysteme teilerfremde Restklassen Eulersche Funktion
- Der Chinesische Restsatz
- mod m mod m mod mr mod mr
- erhalten werden wobei Mj ist
- mod mod mod
- Wir erhalten die Lsung o
- Berechnung der Eulerschen Funktion Multiplikativitt a
- Die Stze von Euler und Fermat a
- Algebraische Grundstrukturen in der Zahlentheorie
- Beispiele in der Zahlentheorie
- Untergruppen zyklische Gruppen Ordnung und Primitivwurzel
- ar ar mod m
- Polynomkongruenzen und Potenzreste
- Werte von j welche
- Anwendungen in der Kryptologie Primzahltests
- Public Key Codes RSA Verfahren
- Zahlen a mit
- so ist n eine Primzahl
Vorschau
Skript zur Vorlesung
Angewandte Diskrete Mathematik
Wintersemester 2009/10
Prof. Dr. Helmut Maier Dipl.-Math. Hans- Peter Reck
Institut fur ahlentheorie und Wahrscheinlichkeitstheorie ¨ Universit¨t Ulm a
Inhaltsverzeichnis
1 Teilbarkeit 1.1 1.2 1.3 1.4 Teilbarkeit ganzer ahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eindeutigkeit der Primfaktorzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . Berechnung von ggT und kgV anhand der Primfaktorzerlegung . . . . . . . . . . . . . Der Euklidische Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 4 4 7 7 9 9 10 11 12 13 15 16 18 18 19 20 24 24 26 28 28 30
2 Kongruenzen 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Das multiplikative Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Das Rechnen mit Kongruenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Elementare Teilbarkeitsregeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Restsysteme, teilerfremde Restklassen, Eulersche ϕ- Funktion . . . . . . . . . . . . . . Lineare Kongruenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Der Chinesische Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Berechnung der Eulerschen ϕ- Funktion, Multiplikativit¨t . . . . . . . . . . . . . . . . a Die S¨tze von Euler und Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a
3 Algebraische Grundstrukturen in der ahlentheorie 3.1 3.2 3.3 Algebraische Grundstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Beispiele in der ahlentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Untergruppen, zyklische Gruppen, Ordnung und Primitivwurzel . . . . . . . . . . . . .
4 Polynomkongruenzen und Potenzreste 4.1 4.2 Polynomkongruenzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Potenzreste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Anwendungen in der Kryptologie, Primzahltests 5.1 5.2 Public- Key- Codes, RSA- Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . Primzahltests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Kapitel 1
Teilbarkeit
1.1 Teilbarkeit ganzer ahlen
Definition 1.1.1. Eine ganze ahl b heißt durch eine ganze ahl a = 0 teilbar, falls es ein x ∈ gibt, so daß b = ax ist, und wir schreiben a|b. Man nennt a einen Teiler von b, und b heißt Vielfaches von a. Falls b nicht durch a teilbar ist, schreiben wir a |b. Satz 1.1.2. (a) a|b ⇒ a|bc f¨r alle c ∈ u (b) a|b und b|c ⇒ a|c (c) a|b und a|c ⇒ a|(bx + cy) f¨r alle x, y ∈ u (d) a|b und b|a ⇒ a = ±b (e) a|b und a, b > 0 ⇒ a ≤ b (f) Ist m = 0, dann gilt: a|b ⇔ ma|mb.
1.2
Eindeutigkeit der Primfaktorzerlegung
Definition 1.2.1. Eine nat¨rliche ahl p ∈ N heißt Primzahl, wenn p nur die positiven Teiler 1 und u p besitzt. Beispiel 1.2.2. Es ist n = 91 keine Primzahl, da 91 = 7 · 13 gilt. Daf¨r ist p = 17 eine Primzahl. u Definition 1.2.3. Unter der (kanonischen) Primfaktorzerlegung einer nat¨rlichen ahl n > 1 versteht u γ1 γr man eine Darstellung der Gestalt n = p1 · . . . · pr mit p1 < . . . < pr und γi ∈ N f¨r i = 1, . . . , r. u Beispiel 1.2.4. Die ahl n = 9000 besitzt die kanonische Primfaktorzerlegung 9000 = 23 · 32 · 53 . Satz 1.2.5. (Fundamentalsatz der Arithmetik) Die kanonische Primfaktorzerlegung einer nat¨rlichen ahl n > 1 existiert stets und ist eindeutig. u 3