Glossar

Select one of the keywords on the left…

Teilbarkeit und PrimzahlenPrimzahlen

Alle Schritte anzeigen

Bei der Berechnung der Teilerpaare einer Zahl kann es vorkommen, dass die Zahl außer dem ersten Paar keine anderen Teiler mehr hat. Ein Beispiel dafür ist 13 - seine einzigen Teiler sind 1 und 13 selbst. Diese besonderen Zahlen werden als Primzahlen bezeichnet. Sie können nicht in Produkte mit kleineren Zahlen zerlegt werden, was sie gewissermaßen zu “Atomen von Zahlen” macht.

Beachte, dass 1 selbst keine Primzahl ist, so dass die ersten Primzahlen 2, 3, 5, 7, 11, 13,.... sind.

Jede Zahl, die keine Primzahl ist, kann als Produkt von Primzahlen geschrieben werden: Wir teilen sie einfach in mehrere Teile, bis alle Faktoren prim sind. Zum Beispiel,

84
2
×
42
2
×
21
3
×
7
84
=
2
×
2
×
3
×
7

Jetzt sind 2, 3 und 7 Primzahlen und können nicht weiter unterteilt werden. Das Produkt 2 × 2 × 2 × 3 × 3 × 7 wird als die Primfaktorzerlegung von 84 bezeichnet, und 2, 3 und 7 sind seine Primfaktoren. Beachte, dass einige Primzahlen, wie in diesem Fall 2, in einer Primfaktorzerlegung mehrfach auftreten können.

Jede ganze Zahl hat eine Primfaktorzerlegung und keine zwei ganzen Zahlen haben die gleiche Primfaktorzerlegung. Außerdem gibt es nur eine einzige Möglichkeit, eine beliebige Zahl als Produkt von Primzahlen zu schreiben - es sei denn, wir zählen unterschiedliche Anordnungen der Primzahlen. Das wird als der Fundamentalsatz der Arithmetik (FdA) bezeichnet.

Die Anwendung des FdA kann viele Probleme in der Mathematik viel einfacher machen: Wir teilen Zahlen in ihre Primfaktoren auf, dann lösen wir das Problem für die einzelnen Primzahlen, was oft viel einfacher sein kann, kombinieren zum Schluss diese Ergebnisse und lösen so das anfängliche Problem.

Das Sieb des Eratosthenes

Es stellte sich heraus, dass es ziemlich schwierig war, festzustellen, ob eine Zahl eine Primzahl ist: Man musste immer alle ihre Primfaktoren finden, was mit zunehmender Größe der Zahlen immer schwieriger wird. Stattdessen entwickelte der griechische Mathematiker Eratosthenes von Kyrene einen einfachen Algorithmus, um alle Primzahlen bis 100 zu finden: das Sieb des Eratosthenes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Zuerst müssen wir alle Zahlen bis 100 aufschreiben.
Wir wissen, dass 1 nicht prim ist, also löschen wir die 1.
Die kleinste Primzahl ist 2. Jedes Vielfache von 2 kann also keine Primzahl sein, da es 2 als Faktor hat. Daher können wir alle Vielfachen von 2 streichen.
Die nächste Zahl in unserer Liste ist 3 - also wieder eine Primzahl. Alle Vielfache von 3 können nicht Primzahlen sein, da sie 3 als Teiler haben. Deshalb können wir diese auch streichen.
Die nächste Zahl, 4, ist bereits gestrichen, also gehen wir weiter zu 5: das ist eine Primzahl und wir streichen wieder alle Vielfache von 5.
Die nächste Primzahl muss sein, da 6 durchgestrichen ist. Und wieder streichen wir alle entsprechenden Vielfachen durch.
Die nächste Primzahl ist . Beachte jedoch, dass alle seine Vielfache bereits gestrichen sindVielfache von 3 sind. Das Gleiche gilt eigentlich für alle anderen verbleibenden Zahlen. Daher müssen alle diese verbleibenden Zahlen Primzahlen sein.

Durch Abzählen sehen wir, dass es insgesamt Primzahlen gibt, die kleiner als 100 sind.

Wie viele Primzahlen gibt es?

Natürlich können wir auch das Sieb des Eratosthenes verwenden, um größere Primzahlen zu finden. Es gibt 21 Primzahlen zwischen 100 und 200, 16 Primzahlen zwischen 200 und 300, 17 Primzahlen zwischen 400 und 500 und nur 11 zwischen 10.000 und 10.100.

Die Primzahlen scheinen in immer größeren Abständen aufzutreten, aber hören sie jemals auf? Gibt es eine größte oder eine letzte Primzahl?

Der altgriechische Mathematiker Euklid von Alexandria bewies als erster, dass es unendlich viele Primzahlen gibt, mit dem folgenden Argument:

  1. Angenommen, es gäbe nur endlich viele Primzahlen.
    P, P, P, P, P
  2. Wir wollen nun alle miteinander multiplizieren, um eine sehr große Zahl zu erhalten, die wir N nennen.
    N = P × P × P × P × P
  3. Sehen wir uns jetzt N + 1 genauer an. Jede Primzahl, die N teilt, kann nicht auch N + 1 teilen. Und da alle Primzahlen, die wir bisher gefunden haben, N teilen, kann keine davon auch N + 1 teilen.
    P, P, P, P,
    P
    N
    P, P, P, P,
    P
    N + 1
  4. Der Fundamentalsatz der Arithmetik besagt, dass N + 1, wie jede andere Zahl in Primfaktoren zerlegt werden kann. Entweder N + 1 ist selbst prim, oder es gibt eine zusätzliche neue Primzahl P’ die Teiler von N + 1 ist.
    P’ N + 1
  5. In beiden Fällen hätten wir also eine neue Primzahl gefunden, die nicht in unserer ursprünglichen Liste enthalten ist - aber wir hatten ja angenommen, dass alle Primzahlen in dieser Liste sind.
  6. Offensichtlich ist da etwas schiefgelaufen! Aber da die Schritte 2-4 alle korrekt waren, ist die einzige mögliche Erklärung die, dass unsere anfängliche Annahme 1 falsch war. Das bedeutet, dass es tatsächlich unendlich viele Primzahlen geben muss.

Euklids Erklärung ist eines der ersten Beispiele in der Geschichte für einen formalen mathematischen Beweis - ein logisches Argument, das zeigt, dass eine Aussage definitiv wahr sein muss. Dieses Beispiel wird oft als Widerspruchsbeweis bezeichnet: Wir beginnen mit einer Annahme, leiten daraus etwas Unmögliches ab und wissen daher, dass unsere Annahme falsch gewesen sein muss.