Zahlentheorie — Primzahlen und Teilbarkeit

Einführung

Die Zahlentheorie ist eine der ältesten Disziplinen der Mathematik — und zugleich eine der lebendigsten. Viele ihrer Fragen klingen simpel: Was sind Primzahlen? Wie viele gibt es? Doch die Antworten führen tief in die Struktur der ganzen Zahlen. Und seit dem 20. Jahrhundert steckt Zahlentheorie überall dort, wo Daten sicher übertragen werden: RSA-Verschlüsselung, die das HTTPS-Schloss in deinem Browser ermöglicht, basiert vollständig auf Primzahlen.

Grundidee

Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Die ersten Primzahlen sind $2, 3, 5, 7, 11, 13, 17, 19, \ldots$ Alle anderen ganzen Zahlen größer als 1 sind zusammengesetzte Zahlen — sie lassen sich als Produkt kleinerer Zahlen schreiben.

Das Erstaunliche: Jede ganze Zahl größer als 1 ist entweder selbst eine Primzahl oder lässt sich eindeutig als Produkt von Primzahlen schreiben. Das ist der Fundamentalsatz der Arithmetik.

Erklärung

Teilbarkeit

$a$ ist teilbar durch $b$ (geschrieben $b \mid a$), wenn es eine ganze Zahl $k$ gibt mit $a = b \cdot k$.

Beispiel: $6 \mid 42$, denn $42 = 6 \cdot 7$. Aber $7 \nmid 30$, denn $30 / 7$ ist keine ganze Zahl.

Wichtige Teilbarkeitsregeln:

Teilbar durch	Regel
2	letzte Ziffer gerade
3	Quersumme teilbar durch 3
4	letzte zwei Ziffern teilbar durch 4
5	letzte Ziffer 0 oder 5
9	Quersumme teilbar durch 9
10	letzte Ziffer 0

Beispiel: $738$: Quersumme $= 7+3+8 = 18$, also durch 3 und 9 teilbar.

Primzahlen und das Sieb des Eratosthenes

Um alle Primzahlen bis $n$ zu finden, nutzt man das Sieb des Eratosthenes:

1. Schreibe alle Zahlen von 2 bis $n$ auf.
2. Die kleinste nicht gestrichene Zahl ist eine Primzahl. Streiche alle ihre Vielfachen.
3. Wiederhole, bis $\sqrt{n}$ überschritten ist. Alle verbliebenen Zahlen sind prim.

Primzahlen bis 30: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$

Primfaktorzerlegung

Jede ganze Zahl $n > 1$ lässt sich eindeutig als Produkt von Primzahlen schreiben:

$180 = 2^2 \cdot 3^2 \cdot 5 \qquad 360 = 2^3 \cdot 3^2 \cdot 5$

Vorgehen: Teile wiederholt durch die kleinste Primzahl, die die Zahl teilt.

$252 \div 2 = 126 \div 2 = 63 \div 3 = 21 \div 3 = 7$ $\Rightarrow 252 = 2^2 \cdot 3^2 \cdot 7$

ggT und kgV

Der größte gemeinsame Teiler $\text{ggT}(a, b)$ ist die größte Zahl, die sowohl $a$ als auch $b$ teilt.

Das kleinste gemeinsame Vielfache $\text{kgV}(a, b)$ ist die kleinste positive Zahl, die sowohl von $a$ als auch von $b$ geteilt wird.

Mit Primfaktorzerlegung: $\text{ggT}(180, 360) = 2^2 \cdot 3^2 \cdot 5 = 180 \quad \text{(kleinste Exponenten)}$ $\text{kgV}(180, 360) = 2^3 \cdot 3^2 \cdot 5 = 360 \quad \text{(größte Exponenten)}$

Nützliche Formel: $\text{ggT}(a,b) \cdot \text{kgV}(a,b) = a \cdot b$

Euklidischer Algorithmus

Für große Zahlen ist die Primfaktorzerlegung aufwändig. Der euklidische Algorithmus berechnet den ggT schneller:

$\text{ggT}(a, b) = \text{ggT}(b,\ a \mod b) \quad \text{solange } b \neq 0$

Beispiel: $\text{ggT}(252, 105)$:

$252 = 2 \cdot 105 + 42$ $105 = 2 \cdot 42 + 21$ $42 = 2 \cdot 21 + 0$

Also $\text{ggT}(252, 105) = 21$.

Kongruenzrechnung (Modulo)

$a \equiv b \pmod{m}$ (lies: „$a$ ist kongruent zu $b$ modulo $m$”) bedeutet, dass $a$ und $b$ denselben Rest bei Division durch $m$ haben — oder gleichwertig: $m \mid (a - b)$.

