Primzahlen sind natürliche Zahlen pp größer oder gleich 22, die nur durch sich selbst und 11 teilbar sind. Es sind also genau diejenigen natürlichen Zahlen, die genau zwei Teiler besitzen.
So ist 55 eine Primzahl, weil sie größer gleich 22 ist und neben sich selbst und 11 keine weiteren Teiler besitzt. 66 ist keine Primzahl, weil sie nicht nur 11 und 66 sondern auch 22 und 33 als Teiler besitzen.
Primzahlen werden in der Verschlüsselung von Nachrichten und von Daten eingesetzt.

Bedeutung für die Primzahlzerlegung

Nicht-Primzahlen größer als 22 können in ein Produkt von kleineren Faktoren zerlegt werden. Nehme die Zahl 4848. Sie ist keine Primzahl, weil sie neben 11 und 4848 auch den Teiler 22 besitzt. Damit können wir schreiben:
48=224\displaystyle \color{Green} 48=2 \cdot 24
Die Zahl 22 ist eine Primzahl und kann damit nicht in ein Produkt mit Faktoren kleiner als 22 zerlegt werden. Demgegenüber ist 2424 keine Primzahl und kann weiter zerlegt werden (So ist 44 ein Teiler von 2424). Es kann also 2424 weiter zerlegt werden:
48=224=246\displaystyle 48 = 2 \cdot {\color{Green}24} = 2 \cdot {\color{Green}4 \cdot 6}
Solange wir Nicht-Primzahlen im Produkt haben, können wir es weiter zerlegen, bis wir nur noch Primzahlen im Produkt haben:
48=224=246=2226=22223\displaystyle 48 = 2 \cdot 24 = 2 \cdot {\color{Green}4} \cdot 6 = 2 \cdot {\color{Green}2\cdot 2} \cdot {\color{Orange}6} = 2 \cdot 2\cdot 2 \cdot {\color{Orange}2 \cdot 3}
Wenn man eine natürliche Zahl größer gleich 22 immer weiter in Produkte zerlegt, so erhält man irgendwann ein Produkt, die nur Primzahlen enthält. Die besondere Eigenschaft der Primzahlen, dass sie nicht in Produkte mit kleineren Faktoren zerlegt werden kann, sorgt dafür, dass am Ende ein Produkt mit nur Primzahlen entsteht. Diese Zerlegung einer Zahl in ein Produkt aus nur Primzahlen wird Primfaktorzerlegung genannt.

Warum ist 1 keine Primzahl?

Die Multiplikation einer Zahl mit 11 verändert diese Zahl nicht. Wenn ich 11 als Primzahl zulassen würde, so könnte ich eine Zahl immer weiter dadurch „zerlegen“, dass ich 1 als Faktor anhänge. Nehmen wir die Zahl 1212. Wäre 11 eine Primzahl, so könnte ich folgende unendliche Primzahlzerlegung machen:
12=112=1112=11112=\displaystyle 12 = 1 \cdot 12 = 1\cdot 1 \cdot 12 = 1 \cdot 1 \cdot 1 \cdot 12 = \ldots
Damit wir irgendwann fertig sind mit der Primzahlenzerlegung, erlauben wir nicht, dass 11 eine Primzahl ist. Dadurch wird unsere Primzahlzerlegung auch eindeutig. Sprich: Nach jeder Primzahlenzerlegung kommen wir immer auf dasselbe Ergebnis (wenn wir die Reihenfolge der Faktoren nicht beachten).

Die Primzahlen von 1 bis 100

Folgende Zahlen zwischen 11 und 100100 sind Primzahlen:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89 und 97\displaystyle \begin{array}{l} 2,\, 3,\, 5,\, 7,\, 11,\, 13,\, 17,\\ 19,\, 23,\, 29,\, 31,\, 37,\, 41,\, 43,\\ 47,\, 53,\, 59,\, 61,\, 67,\, 71,\, 73,\\ 79,\, 83,\, 89\text{ und }97 \end{array}

Fakten über Primzahlen

  • Die 2 ist die einzige gerade Primzahl.
  • Wenn das Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar ist, dann muss bereits eine der natürlichen Zahlen durch die Primzahl teilbar gewesen sein.

Verfahren zur Überprüfung, ob eine Zahl Primzahl ist

Wenn man eine Zahl gegeben hat und überprüfen soll, ob die gegebene Zahl eine Primzahl ist, ist die einfachste Methode zu versuchen sie der Reihe nach durch alle Primzahlen zu teilen.
Man testet also ob die Zahl durch 2 teilbar ist, dann durch 3, durch 5…
Wenn man bis zur Wurzel der gegebenen Zahl alle Primzahlen als Teiler ausgeschlossen hat, dann ist die Zahl  selbst eine Primzahl. Andernfalls nicht.
Natürlich verwendet man aber heute mit Computern auch andere Verfahren.

Unendlichkeit der Primzahlen

