Angewandte Diskrete Mathematik

  • Titel: Angewandte Diskrete Mathematik
  • Organisation: UNI ULM
  • Seitenzahl: 34

Skript herunterladen (PDF)

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