$17 \equiv 2 \pmod{5} \quad \text{(beide lassen Rest 2 bei Division durch 5)}$ $-3 \equiv 4 \pmod{7} \quad \text{(denn } -3 - 4 = -7 = (-1) \cdot 7\text{)}$

Restklassen: Die Menge aller Zahlen mit demselben Rest bei Division durch $m$ heißt Restklasse. Modulo 5 gibt es fünf Restklassen: $[0], [1], [2], [3], [4]$.

Unendlichkeit der Primzahlen (Euklids Beweis)

Angenommen, es gäbe nur endlich viele Primzahlen $p_1, p_2, \ldots, p_n$. Bilde die Zahl $N = p_1 \cdot p_2 \cdots p_n + 1$. Diese Zahl ist durch keine der aufgelisteten Primzahlen teilbar (jede lässt Rest 1). Also ist $N$ entweder selbst prim oder hat einen Primfaktor außerhalb der Liste — Widerspruch! Also gibt es unendlich viele Primzahlen.

Beispiel aus dem Alltag

RSA-Verschlüsselung: Zwei sehr große Primzahlen $p$ und $q$ werden multipliziert: $n = p \cdot q$. Das Produkt $n$ ist öffentlich bekannt (es steht im Zertifikat der Website). Die Verschlüsselung nutzt $n$, die Entschlüsselung braucht die Faktoren $p$ und $q$ — und die zu finden, wenn $n$ aus hundert Stellen besteht, ist selbst für Computer praktisch unmöglich. Das Bankgeheimnis deiner Überweisung basiert auf dieser mathematischen Einbahnstraße.

Brüche kürzen: $\frac{252}{360}$ kürzen mit $\text{ggT}(252, 360) = 36$: $\frac{252}{360} = \frac{7}{10}$.

Anwendung

Aufgabe 1: Bestimme die Primfaktorzerlegung von $504$ und berechne $\text{ggT}(504, 180)$ sowie $\text{kgV}(504, 180)$.

Lösung: $504 = 2^3 \cdot 3^2 \cdot 7 \qquad 180 = 2^2 \cdot 3^2 \cdot 5$ $\text{ggT}(504, 180) = 2^2 \cdot 3^2 = 36$ $\text{kgV}(504, 180) = 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ Probe: $36 \cdot 2520 = 90720 = 504 \cdot 180$ ✓

Aufgabe 2: Was ist $2^{100} \pmod{7}$?

Lösung: Berechne den Zyklus von $2^n \pmod{7}$: $2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 1 \pmod{7}$ — Zyklus der Länge 3. Da $100 = 3 \cdot 33 + 1$, gilt $2^{100} \equiv 2^1 \equiv 2 \pmod{7}$.

Typische Fehler

„1 ist eine Primzahl” — Nein. Die Zahl 1 gilt per Definition nicht als Primzahl. Der Fundamentalsatz der Arithmetik würde sonst scheitern (man könnte 1er beliebig hinzufügen: $6 = 2 \cdot 3 = 2 \cdot 3 \cdot 1 = \ldots$).

ggT und kgV verwechseln: ggT nimmt die kleinsten Exponenten, kgV die größten. Merkhilfe: ggT ist kleiner (oder gleich) als beide Zahlen, kgV ist größer (oder gleich) als beide.

Modulo-Fehler bei negativen Zahlen: $-7 \pmod{3}$ ist nicht $-1$, sondern $2$ (in der üblichen mathematischen Konvention ist der Rest immer nicht-negativ): $-7 = (-3) \cdot 3 + 2$.

Zusammenfassung

Merke dir:

• Eine Primzahl ist größer als 1 und nur durch 1 und sich selbst teilbar — die 1 ist keine Primzahl
• Jede Zahl $>1$ hat eine eindeutige Primfaktorzerlegung (Fundamentalsatz der Arithmetik)
• $\text{ggT}$: kleinste Exponenten in Primfaktorzerlegung; $\text{kgV}$: größte Exponenten
• Euklidischer Algorithmus: $\text{ggT}(a, b) = \text{ggT}(b, a \bmod b)$ — schnell und elegant
• $a \equiv b \pmod{m}$: gleicher Rest bei Division durch $m$
• Es gibt unendlich viele Primzahlen (Euklids Beweis durch Widerspruch)

Quiz

Frage 1: Ist 91 eine Primzahl?

Frage 2: Berechne $\text{ggT}(84, 56)$ mit dem euklidischen Algorithmus.

Frage 3: Welchen Rest lässt $2026$ bei Division durch 9?

Frage 4: Warum können zwei verschiedene Primzahlen niemals den gleichen ggT mit einer dritten Zahl haben, der größer als 1 ist?