Zahlentheorie für Olympiaden: Grundlagen und Aufgaben

18. February 2026

Wer sich auf mathematische Olympiaden vorbereitet, kommt an der Zahlentheorie nicht vorbei. Sie ist eines der klassischsten und gleichzeitig faszinierendsten Gebiete der Olympiadenmatematik – voller eleganter Beweise, überraschender Zusammenhänge und Aufgaben, die mit einfachen Mitteln formuliert sind, aber tiefes Denken verlangen. Dieser Artikel führt durch die wichtigsten Grundlagen: Teilbarkeit, Primzahlen und modulare Arithmetik – jeweils mit konkreten Aufgabenbeispielen.

Was ist Zahlentheorie?

Die Zahlentheorie ist der Teilbereich der Mathematik, der sich mit den Eigenschaften ganzer Zahlen beschäftigt. Sie fragt: Welche Zahlen sind prim? Wann ist eine Zahl durch eine andere teilbar? Welche Muster entstehen beim Rechnen mit Resten?

Was die Zahlentheorie für Olympiaden besonders attraktiv macht: Die Aufgaben erfordern selten komplizierte Formeln, dafür umso mehr Kreativität, kombinatorisches Denken und die Fähigkeit, Strukturen zu erkennen. Viele legendäre Aufgaben der Internationalen Mathematik-Olympiade (IMO) stammen aus diesem Bereich.

Teilbarkeit: Das Fundament

Grundbegriffe

Eine ganze Zahl $a$ ist teilbar durch $b$ (geschrieben: $b \mid a$), wenn es eine ganze Zahl $k$ gibt mit $a = b \cdot k$. Man sagt auch: $b$ ist ein Teiler von $a$.

Wichtige Rechenregeln:

Wenn $b \mid a$ und $b \mid c$, dann gilt $b \mid (a + c)$ und $b \mid (a - c)$.
Wenn $b \mid a$, dann gilt $b \mid (a \cdot m)$ für jedes ganze $m$.
Transitivität: Wenn $c \mid b$ und $b \mid a$, dann gilt $c \mid a$.

Der größte gemeinsame Teiler (ggT)

Der ggT zweier Zahlen $a$ und $b$ ist die größte Zahl, die beide teilt. Der Euklidische Algorithmus berechnet ihn effizient:

$$\text{ggT}(a, b) = \text{ggT}(b, a \mod b)$$

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

$252 = 1 \cdot 180 + 72$
$180 = 2 \cdot 72 + 36$
$72 = 2 \cdot 36 + 0$

Also: $\text{ggT}(252, 180) = 36$.

Übungsaufgabe Teilbarkeit

Beweise: Wenn $n$ eine natürliche Zahl ist, dann ist $n^3 - n$ stets durch 6 teilbar.

Lösung: Man schreibt $n^3 - n = n(n^2 - 1) = (n-1)\cdot n \cdot (n+1)$. Das ist das Produkt von drei aufeinanderfolgenden natürlichen Zahlen. Unter je drei aufeinanderfolgenden Zahlen ist mindestens eine durch 2 und mindestens eine durch 3 teilbar. Also ist das Produkt stets durch $2 \cdot 3 = 6$ teilbar. $\square$

Primzahlen: Bausteine der Arithmetik

Definition und der Fundamentalsatz

Eine natürliche Zahl $p > 1$ heißt Primzahl, wenn ihre einzigen Teiler 1 und $p$ selbst sind. Der Fundamentalsatz der Arithmetik besagt: Jede natürliche Zahl größer als 1 lässt sich eindeutig als Produkt von Primzahlen schreiben (bis auf die Reihenfolge).

Die ersten Primzahlen: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots$

Es gibt unendlich viele – das bewies bereits Euklid mit einem brillant einfachen Widerspruchsbeweis.

Sieb des Eratosthenes

Wer alle Primzahlen bis zu einer Grenze $N$ sucht, nutzt das Sieb des Eratosthenes:

Schreibe alle Zahlen von 2 bis $N$ auf.
Beginne mit $p = 2$: Streiche alle echten Vielfachen von $p$.
Gehe zur nächsten nicht gestrichenen Zahl – das ist die nächste Primzahl.
Wiederhole bis $p > \sqrt{N}$.

Alle verbleibenden Zahlen sind Primzahlen. Das Verfahren ist besonders nützlich in der Informatik-Olympiade, wo es als Algorithmus implementiert wird.

Übungsaufgabe Primzahlen

Für welche natürlichen Zahlen $n$ ist $n^2 - 1$ eine Primzahl?

