Es gibt Zahlen, die nur zwei Teiler haben, nämlich \(1\) und sich selbst. Diese Zahlen nennt man Primzahlen. Die ersten Primzahlen sind \begin{align*}2,3,5,7,11,13, 17, 19, 23, 29, 31, 37,...\end{align*}
Es gibt unendlich viele Primzahlen, der Beweis hierfür ist über 2000 Jahre alt! Du findest ihn im Beweisarchiv. Primzahlen lösen bei Mathematikern eine besondere Faszination aus, da sie, obwohl sie für viele Bereiche der Mathematik so grundlegend sind, bis heute viele Fragen aufwerfen:

    - Gibt es unendlich viele Primzahlzwillinge, also Primzahlen, deren Differenz \(2\) ist (z.B. \(17\) und \(19\))?
    - Gibt zwischen zwei Quadratzahlen stets mindestens eine Primzahl? (Vermutung von Legendere)
    - Ist eine gerade Zahl größer als \(2\) immer als Summe zweier Primzahlen darstellbar (z.B. \(100=47+53\))? (Vermutung von Goldbach)

Bei den letzten beiden Fragen weiß man heute dank Computerhilfe, dass sie für die ersten Milliarden (und mehr) Zahlen mit „ja“ beantwortet werden können. Ein Beweis dafür, dass dies immer der Fall ist, ist das natürlich nicht. Vielleicht gelingt es dir ja eines Tages, eine dieser Vermutungen zu beweisen, wer weiß?

Jede Zahl ist entweder bereits eine Primzahl oder hat eine Primzahl als Teiler (einen solchen Teiler nennt man Primteiler). Wenn man nun eine Zahl, die keine Primzahl ist, durch einen ihrer Primteiler teilt, entsteht eine weitere Zahl, die wieder entweder prim ist, oder einen Primteiler hat. Wenn man so weitermacht, hat man irgendwann die Zahl, mit der man angefangen hat, als Produkt von Primzahlen dargestellt. Diese Darstellung ist (natürlich abgesehen von der Reihenfolge der Faktoren) eindeutig und wird Primfaktorzerlegung dieser Zahl genannt. Bspw. ist \begin{align*}60=3 \cdot 20=3 \cdot 2 \cdot 10=3 \cdot 2 \cdot 5 \cdot 2. \end{align*}
Meistens fasst man die Primzahlen als Potenzen zusammen, und ordnet die entsprechenden Primzahlpotenzen der Größe nach. Man schreibt also \begin{align*}60 =2^2 \cdot 3 \cdot 5. \end{align*}
Weitere Beispiele für die Primfaktorzerlegung einer natürlichen Zahl:
\begin{align*}144 &=12 \cdot 12 \\&=3 \cdot 4 \cdot 3 \cdot 4 \\&= 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \\&= 2^4 \cdot 3^2 \\1050 &= 105 \cdot 10 \\&= 21 \cdot 5 \cdot 5 \cdot 2 \\&= 2 \cdot 3 \cdot 5 \cdot 5 \cdot 7 \\&= 2 \cdot 3 \cdot 5^2 \cdot 7\end{align*}

 

 


Die Primfaktorzerlegung gibt also an, aus welchen nicht mehr weiter teilbaren Zahlen eine Zahl besteht. Daher vergleicht man Primzahlen gerne mit Atomen – sie sind die unteilbaren Bausteine der Natürlichen Zahlen; deswegen sind sie für die Zahlentheorie auch so wichtig.

Wenn man Primzahlen finden will, kann man das Sieb des Erasthothanes benutzen. Anstatt sich zu fragen, ob eine Zahl eine Primzahl ist, streicht man stattdessen alle Zahlen, die keine Primzahl sein können. Nach dem Ausschlussverfahren müssen am Ende die Zahlen, die nicht durchgestrichen worden sind, Primzahlen sein. Die Primzahlen werden sozusagen ausgesiebt. Man geht dabei wie folgt vor:

-Man schreibt zunächst alle Zahlen in eine Liste (die zur besseren Übersicht in Zehnerschritte unterteilt ist). danach geht man alle Zahlen durch.

-Man beginnt mit der \(2\). Da die \(2\) noch nicht durchgestrichen wurde, muss sie eine Primzahl sein. Danach streicht man alle Vielfachen der \(2\) durch, sie sind ja durch \(2\) teilbar und können daher keine Primzahlen sein.

-Danach geht man zur \(3\). Da die \(3\) noch nicht durchgestrichen ist, muss sie eine Primzahl sein. Danach streicht man alle Vielfachen der \(3\) durch, denn auch sie können keine Primzahlen sein.

-Die \(4\) (und alle ihre Vielfachen) wurde(n) bereits durchgestrichen.

-Die \(5\) muss wieder eine Primzahl sein. Danach streicht man alle Vielfachen der \(5\) durch.

So macht man weiter, bis man alle Primzahlen bis zu einer gewünschten Größe gefunden hat. In der Animation unten ist das Sieb des Erasthothanes für die Primzahlen bis \(120\) dargestellt.

Mittlerweile gibt es wesentlich schnellere Verfahren, für eine Zahl zu entscheiden, ob sie eine Primzahl ist oder nicht. Diese Verfahren, zum Beispiel der AKS-Primzahltest sind aber relativ schwierig zu verstehen.

Trotz dieser Verfahren ist es, selbst für moderne Computer, schwer und zeitaufwendig, für große Zahlen zu entscheiden, ob eine Zahl Primzahl ist oder nicht, bzw. eine Primfaktorzerlegung durchzuführen; kannst du zum Beispiel entscheiden, ob \(610369\) eine Primzahl ist oder nicht? Und wenn nein, was sind ihre Primfaktoren?

Dass Primfaktorzerlegungen so vergleichsweise schwer zu bestimmen sind, hat aber auch Vorteile: Zahlreiche Verschlüsselungsverfahren, die zum Beispiel Online-Banking möglich machen nutzen den Fakt aus, dass es selbst für Computer zu schwierig sein kann, zu einer gegebenen Zahl Primteiler zu finden.

Im nächsten Kapitel wird es dann um zwei Begriffe gehen, bei denen Primfaktoren eine wichtige Rolle spielen, dem ggT und das kgV.