Eine ganz besondere Teilmenge der natürlichen Zahlen stellen die Primzahlen dar. Schon in der Antike übten sie einen großen Reiz auf die Gelehrten aus und auch heute gibt es noch zahlreiche ungelöste Fragen im Zusammenhang mit Primzahlen. Eine wichtige Einsatzmöglichkeit sind diverse Verschlüsselungsverfahren, weshalb die Erforschung der Primzahlen auch heute noch einen Nutzen hat. Jede natürliche Zahl, die genau zwei Teiler hat, ist eine Primzahl. Daraus ergibt sich unmittelbar, dass 0 keine Primzahl ist, da sie unendlich viele Teiler hat, und dass 1 keine Primzahl ist, da sie nur einen einzigen Teiler hat. Die ersten Primzahlen lauten folgendermaßen: \begin{equation*} 2,3,5,7,11,13,17,19,23,29, ... \end{equation*}

Aufgabe 1

Finde die kleinste dreistellige Primzahl. Lösung: ausklappen 101 einklappen

Bereits bei relativ kleinen Zahlen wie etwa 571, 1001 oder 1993 ist es schwierig, festzustellen, ob es sich um eine Primzahl handelt. Es wird nun ein allgemeines Verfahren vorgestellt, mit dem überprüft werden kann, ob eine natürliche Zahl $n$ eine Primzahl ist.

1. Es wird die Wurzel der zu überprüfenden Zahl $n$ berechnet.
2. Alle Primzahlen, die kleiner als diese Wurzel sind, werden aufgeschrieben.
3. Es wird mit Hilfe der Teilbarkeitsregeln oder mit dem Taschenrechner überprüft, ob $n$ durch eine dieser Zahlen teilbar ist.
4. Wenn die Zahl $n$ durch keine dieser Zahlen teilbar ist, ist sie eine Primzahl.

Begründung

Es wird hier begründet, warum es ausreicht, wenn man alle Primzahlen überprüft, die kleiner als $\sqrt{n}$ sind. Damit eine natürliche Zahl $ n$ keine Primzahl ist, muss es zwei natürliche Zahlen $1< a , b < n $ geben, sodass $a\cdot b=n$ gilt. Ist eine der beiden Zahlen größer als $\sqrt{n}$, so muss die andere Zahl kleiner als $\sqrt{n}$ sein, da sonst $a\cdot b>n$ wäre. Für den Fall, dass $\sqrt{n}\in \mathbb{N}$ gilt, ist ohnehin sichergestellt, dass $n$ keine Primzahl ist, da sie dann den Teiler $\sqrt{n}$ besitzt.

Beispiel 1

Es wird überprüft, ob 1993 eine Primzahl ist. Bevor man das obige Verfahren anwendet, sollte man mit den einfachen Teilbarkeitsregeln überprüfen, ob eventuell dadurch schon eine Entscheidung getroffen werden kann. Da die letzte Ziffer nicht 0, 2, 4, 5, 6 oder 8 ist, fallen bereits sehr viele Teilbarkeiten weg. Die Ziffernsumme 22 ist nicht durch 3 teilbar (und somit auch nicht durch 9) und die alternierende Ziffernsumme 2 ist nicht durch 11 teilbar. Es muss daher das obige Verfahren angewendet werden. Die Wurzel von 1993 lautet ungefähr 44,63. Daher müssen alle Primzahlen bis 44 überprüft werden. Das sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 und 43. Es bleibt nun nichts anderes übrig, als 1993 durch all diese Zahlen zu dividieren. Bleibt irgendwo kein Rest, so hat man einen Teiler gefunden. Da sich aber herausstellt, dass die Division immer zu Nachkommastellen führt, ist 1993 eine Primzahl.

Das Sieb des Eratosthenes (benannt nach dem griechischen Matematiker Eratosthenes, ca. 200 v. Chr.) ist ein Verfahren, mit dem man alle Primzahlen bis zu einer bestimmten Obergrenze $n$ auffinden kann. Dazu schreibt man alle Zahlen von 1 bis zur gewünschten Obergrenze in eine Tabelle (praktisch sind 6 Spalten) und geht folgendermaßen vor:

1. Die Zahl 1 wird durchgestrichen, da diese per Definition keine Primzahl ist.
2. Die kleinste Zahl, die nicht durchgestrichen ist, wird markiert. Diese ist eine Primzahl.
3. Alle Vielfachen dieser Zahl werden durchgestrichen, da dies keine Primzahlen sein können.
4. Springe zu Punkt 2, sofern die kleinste verbliebene Zahl kleiner als $\sqrt{n}$ ist. Sonst beende das Verfahren (alle offenen Zahlen sind Primzahlen).

Für $n=102$ erhält man folgendes Ergebnis:

Begründung

Hier wird begründet, wieso man abbrechen kann, sobald man $\sqrt{n}$ erreicht hat. Damit eine natürliche Zahl $k\leq n$ keine Primzahl ist, muss es zwei natürliche Zahlen $1< a,b < k$ geben, sodass $a\cdot b=k$ gilt. Ist eine der beiden Zahlen größer als $\sqrt{n}$, so muss die andere Zahl kleiner als $\sqrt{n}$ sein, da sonst $a\cdot b>n$ und somit auch $a\cdot b > k$ wäre. Für den Fall, dass $\sqrt{n}\in \mathbb{N}$ gilt, ist ohnehin sichergestellt, dass $n$ keine Primzahl ist (da sie den Teiler $\sqrt{n}$ besitzt). Somit genügt es, zu überprüfen, ob eine Zahl ein Vielfaches der Zahlen aus $\{k \in \mathbb{N}\mid k< \sqrt{n} \}$ ist.

Der Satz von Euklid besagt, dass es unendlich viele Primzahlen gibt.

Beweis

Man startet mit einer beliebigen Primzahl $p_1$ (z. B. 3). Die Zahl $p_1+1$ ist auf keinen Fall durch $p_1$ teilbar, da die Division 1 Rest ergibt. Es ist also $p_1+1$ entweder selbst eine Primzahl oder das Produkt neuer Primzahlen: $3+1=4=2\cdot 2$. In diesem Fall erhält man die neue Primzahl $p_2=2$. Die Zahl $p_1\cdot p_2+1$ kann ebenfalls nicht durch $p_1,p_2$ teilbar sein, weshalb man auch hier eine neue Primzahl erhalten muss: $3\cdot 2+1=7$. Da man diesen Schritt unendlich oft durchführen kann und in jedem Schritt mindestens eine neue Primzahl erhält, muss es unendlich viele Primzahlen geben.

Einerseits gibt es unendlich viele Primzahlen. Andererseits gibt es unendlich viele natürliche Primzahlen. Aber weniger als ein Drittel aller natürlichen Zahlen sind Primzahlen. Das zeigt: Zwei Mengen, die unendlich viele Elemente besitzen, müssen daher nicht gleich groß sein.

Feedback

Bitte nutze das folgende Textfeld, um Feedback, Verbesserungsvorschläge oder Fehler mitzuteilen. Deine Nachricht wird vollkommen anonym gespeichert.