Vorlesung 2 Freudenberg

Aus ProgrammingWiki

ÜA: Beweis das die Menge der Primzahlen abzählbar unendlich ist

-> Beweis durch Wiederspruch

- Primzahlen sind eine Teilmenge der natürlichen Zahlen -> sind auf die natürlichen Zahlen abbildbar

Fundamentalsatz der Arithmetik: jede Zahl die größer als 1 ist, lässt sich als Produkt von Primzahlen darstellen

A = Es gibt eine unendliche Anzahl an Primzahlen
A(Dach) = Es gibt eine endliche Anzahl an Primzahlen

- wenn A(Dach) richtig ist, dann gibt es eine höchste Primzahl (Zahl h)
- Reihe der Primzahlen: 2, 5, 7, 11, 13, 17, 19, 23, ….
- n = 2 x 5 x 7 x 11 x 13 x 17 x 19 x 23 x … x h +1
- durch die Addition der Zahl 1 ist unsere endliche Reihe nicht mehr durch eine der Primzahlen teilbar, d.h.:

1. n ist selber eine Primzahl
2. n ist teilbar durch eine Primzahl die größer als h ist

- wenn erste Erklärung stimmt, hätten wir bewiesen, dass es eine größere Primzahl als h gäbe
- die zweite Erklärung nutzt den Fundamentalsatz der Arithmetik, da n nicht durch eine der bekannten Primzahlen teilbar ist, muss es durch eine Primzahl die größer als h ist, teilbar sein