Primzahlen

Primzahlen sind Zahlen, die nur durch eins und durch sich selbst teilbar sind. Die Eigenschaften der Primzahlen werden oft zum Beispiel in der Kryptographie genutzt.

Definition und Beispiele

Eine Primzahl ist eine natürliche Zahl, die ohne Rest nur durch eins und durch sich selbst teilbar ist, wobei die Eins selbst keine Primzahl ist. Die kleinste Primzahl ist die Zwei – sie ist ohne Rest durch eins und durch zwei teilbar. Es ist zugleich die einzige Primzahl, die gerade ist. Alle anderen Primzahlen sind ungerade, denn jede andere gerade Zahl ist außer durch eins und durch sich selbst auch noch durch zwei teilbar.

Die Folge der ersten 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, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…

Mit Primzahlen hängt der Fundamentalsatz der Arithmetik zusammen, der besagt, dass sich jede ganze Zahl größer als 1 als Produkt von Primzahlen schreiben lässt.

Teste, ob eine Zahl eine Primzahl ist

Eigenschaften der Primzahlen

• Es gibt unendlich viele Primzahlen. Der Beweis steht im Artikel über den Widerspruchsbeweis.
• Für jede ganze Zahl z>1 gilt, dass im Intervall ]z; 2z[ mindestens eine Primzahl liegt. Beispiel: Für z = 2 haben wir das Intervall ]2; 4[. Die einzige ganze Zahl in diesem Intervall ist die Drei, und das ist eine Primzahl. Für z = 5 erhalten wir das Intervall ]5; 10[, also die Zahlen 6, 7, 8, 9. Die Zahl 7 ist eine Primzahl. Ähnlich für größere z.
• Eine Mersenne-Primzahl ist eine Primzahl, die um eins kleiner ist als eine ganzzahlige Potenz von zwei. Eine Mersenne-Primzahl M hat also die Form M = 2^z − 1, wobei z eine natürliche Zahl ist. Ein Beispiel ist die Primzahl 3, denn es gilt 2² − 1 = 3. Oder 7, denn es gilt 2³ − 1 = 7.
• Die größten bekannten Primzahlen sind meist Mersenne-Primzahlen. Zum Beispiel wurde am 23. August 2008 die Mersenne-Primzahl M_43112609 gefunden, wobei der untere Index den Exponenten z angibt. Es handelt sich also um die Primzahl 2^43112609 − 1, die 12.978.189 Ziffern hat und zu dieser Zeit die größte bekannte Primzahl war.

Folge ohne Primzahlen

Man kann beliebig lange endliche Folgen aufeinanderfolgender natürlicher Zahlen finden, unter denen keine einzige Primzahl vorkommt. Eine solche Folge kann die Form k!+2, k!+3, …, k!+k haben und enthält k − 1 aufeinanderfolgende zusammengesetzte Zahlen (das Ausrufezeichen steht für die Fakultät).

Für k = 6 erhalten wir zum Beispiel fünf aufeinanderfolgende zusammengesetzte Zahlen der Form: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Diese Zahlen sind der Reihe nach durch zwei, drei, vier, fünf und sechs teilbar, denn die Zahl 6! = 720 ist bestimmt durch alle diese Zahlen teilbar, weil sie als deren Produkt entstanden ist: 6! = 6 · 5 · 4 · 3 · 2. Wenn die Zahl 720 durch drei teilbar ist, dann muss auch die Zahl 720 + 3 durch drei teilbar sein. Ähnlich bei den übrigen.

Kleiner fermatscher Satz

Für jede Primzahl p und jede ganze Zahl z gilt, dass die Zahl z^p − z durch die Primzahl p teilbar ist.

Beispiel: Nehmen wir die Primzahl p = 3 und die ganze Zahl z = 4. Wir berechnen den Wert von 4³ − 4. Das ist gleich 60. Dabei gilt aber 60/3 = 20, die Zahl drei teilt also die Sechzig ohne Rest, was dem fermatschen Satz entspricht. Ein anderes Beispiel: p = 7, z = 10. Wir berechnen das Zwischenergebnis 10⁷ − 10 = 9999990 und teilen diese Zahl durch sieben: 9999990/7 = 1428570. Wieder haben wir ein Ergebnis ohne Rest erhalten.

Ungelöste Fragen

Mit Primzahlen hängen viele bekannte Vermutungen zusammen, die sich bisher (2011) weder beweisen noch widerlegen ließen. Zu den zwei bekanntesten gehören:

• Unendlichkeit der Primzahlzwillinge: Ein Primzahlzwilling ist ein Zahlenpaar (z, z + 2), wobei beide Zahlen Primzahlen sind. Zum Beispiel (3, 5) oder (29, 31). Die Frage ist, ob es unendlich viele solcher Primzahlzwillinge gibt. Man vermutet es, aber ein Beweis fehlt.
• Riemannsche Vermutung: Alle nichttrivialen Nullstellen der riemannschen Zetafunktion haben den Realteil $\frac{1}{2}$. Die Vermutung hängt mit der Verteilung der Primzahlen zusammen und ist eines der sogenannten Millennium-Probleme, und für ihre Lösung erwartet dich ein Preis von einer Million Dollar.