Primzahlen sind natürliche Zahlen, die genau zwei Teiler haben, nämlich 1 und sich selbst.

Daher zählt die 1 nicht zu den Primzahlen.

Es gibt unendlich viele Primzahlen. Ein System, welche Zahlen Primzahlen sind, wurde bisher noch nicht gefunden.

Man verwendet Primzahlen häufig in der Kryptographie beim Verschlüsseln von Daten.

Die Primzahlen von 1 bis 100

Folgende Zahlen zwischen 1 und 100 sind prim:

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.

       

Fakten über Primzahlen

  • Die 2 ist die einzige gerade Primzahl.

  • Jede natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen schreiben.     (Primfaktorzerlegung)

  • 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.    

   

Primfaktorzerlegung    

Artikel zum Thema

Als Primfaktorzerlegung bezeichnet man die Darstellung einer Zahl als Produkt von Primzahlen. Dazu verwendet man, dass sich jede natürliche Zahl eindeutig als Produkt von Primzahlen darstellen lässt.

                                                 

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.

Unendlichkeitsbeweis nach Euklid (hier ausklappen)

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 %%p%%) 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:
    %%7%% ist die größte Primzahl. Liste an Primzahlen: %%2,3,5,7%%
    %%p = 2 \cdot 3 \cdot5 \cdot7 + 1 = 211%% und %%211%% ist eine Primzahl.
    %%7%% ist also nicht die größte Primzahl.

  • andere Annahme:
    %%13%% ist die größte Primzahl. Liste an Primzahlen: %%2,3,5,7, 11, 13%%
    %%p = 2 \cdot 3 \cdot5 \cdot7 \cdot 11 \cdot 13 + 1 = 30031%%.
    %%30031 = 59 \cdot 509%% und sowohl %%59%% als auch %%509%% sind Primzahlen, die nicht in unserer Liste und größer als %%13%% sind.
    %%13%% ist also nicht die größte Primzahl.


Unsere Zahl %%p%% ist auf jeden Fall größer als alle Zahlen unserer Liste.

Da %%p -1%% ein Produkt aus unserer Liste aus Primzahlen ist, hat %%p%% beim Teilen durch jede dieser Primzahlen den Rest %%1%% und kann daher keine der Primzahlen aus der Liste als Teiler haben.

Daher kann %%p%% 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.

 

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.
Antwort abschicken