0 Daumen
799 Aufrufe

Aufgabe:

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


Problem/Ansatz:

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

Avatar von

Für n=1 stimmt die Behauptung.

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

pn22n p_n ≥ 2^{2^n}

Betrachte

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

1 Antwort

+1 Daumen
 
Beste Antwort

Vollständige Induktion über nn.

pn+1i=1n22i=2i=1n2i22n+1p_{n+1}\leq \prod\limits_{i=1}^n 2^{2^i} = 2^{\sum_{i=1}^n 2^i}\leq 2^{2^{n+1}}

Avatar von 107 k 🚀

pn+1(i=1n22i)+1=(2i=1n2i)+1=22n+12+122n+1p_{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 nn Primzahlen 11 addiert.

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

Daher kommt die Ungleichung

        pn+1i=1n22ip_{n+1}\leq \prod\limits_{i=1}^n 2^{2^i}.

Beachte, dass in dem Ausdruck

        2i=1n2i2^{\sum_{i=1}^n 2^i}

die Summe im Exponenten steht.

Ein anderes Problem?

Stell deine Frage