Ein Klassiker

Vielgerühmt ob seiner Schönheit ist Euklid's klassischer Beweis, daß es unendlich viele Primzahlen gibt.

Euklids Klassiker

Annahme: es gibt eine größte Primzahl P. Die Anzahl der Primzahlen ist aufgrund dieser Annahme endlich.

Behauptung: Die Annahme trifft nicht zu.

Beweis: Man konstruiere eine Zahl a wie folgt:

a = 2 ´ 3 ´ 5 ´ 7 ´ 11 ´...´ P + 1

a ist das Produkt aller Primzahlen, vermehrt um 1. Die Zahl a ist offenbar durch keine der Primzahlen teilbar, da bei einer Division von a mit einer Primzahl der Rest 1 bleibt. Folgerung a ist entweder prim oder aus Primfaktoren zusammengesetzt, die ungleich den vorausgesetzten (und damit zwangsweise größer als P) sind. Dies steht im Widerspruch zur Annahme. Folglich ist die Annahme falsch und es gibt unendlich viele Primzahlen.

Im Umkehrverfahren wird auch etwas nützliches daraus. Diese Methode läßt sich konstruktiv verwenden, um sehr große Primzahlen zu erzeugen. Allerdings ist nicht jede der zu gebildeteten Zahlen auch prim, wie die nachstehenden Beispiele zeigen:

Bildungsformel Wert Faktoren
2 ´ 3 + 1 7 prim
2 ´ 3 ´ 5 + 1 31 prim
2 ´ 3 ´ 5 ´ 7 + 1 211 prim
2 ´ 3 ´ 5 ´ 7 ´ 11 + 1 2311
2 ´ 3 ´ 5 ´ 7 ´ 11 ´ 13 + 1 30031
2 ´ 3 ´ 5 ´ 7 ´ 11 ´ 13´ 17 + 1 510511
2 ´ 3 ´ 5 ´ 7 ´ 11 ´ 13 ´ 17 ´ 19 + 1 9699691
2 ´ 3 ´ 5 ´ 7 ´ 11 ´ 13 ´ 17 ´ 19 ´ 23 + 1 223092871

Tatsächlich sind Zahlen mit großen Primfaktoren auch schon ein nettes Ergebnis.


Stand: 19.11.2003 /
 HPs Home      Primzahlen/Home