Primzahlen und ihre Eigenschaften                                                                Primzahlen sind natürliche Zahlen, die nur durch sich selbst und 1 teilbar sind. Die Eins zählt nicht als Primzahl, obwohl sie theoretisch der allgemeinen Definition entspricht. Expliziter greift die Definition durch die Ergänzung folgender Eigenschaften: Die natürliche Zahl muss größer Eins sein und genau zwei unterschiedliche Teiler besitzen um eine Primzahl zu sein. Somit ist 2 die kleinste Primzahl.


Der Beweis von Euklid zeigt, dass es unendlich viele Primzahlen gibt. Aus einer Primzahlmenge kann immer mindestens eine weitere Primzahl berechnet werden.
Jede Primzahl ist ungerade, mit Ausnahme der Zwei. Daher gilt für jede Primzahl die Darstellungsform 4n+1 und 4n-1, sowie 6n+1 und 6n-1 für jede Primzahl, die größer 3 ist.

Ergibt die Summe zweier natürlicher Zahlen eine Primzahl, so gelten die beiden Zahlen als teilerfremd. Sie besitzen nur die Eins als gemeinsamen Teiler. Im umgekehrten Fall trifft dies nicht immer zu. Addiert man zwei teilerfremde natürliche Zahlen, muss das Ergebnis nicht zwangsweise eine Primzahl ergeben.

Bestimmung der Primzahlen

Um die größte Primzahl zu ermitteln, werden zunächst die kleineren, durch 2, dann durch 3 teilbaren Zahlen "ausgesiebt".

Um die Primzahlkombination einer Zahl zu ermitteln, werden zunächst die kleineren, durch 2, dann durch 3 teilbaren gefundenen Primzahlen „ausgesiebt“.

Die Ermittlung von Primzahlen kann mit einem sehr alten Verfahren durchgeführt werden, dem Sieb des Eratosthenes. Man streicht nach der kleinsten Primzahl jede durch 2 teilbare Zahl und geht zur nächstgrößeren Zahl über, die stehen geblieben ist. Diese ist demnach die nächste Primzahl. Danach wird jede durch 3 teilbare Zahl gestrichen und die folgende Primzahl herausgesiebt. In weiteren Durchläufen werden alle Vielfachen der zuletzt gefundenen Primzahl gestrichen bis eine gewünschte Menge erreicht ist. Durch das Siebverfahren bleiben in einem vorgegebenen Zahlenbereich nur die Primzahlen stehen.

Primfaktorzerlegung – Fundamentalsatz der elementaren Zahlentheorie

Jede natürliche Zahl größer 1 ist entweder selbst eine Primzahl oder lässt sich durch Faktoren aus Primzahlen darstellen. Das Produkt lässt sich eindeutig bis auf die Reihenfolge der Faktoren bestimmen.
Das folgende Beispiel verdeutlicht die Primfaktorzerlegung von 2940:

2940 = 70 x 42
70 = 7 x 10 und 42 = 6 x 7
10 = 2 x 5 und 6 = 2 x 3
Daraus folgt 2940 = 7 x 2 x 5 x 2 x 3 x 7.

Die Primfaktorzerlegung dient sowohl zur Ermittlung des größten gemeinsamen Teilers, als auch des kleinsten gemeinsamen Vielfachen einer Zahlengruppe.