Zahlentheorie — Primzahlen, Teilbarkeit & Modulare Arithmetik

Die Zahlentheorie ist die Lehre von den ganzen Zahlen. Wenn du Primzahlen, Teilbarkeit oder modulare Arithmetik verstehen willst, beschäftigst du dich bereits mit dem Kern der Zahlentheorie.

Eine Primzahl ist eine ganze Zahl größer als $1$ mit genau zwei positiven Teilern: $1$ und sich selbst. Bei der Teilbarkeit geht es darum, ob eine ganze Zahl ohne Rest in eine andere hineingeht. Die modulare Arithmetik verfolgt Reste, weshalb man sie oft auch Uhrarithmetik nennt.

Was die Zahlentheorie umfasst

Diese drei Ideen gehören zusammen:

• Primzahlen sind die grundlegenden Bausteine der positiven ganzen Zahlen.
• Teilbarkeit sagt dir, wann eine ganze Zahl genau in eine andere hineinpasst.
• Modulare Arithmetik formuliert Teilbarkeitsfragen als Restklassenfragen um.

Zum Beispiel ist die Aussage „$a$ ist durch $n$ teilbar“ dasselbe wie

$$a \equiv 0 \pmod n$$

Eine Teilbarkeitsfrage lässt sich also oft als Frage nach dem Rest umschreiben.

Primzahlen: Die Bausteine

Die Primzahlen beginnen mit

$$2, 3, 5, 7, 11, 13, \dots$$

Die Zahl $2$ ist die einzige gerade Primzahl. Jede andere gerade Zahl ist durch $2$ teilbar und kann daher nicht prim sein.

Wenn eine positive ganze Zahl größer als $1$ nicht prim ist, nennt man sie zusammengesetzt. Zum Beispiel ist $21$ zusammengesetzt, denn

$$21 = 3 \cdot 7$$

Primzahlen sind wichtig, weil sich jede ganze Zahl größer als $1$ bis auf die Reihenfolge der Faktoren als Produkt von Primzahlen schreiben lässt. Das ist die Grundidee der Primfaktorzerlegung.

Teilbarkeit: Wenn eine Zahl genau in eine andere passt

Sind $a$ und $b$ ganze Zahlen mit $b \ne 0$, dann bedeutet „$b$ teilt $a$“, dass es eine ganze Zahl $k$ gibt mit

$$a = bk$$

Das schreibt man als

$$b \mid a$$

Zum Beispiel gilt $4 \mid 20$, weil $20 = 4 \cdot 5$. Aber $4 \nmid 22$, weil bei der Division von $22$ durch $4$ ein Rest bleibt.

Teilbarkeit ist die Sprache hinter Faktoren, Vielfachen, größten gemeinsamen Teilern und kleinsten gemeinsamen Vielfachen. Sie erklärt auch bekannte Tests:

• Eine Zahl ist durch $2$ teilbar, wenn ihre letzte Ziffer gerade ist.
• Eine Zahl ist durch $5$ teilbar, wenn ihre letzte Ziffer $0$ oder $5$ ist.
• Eine Zahl ist durch $3$ teilbar, wenn ihre Quersumme durch $3$ teilbar ist.

Die letzte Regel ist kein Trick. Sie folgt aus der modularen Arithmetik.

Modulare Arithmetik: Rechnen mit Resten

Wenn zwei ganze Zahlen bei Division durch $n$ denselben Rest lassen, heißen sie kongruent modulo $n$. Man schreibt

$$a \equiv b \pmod n$$

Das bedeutet, dass $n$ die Zahl $a-b$ teilt.

Zum Beispiel gilt

$$17 \equiv 5 \pmod{12}$$

weil $17$ und $5$ bei Division durch $12$ beide den Rest $5$ lassen und außerdem $12$ die Zahl $17 - 5 = 12$ teilt.

Das ist nützlich, weil du eine Zahl durch eine einfachere kongruente Zahl ersetzen kannst. Auf einer $12$-Stunden-Uhr hat das Addieren von $15$ Stunden denselben Effekt wie das Addieren von $3$ Stunden, denn

$$15 \equiv 3 \pmod{12}$$

Durchgerechnetes Beispiel: Warum ist $231$ durch $3$ teilbar?

Betrachte die Zahl $231$.

Schreibe sie zuerst in Stellenwertform:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

Nun rechnen wir modulo $3$. Da

$$10 \equiv 1 \pmod 3$$

folgt

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

Also gilt

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

Weil $231 \equiv 0 \pmod 3$, ist die Zahl durch $3$ teilbar.

Das erklärt die Quersummenregel: Im Zehnersystem ist jede Potenz von $10$ kongruent zu $1$ modulo $3$, also hat die ganze Zahl denselben Rest wie die Summe ihrer Ziffern.

Und nach dem Dividieren erhält man

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

also ist $231$ zusammengesetzt und nicht prim.

Häufige Fehler in der Zahlentheorie

$1$ als Primzahl behandeln

$1$ ist keine Primzahl. Eine Primzahl muss genau zwei positive Teiler haben, und $1$ hat nur einen.

Die Bedingung bei der Teilbarkeit vergessen

Die Aussage $b \mid a$ ergibt nur Sinn, wenn $b \ne 0$. Eine Division durch null ist nicht erlaubt.

Gleichheit und Kongruenz verwechseln

$17 \equiv 5 \pmod{12}$ bedeutet nicht $17 = 5$. Es bedeutet, dass sich die beiden Zahlen um ein Vielfaches von $12$ unterscheiden.

Teilbarkeitsregeln überstrapazieren

Manche Tests sind schnell, weil das Rechnen im Zehnersystem sie besonders einfach macht. Das bedeutet nicht, dass jeder Teiler eine einfache Ziffernregel hat.

Wo Zahlentheorie vorkommt

Auf Schulniveau begegnet dir die Zahlentheorie bei Faktorisierung, Restaufgaben, Teilbarkeitsbeweisen und Uhr-Aufgaben. Sie taucht auch auf, wenn du Brüche kürzt, gemeinsame Teiler suchst oder Probleme mit periodischen Mustern löst.

Auf tieferem Niveau sind Primzahlen und modulare Arithmetik auch zentral für Kryptografie und Informatik. Du brauchst diesen Hintergrund nicht, um die Ideen anzuwenden, aber er erklärt, warum die Zahlentheorie in Anwendungen immer wieder auftaucht.

Probiere deine eigene Version

Versuche dieselbe Argumentation mit $462$. Nutze zuerst die Quersumme, um die Teilbarkeit durch $3$ zu prüfen, und faktorisiere die Zahl dann so weit, dass du entscheiden kannst, ob sie prim oder zusammengesetzt ist.

Wenn du deine Methode überprüfen willst, löse eine ähnliche Teilbarkeits- oder Restaufgabe in einem Mathe-Löser und vergleiche die Schritte der modularen Arithmetik mit deinen eigenen.