Die Anzahl der Primzahlen ist unendlich. Man kann also keine größte Primzahl finden. Es wird immer eine Primzahl geben die größer ist. Den Beweis für diese These hat Euklid schon vor mehr als 2000 Jahren geliefert.

Widerspruchsbeweis

Die Argumentation beruht auf einem Widerspruchsbeweis. Man nimmt also an, es gäbe eine größte Primzahl und versucht durch Argumente auf einen Widerspruch zu kommen. Dann muss die Annahme falsch gewesen sein.
Angenommen, es gibt nur endlich viele Primzahlen, und wir können eine vollständige Liste der Primzahlen angeben.

Beispiel

Zum Beispiel nehmen wir an das wir nur die Primzahlen 2, 3, 5 und 7 haben und nicht mehr.
Nun nimmt man alle Primzahlen aus der Liste mal und addiert 1.Die so entstandene Zahl (nennen wie sie pp) ist nun entweder
  1. selbst eine Primzahl oder
  2. hat eine Primfaktorzerlegung aus Faktoren, die größer sind als die bisher angenommene größte Primzahl

Beispiel

  • Annahme: 77 ist die größte Primzahl.Liste an Primzahlen: 2,3,5,72,3,5,7 p=2357+1=211p = 2 \cdot 3 \cdot5 \cdot7 + 1 = 211 und 211211 ist eine Primzahl. 77 ist also nicht die größte Primzahl.
  • andere Annahme: 1313 ist die größte Primzahl.Liste an Primzahlen: 2,3,5,7,11,132,3,5,7, 11, 13 p=23571113+1=30031p = 2 \cdot 3 \cdot5 \cdot7 \cdot 11 \cdot 13 + 1 = 30031. 30031=5950930031 = 59 \cdot 509 und sowohl 5959 als auch 509509 sind Primzahlen, die nicht in unserer Liste und größer als 1313 sind. 1313 ist also nicht die größte Primzahl.
Unsere Zahl pp ist auf jeden Fall größer als alle Zahlen unserer Liste.
Da p1p -1 ein Produkt aus unserer Liste aus Primzahlen ist, hat pp beim Teilen durch jede dieser Primzahlen den Rest 11 und kann daher keine der Primzahlen aus der Liste als Teiler haben.
Daher kann pp nur Primteiler haben, die größer sind als die Primzahlen aus unserer Liste oder selbst eine Primzahl sein, welche größer ist als die angenommene größte Primzahl unserer Liste.
Die Annahme, es gebe nur endlich viele Primzahlen führt also zu einem Widerspruch.
        \;\;\Rightarrow\;\; Es gibt unendlich viele Primzahlen.

Übungsaufgaben

Kommentieren Kommentare

Zu article Primzahlen:
Daniela_Colantuono 2019-10-05 10:17:03+0200
Im Beispiel: sollte: 2x3x5x7+1 = 211 stehen (ist eine Primzahl)
Nish 2019-10-05 21:25:35+0200
Vielen Dank, Daniela_Colantuono! Du hast natürlich recht! Ich habe es eben verbessert. Sehr aufmerksam von dir :)

Falls dir wieder mal etwas auffällt oder du eine Frage hast, schreib uns gerne wieder einen Kommentar ,)

LG,
Nish
Antwort abschicken
Zu article Primzahlen:
IvanP 2019-07-27 21:58:08+0200
Das würde ich entfernen: „Ein System, welche Zahlen Primzahlen sind, wurde bisher noch nicht gefunden.“

Welche Zahlen Primzahlen sind, ist klar definiert, und es lässt sich auch jede Primzahl ermitteln (etwa mit dem Sieb des Eratosthenes), von dem her gibt es ja schon ein „System“. Siehe auch: http://recursed.blogspot.com/2013/01/no-formula-for-prime-numbers.html

Den Unendlichkeitsbeweis hat Euklid übrigens in etwas anderer Form geführt; er zeigte, dass zu einer vorgelegten endlichen Menge von Primzahlen eine weitere existiert – das steht natürlich im Widerspruch dazu, dass sie alle Primzahlen enthält, allerdings formulierte er das nicht als Annahme. Siehe: https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html

Auch interessant: https://web.archive.org/web/20190505034040/http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/
Renate 2019-07-29 21:18:13+0200
Hallo IvanP,

im ersten Augenblick habe ich dir völlig zugestimmt und konnte mir nicht einmal recht erklären, wie dieser Satz in den Artikel hineingekommen ist - zumal ja unten dann der Abschnitt "Verfahren zur Überprüfung, ob eine Zahl Primzahl ist" folgt! ;)


Aber inzwischen glaube ich, dass der Satz anders gemeint ist (und zugegebenermaßen ungeschickt bis unverständlich formuliert wurde).

Ich denke, dass der Autor / die Autorin ausdrücken wollte:
Die Primzahlen sind innerhalb der natürlichen Zahlen in ungleichmäßigen Abständen verteilt, und man hat bislang kein System gefunden, dem diese Verteilung folgt.

Man kann also, wenn man eine Primzahl gefunden hat, nicht ausrechnen, wann die nächste Primzahl kommt.

