Grundlagen der Elementaren Zahlentheorie

Dieses Cheat Sheet fasst die Kernkonzepte der elementaren Zahlentheorie zusammen, einschließlich Teilbarkeit, Primzahlen, modulare Arithmetik und kryptographische Anwendungen wie RSA.

Core Principles

• Teilbarkeit: a|b bedeutet, dass a ein Teiler von b ist.
• Division mit Rest: Für a ∈ Z und m ∈ N, m > 1, existieren eindeutige q, r mit a = qm + r.
• Größter gemeinsamer Teiler (ggT): Die größte natürliche Zahl, die zwei Zahlen teilt.
• Diophantische Gleichungen: Lineare Gleichungen mit ganzzahligen Koeffizienten und Lösungen.
• Primzahlen: Natürliche Zahlen > 1, die nur durch 1 und sich selbst teilbar sind.
• Euklidischer Algorithmus: Effizientes Verfahren zur Bestimmung des ggT.
• Modulare Arithmetik: Rechnen mit Resten.
• Chinesischer Restsatz: Löst Systeme simultaner Kongruenzen.
• RSA-Algorithmus: Asymmetrisches Verschlüsselungsverfahren basierend auf Primfaktorzerlegung.

Action Steps

• 1. Bestimme den ggT(a, b) mit dem Euklidischen Algorithmus.
• 2. Prüfe, ob c ein Vielfaches des ggT(a, b) ist (für diophantische Gleichungen).
• 3. Nutze den erweiterten Euklidischen Algorithmus, um eine spezielle Lösung zu finden.
• 4. Füge die Lösungen der homogenen Gleichung hinzu, um alle Lösungen zu erhalten.
• 5. Zerlege das Modul in teilerfremde Faktoren für den Chinesischen Restsatz.
• 6. Berechne die Inversen der Gegenzahlen modulo der Teilmodule.
• 7. Multipliziere Reste, Inverse und Gegenzahlen und addiere sie, um das Endergebnis zu erhalten.

Formulas

• $a = qm + r$
• $ggT(a, b) = ggT(b, r)$
• $a \equiv b \pmod{m}$
• $a \cdot x + b \cdot y = c$
• $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_s^{\alpha_s}$
• $\phi(m) = m \prod_{p|m} \left(1 - \frac{1}{p}\right)$
• $a^{\phi(m)} \equiv 1 \pmod{m}$
• $c = n^r \pmod{m}$
• $n = c^s \pmod{m}$

Key Terms

• Teilbarkeit: a|b, wenn ein k ∈ Z existiert mit a·k = b.
• ggT: Größter gemeinsamer Teiler zweier Zahlen.
• Diophantische Gleichung: Lineare Gleichung ax + by = c mit ganzzahligen Lösungen x, y.
• Primzahl: Natürliche Zahl > 1, nur teilbar durch 1 und sich selbst.
• Kongruenz: a ≡ b (mod m), wenn a und b bei Division durch m den gleichen Rest haben.
• Euler'sche Phi-Funktion φ(m): Anzahl der zu m teilerfremden Zahlen k ∈ {1, ..., m}.
• RSA-Algorithmus: Asymmetrisches Verschlüsselungsverfahren basierend auf der Schwierigkeit der Primfaktorzerlegung großer Zahlen.

Real World Examples

• Zeitangaben: Rechnen mit Resten (Stunden modulo 24, Sekunden modulo 60).
• Kryptographie: RSA-Algorithmus zur sicheren Datenübertragung mittels modularer Arithmetik und Primzahlen.
• Zahlentheorie-Beweise: Euklidischer Algorithmus zur Bestimmung des ggT und zur Lösung diophantischer Gleichungen.

Timeline

• ca. 300 v. Chr.: Euklid von Alexandria veröffentlicht 'Die Elemente', die den Euklidischen Algorithmus systematisch darlegen.
• Unbekannt (ca. 100 v. Chr. - 300 n. Chr.): Diophant von Alexandria beschäftigt sich mit zahlentheoretischen Gleichungen (Diophantische Gleichungen).
• 1700er: Leonhard Euler entwickelt die Euler'sche Phi-Funktion und den Satz von Euler.
• 1700er: Carl Friedrich Gauß formuliert den Chinesischen Restsatz und entwickelt die modulare Arithmetik.
• 1970er: Entwicklung des RSA-Algorithmus durch Rivest, Shamir und Adleman, basierend auf zahlentheoretischen Prinzipien.

People

• Euklid von Alexandria: Mathematiker, bekannt für den Euklidischen Algorithmus und 'Die Elemente'.
• Diophant von Alexandria: Mathematiker, nach dem diophantische Gleichungen benannt sind.
• Leonhard Euler: Einflussreicher Mathematiker, entwickelte die Euler'sche Phi-Funktion und den Satz von Euler.
• Carl Friedrich Gauß: Mathematiker, prägte die modulare Arithmetik und formulierte den Chinesischen Restsatz.
• Rivest, Shamir, Adleman: Entwickler des RSA-Verschlüsselungsalgorithmus.