Lösung: $n^2 - 1 = (n-1)(n+1)$. Damit das Produkt prim ist, muss einer der Faktoren gleich 1 sein. Da $n-1 < n+1$, muss $n - 1 = 1$, also $n = 2$ gelten. Dann ist $n^2 - 1 = 3$ – tatsächlich prim. Für alle $n > 2$ ist $(n-1) \geq 2$ und $(n+1) \geq 4$, also ist das Produkt zusammengesetzt. Antwort: nur $n = 2$.

Modulare Arithmetik: Rechnen mit Resten

Kongruenz

Zwei ganze Zahlen $a$ und $b$ heißen kongruent modulo $m$ (geschrieben $a \equiv b \pmod{m}$), wenn $m \mid (a - b)$, d.h. wenn $a$ und $b$ bei Division durch $m$ denselben Rest lassen.

Ausführlich erklärt findet sich dieses Konzept auf der Wikipedia-Seite zur Kongruenz in der Zahlentheorie.

Beispiel: $17 \equiv 5 \pmod{6}$, denn $17 - 5 = 12 = 2 \cdot 6$.

Rechenregeln

Kongruenzen verhalten sich wie Gleichungen – man darf addieren, subtrahieren und multiplizieren:

$a \equiv b$ und $c \equiv d \Rightarrow a + c \equiv b + d \pmod{m}$
$a \equiv b$ und $c \equiv d \Rightarrow a \cdot c \equiv b \cdot d \pmod{m}$

Division ist nur unter besonderen Bedingungen erlaubt (wenn der Divisor teilerfremd zu $m$ ist).

Kleiner Satz von Fermat

Für eine Primzahl $p$ und eine zu $p$ teilerfremde ganze Zahl $a$ gilt:

$$a^{p-1} \equiv 1 \pmod{p}$$

Das ist ein mächtiges Werkzeug, um große Potenzen modulo einer Primzahl zu berechnen.

Beispiel: Was ist der Rest von $7^{100}$ bei Division durch 13?

Da 13 prim und $\text{ggT}(7, 13) = 1$: $7^{12} \equiv 1 \pmod{13}$.
Nun ist $100 = 8 \cdot 12 + 4$, also $7^{100} = (7^{12})^8 \cdot 7^4 \equiv 1^8 \cdot 7^4 \pmod{13}$.
$7^2 = 49 \equiv 10 \pmod{13}$, $7^4 \equiv 100 \equiv 9 \pmod{13}$.
Ergebnis: Rest 9.

Übungsaufgabe Modulare Arithmetik

Zeige, dass $4^{2n} - 1$ für alle natürlichen Zahlen $n$ durch 15 teilbar ist.

Lösung: Es gilt $4^2 = 16 \equiv 1 \pmod{15}$. Damit ist $(4^2)^n = 4^{2n} \equiv 1^n = 1 \pmod{15}$, also $4^{2n} - 1 \equiv 0 \pmod{15}$. $\square$

Strategien für Olympiade-Aufgaben

Bei zahlentheoretischen Olympiadeaufgaben helfen einige bewährte Herangehensweisen:

Spezialfälle prüfen: Kleine Werte für $n$ einsetzen und Muster erkennen.
Teilbarkeitsargumente: Produkte aufeinanderfolgender Zahlen, Paritätsüberlegungen.
Modulo-Reduktion: Komplizierte Ausdrücke modulo einer geschickt gewählten Zahl betrachten.
Primfaktorzerlegung: Den Fundamentalsatz der Arithmetik gezielt einsetzen.
Widerspruchsbeweis: Annehmen, dass etwas gilt, und zum Widerspruch führen.

Die Mathematik-Olympiade in Deutschland, an der jährlich rund 200.000 Schülerinnen und Schüler teilnehmen, stellt regelmäßig Aufgaben aus dem zahlentheoretischen Bereich. Ein Blick in das Aufgabenarchiv auf olympiade-mathematik.de lohnt sich – dort finden sich über 6.000 Aufgaben mit Lösungen aus echten Wettbewerben.

Übersicht: Was du beherrschen solltest

Thema	Kernwerkzeug
Teilbarkeit	ggT, Euklidischer Algorithmus
Primzahlen	Fundamentalsatz, Sieb des Eratosthenes
Modulare Arithmetik	Kongruenzrechenregeln, Kleiner Satz von Fermat
Diophantische Gleichungen	Erweiterter Euklidischer Algorithmus

Zahlentheorie ist eines jener Gebiete, wo regelmäßiges Üben den Unterschied macht. Wer die Grundlagen fest im Griff hat und viele Aufgaben durchgearbeitet hat, entwickelt mit der Zeit ein Gespür dafür, welcher Ansatz bei einer unbekannten Olympiadeaufgabe zuerst versucht werden sollte.