(Sicher ist allerdings, DASS irgendwann wieder eine Primzahl kommt, und zwar spätestens dann, wenn die im Beweis von Euklid angegebene Zahl erreicht ist.)


Wie stehst du zu diesen Überlegungen? Würde das so Sinn ergeben?

Viele Grüße
Renate

PS: Vielen Dank auch für die Angabe der Links, auf die du in deinem Kommentar verweist! Ich konnte mich (aus privaten Gründen) leider im Augenblick nur eher kurz und nicht (oder noch nicht) umfassend damit beschäftigen - und wollte dich auf der anderen Seite auch nicht noch länger auf eine Antwort warten lassen! :)
IvanP 2019-07-30 07:12:21+0200
Hallo Renate, du schreibst: „Man kann also, wenn man eine Primzahl gefunden hat, nicht ausrechnen, wann die nächste Primzahl kommt.“

Das Problem ist, dass unklar ist, was hier mit „ausrechnen“ gemeint ist, die Anwendung eines Primzahltests auf die natürlichen Zahlen ab 2 ist eben auch ein Ausrechnen, auch wenn das normalerweise nicht in Form einer Formel notiert wird. Und was als Formel notiert werden kann, ist eine Sache des Zeichenrepertoires, man könnte etwa schlicht „%%\mathrm p_n%%“ als Term für die %%n%%-te Primzahl verwenden. Du meinst, hier irgendeinen fundamentalen Unterschied zu erkennen, aber der müsste konkret benannt werden – und selbst das wäre in einer Einführung für Schüler vielleicht eher überflüssig –, so ist das zu schwammig oder ein Produkt der Einbildung.
ZenGorilla 2020-01-27 15:47:08+0100
Ich habe mal versucht, für das "System" eine passendere Formulierung zu finden. Wenn ich Zeit finde, könnte ich den zusätzlichen Unendlichkeitsbeweis noch einfügen, falls das gewünscht ist.
IvanP 2020-01-28 07:53:27+0100
Dasselbe in Grün Die Definition der Primzahlen bestimmt deren Anordnung, das ist dann die Regelmäßigkeit, was gibt es also konkret zu finden? Siehe aber den eingangs erwähnten Blogpost, da wird tatsächlich ein offenes Problem formuliert. http://recursed.blogspot.com/2013/01/no-formula-for-prime-numbers.html
IvanP 2020-01-28 07:54:12+0100
*Grün.
ZenGorilla 2020-01-28 13:34:36+0100
Die Definition der Primzahlen bestimmt deren Eigenschaften. Ich bin jetzt kein Mathe-Profi, aber eine kurze Google-Suche ergab, dass man zwar 2016 eine mögliche Regel für die Anordnung der Primzahlen auf dem Zahlenstrahl gefunden hat, diese aber noch nicht bewiesen ist. Das wie gesagt, ohne Gewähr, weil ich ein Laie bin und die Erkenntnis nur von Google stammt. Das die Primzahlen Regeln unterliegen und berechenbar sind, hat damit meiner Ansicht nach nichts zu tun.
IvanP 2020-01-29 00:34:01+0100
Es gibt mehrere offene Probleme, zum Beispiel: Liegt für jede positive ganze Zahl $n$ eine Primzahl zwischen $n^2$ und $(n+1)^2$? Die Äußerung, es sei keine „Regelmäßigkeit“ bekannt, ergibt für mich jedoch keinen rechten Sinn.
IvanP 2020-01-29 00:40:46+0100
(Jetzt aber:) Es gibt mehrere offene Probleme, zum Beispiel: Liegt für jede positive ganze Zahl %%n%% eine Primzahl zwischen %%n^2%% und %%(n+1)^2%%? Die Äußerung, es sei keine „Regelmäßigkeit“ bekannt, ergibt für mich jedoch keinen rechten Sinn.
ZenGorilla 2020-01-29 07:25:04+0100
Da das ja auch eine Seite für lernende ist, macht die Aufnahme von offenen Problemen keinen Sinn. Ich denke es geht darum, zu erklären, dass die Primzahlen auf den ersten Blick zufällig über den Zahlenstrahl verteilt scheinen. Aller Wahrscheinlichkeit nach ist das natürlich nicht so, aber eine endgültige Regel (z.B. die Möglichkeit, von einer Primzahl direkt auf die nächste zu schließen) wurde denke ich noch nicht bewiesen. Klar kann ich die folgenden Zahlen mittels Primzahlentests überprüfen. Aber das ist ja eher ausprobieren als berechnen.
IvanP 2020-01-29 11:08:46+0100
Man könnte mit einem Augenzwinkern so etwas aufnehmen wie das hier: It is evident that the primes are randomly distributed but, unfortunately, we don’t know what ‘random’ means.

Ich würde aber nicht schwammige Begrifflichkeiten verwenden (du grenzt hier zum Beispiel das „Ausprobieren“ vom Berechnen ab) und dabei so tun, als seien sie mathematisch klar definiert.
Antwort abschicken