Lösung - Primzahlen 01

Gibt es unendlich viele Primzahlen?

Während im Intervall von 0 - 100 noch 25 Primzahlen vertreten sind, werden es in einem Intervall gleicher Länger bei höheren Zahlen deutlich weniger. Zwischen 1.000.000 und 1.000.100 sind es nur mehr 6 Primzahlen, wenn man höhere Zahlen betrachtet, noch weniger. Es stellt sich daher die Frage, ob die Anzahl der Primzahlen eventuell endlich ist!

Bereits EUKLID (365 - 300 v. Chr.) beantwortete die Frage, ob es unendlich viele Primzahlen gibt, durch einen indirekten Beweis.

• Euklid nahm an, dass es nur endlich viele Primzahlen gibt.
• Wenn es endliche viele Primzahlen gibt, kann man diese mit einem Index versehen (durchnumerieren) und der Größe nach sortieren.
  P ={2, 3, 5, 7, ... , p_n}
• Wir bilden das Produkt aller dieser Primzahlen und zählen 1 hinzu:
  q = 2*3*5*7*...*p_n + 1
• Wenn die Menge P endlich ist, muss q nun Teiler aus P enthalten, da P alle vorhandenen Primzahlen enthält.
• Egal, durch welche Primzahl aus P q geteilt wird, es bleibt immer Rest 1
• Keine Primzahl aus P kann daher Teiler von q sein - q ist entweder selbst eine Primzahl oder besitzt andere Primteiler
• Dies ist aber ein Widerspruch, da wir ja angenommen haben, dass P bereits alle Primzahlen enthält.

Die Annahme, dass es endlich viele Primzahlen gibt, ist somit falsch - es muss unendlich viele Primzahlen geben.

[ Schliessen ]