• Home
• Theorie
  • Potenzmenge
  • Unendlichkeit der Primzahlen
  • Euler-Formel
  • Diagonalsprache
  • O-Kalkül
  • wp-Kalkül
  • Informationstheorie
  • Schnelle Fourier Transformation
  • Diskrete Kosinus Transformation
• Praxis
  • Huffman Kodierung
  • Primzahlen TM
• Aufschriebe
  • Papers
  • Mathematik
• Tutorien
  • Info III WS05/06
  • Info IV SS06
  • Info III WS06/07
  • Info IV SS07

Unendlichkeit der Primzahlen

Eine Primzahl ist eine natürliche Zahl, deren einzige Teiler 1 und die Zahl selbst sind. So sind beispielsweise 2, 3, 5, 7, 11 und so weiter die ersten fünf Primzahlen. Der folgende Beweis soll nun darlegen, dass diese Folge der Primzahlen unendlich fortgesetzt werden kann. Er verwendet Algebra und ist in meinen Augen besonders schön und elegant.

Beweis

Wir wollen einen Widerspruchsbeweis führen, und nehmen daher an, dass es eine größte Primzahl gibt - sie sei mit $p$ bezeichnet. Zu $p$ betrachten wir jetzt die Zahl $2^p - 1$. Man nennt diese Zahl auch Mersenne-Zahl.

Offenbar ist $2^p - 1$ größer als $p$, also hat sie einen Primteiler $q < p$. Das $q$ die Zahl $2^p - 1$ teilt ist äquivalent zu der Aussage

$$2^p \equiv 1 \mod q$$

Nun kommt die Algebra ins Spiel: Wir betrachten die zyklische multiplikative Gruppe $G := \mathbb{Z}_q \setminus \{0\}$. Offenbar hat die $2$ in $G$ die Ordnung $p$. Die Gruppe hat nach Definition gerade $q - 1$ Elemente, und jetzt schlägt die Klappe zu: Nach dem Satz von Lagrange teilt die Ordnung jedes Elements die Gruppengröße. In unserem Fall also

$$p | q - 1$$

Damit folgt jedoch $p < q$.

Wir hatten $q$ als Primzahl angenommen, und konnten zeigen, dass sie echt größer als $p$ ist. Dies ist der Widerspruch zur Voraussetzung, dass $p$ die größte Primzahl ist. Es gibt also beliebig große Primzahlen, und somit folgt, dass die Menge der Primzahlen unendlich groß sein muss. $\square$

Literatur

[1] Martin Aigner, Günther M. Ziegler, Das BUCH der Beweise, Springer-Verlag 2002