Beweisen Sie für die n-te Primzahl pn < 2^(2^n)

Question

Aufgabe:

Beweisen Sie für die n-te Primzahl p_n < 2^(2^n)

Problem/Ansatz:

Wie kann man folgende Behauptung beweisen? Ich weiß, dass dies eine Folgerung aus dem Satz von Euklid ist und 2^{2^n} ist eine Fermat-Zahl. Wie kann man diese Aussage aber beweisen?

Comments

Für n=1 stimmt die Behauptung.

Angenommen die Behauptung ist falsch. Dann wähle das kleinste n>1 s.d.

\( p_n ≥ 2^{2^n} \)

Betrachte

$$ N:= p_1 \dotsm p_{n-1} +1 $$ Und schätze ab \( N < 2^{2^n}\) sowie \( N \ge 2^{2^n} \). Dann ergibt sich der gewünschte Widerspruch.

Answer 1

Vollständige Induktion über \(n\).

\(p_{n+1}\leq \prod\limits_{i=1}^n 2^{2^i} = 2^{\sum_{i=1}^n 2^i}\leq 2^{2^{n+1}}\)

Comments

\(p_{n+1}\leq (\prod\limits_{i=1}^n 2^{2^i}) +1 = (2{\sum_{i=1}^n 2^i}) +1 = 2^{2^{n+1}-2}+1 \leq 2^{2^{n+1}}\)

Richtig so?

---

Im Beweis des Satzes von Euklid wird zum Produkt der ersten \(n\) Primzahlen \(1\) addiert.

Einziger Grund dafür ist \(n=1\). Für \(n > 1\) kann nämlich genauso gut vom Produkt der ersten \(n\) Primzahlen \(1\) subtrahiert werden.

Daher kommt die Ungleichung

        \(p_{n+1}\leq \prod\limits_{i=1}^n 2^{2^i}\).

Beachte, dass in dem Ausdruck

        \(2^{\sum_{i=1}^n 2^i}\)

die Summe im Exponenten steht.