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

Question

Aufgabe:

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

Problem/Ansatz:

Wie kann man folgende Behauptung beweisen? Ich weiß, dass dies eine Folgerung aus dem Satz von Euklid ist und 2²ⁿ 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.