Primzahl (Beweise)
Bei den folgenden Beweisen zu Primzahlen geht es darum, zu zeigen, dass es keine größte Primzahl gibt. Daraus folgt dann, dass unendlich viele Primzahlen existieren. Der bekannteste Beweis ist der Satz von Euklid. Neben diesem sind mit der Zeit auch noch andere Beweise aufgestellt worden.
| Inhaltsverzeichnis |
Stieltjes' Beweis (1890)
Angenommen 
seien die einzigen Primzahlen, die existieren. Dann gilt für die Zahl N = p1 * p2 * p3 * ... * pr, dass sie sich in der Form N = m * n zerlegen lässt, wobei für beide Zahlen m und n gilt, dass sie größer oder gleich 1 sind. Jede Primzahl pi teilt nun entweder m oder n, aber nicht beide zugleich. Aus diesem Grund ist m+n durch keine der existierenden Primzahlen teilbar. Da aber m+n ≠ 1 ist, ist m+n eine weitere, größere Primzahl oder durch eine weitere noch unbekannte Primzahl teilbar.
Beispiel
Angenommen es gäbe nur die 4 Primzahlen 2, 3, 5 und 7. Dann wäre N = 2 * 3 * 5 * 7 = 210. N ließe sich beispielsweise in die Faktoren 15 (= 3*5) und 14 (= 2*7) zerlegen. 15 + 14 = 29. 29 lässt sich weder durch 2, 3, 5 oder 7 teilen. Also ist 29 eine Primzahl oder durch eine Primzahl größer 7 teilbar.
Schorns Beweis
Vorbemerkung zu "paarweise teilerfremd"
Dieser (Schorns) und der folgende (Goldbachs) Beweis erfordern eine Erklärung. Zwei Zahlen a1 und a2 (nicht unbedingt Primzahlen) ohne gemeinsame Primfaktoren, also mit ggT (größter gemeinsame Teiler) 1, heißen teilerfremd. Eine Menge von Zahlen heißt paarweise teilerfremd, wenn je zwei beliebige Zahlen aus dieser Menge teilerfremd sind.
Beweis
Angenommen, es gäbe genau m verschiedene Primzahlen. Dann setze n = m+1. Die n natürlichen Zahlen (n!)*i+1 für i = 1, ..., n sind paarweise teilerfremd. Wenn eine Primzahl pi die natürliche Zahl (n!)*i+1 teilt, dann sind die Primzahlen p1,p2,...,pn n = m+1 unterschiedliche Primzahlen, was im Widerspruch zu unserer anfänglichen Annahme steht, dass es genau m verschiedene Primzahlen gibt.
Beispiel
Angenommen, man geht davon aus, dass es genau 3 Primzahlen gibt. Dann ist n = 3+1 = 4. Mit dieser Zahl kann man die folgenden 4 Zahlen konstruieren: (4!)*1+1 = 25 = 5*5, (4!)*2+1 = 49 = 7*7, (4!)*3+1 = 73, (4!)*4+1 = 97. Alle vier Zahlen sind also paarweise teilerfremd. Das bedeutet auch, dass es mindestens 4 verschiedene Primzahlen gibt, was der Annahme widerspricht, dass es nur genau 3 Primzahlen gibt.
Vorteil
Der große Vorteil an Schorns Beweis gegenüber den Beweisen von Euklid und Stieltjes ist, dass man bei ihm nur von einer bestimmten Anzahl von Primzahlen, nicht aber von konkreten Primzahlen ausgeht.
Goldbachs Beweis (1730)
Wenn man eine unendliche Folge natürlicher Zahlen a1,a2,...,an,... finden kann, die paarweise teilerfremd sind, dann existiert eine Folge von Primzahlen p1,p2...,pn,..., für die gilt, dass die Primzahlen pi die natürliche Zahlen ai teilen. Diese Primzahlen sind dann alle verschieden. Wenn man also eine solche Folge findet, dann gibt es auch eine unendliche Anzahl von Primzahlen.
Es gibt eine solche Folge natürlicher Zahlen, die paarweise teilerfremd sind: die Folge der Fermat-Zahlen 
für n≥0. Es gilt nämlich Fm − 2 = F0 * F1 * ... * Fm − 1. Dieser Satz lässt sich per vollständiger Induktion zeigen. Daraus folgt für n<m, dass Fn die Zahl Fm-2 dividiert. Angenommen eine Primzahl p würde die beiden Fermat-Zahlen Fn und Fm dividieren, dann würde sie auch Fm-2 und Fm dividieren. Daraus würde p=2 folgen. Da aber jedes Fn ungerade und damit nicht durch 2 teilbar ist, ist jedes Glied dieser Folge teilerfremd zu allen anderen.
Weblinks