0 Daumen
139 Aufrufe

Entscheiden Sie, ob \( 2^{3^{33333}} + 1 \) eine Primzahl ist. Begründen Sie Ihre Entscheidung.

Wie begründe ich es? Hierbei ist es mir wichtig, zu wissen, wie man es schnell auf dem ersten Blick erkennt.

Es muss nicht unbedingt diese Zahl sein, ihr könnt auch eine andere Zahl nehmen, mit dieser Struktur.

von

3 Antworten

+2 Daumen
 
Beste Antwort

bei solchen Zahlen hast Du keine reelle Chance zu zeigen, dass es sich um eine Primzahl handelt. Zum Vergleich: die größte bekannte Mersenne-Primzahl ist z.Zt.: \(2^{77.232.917}-1\). Und die Zahl aus der Aufgabe ist sehr viel größer.

Also liegt der Verdacht nahe, dass es sich um keine Primzahl handelt und man eine Teilbarkeit durch einen kleinen Teiler nachweisen kann.

Die obige Zahl \(z\) hat die Form $$z = 2 ^n + 1; \quad n \in \mathbb{N}$$ wobei \(n\) sicher durch 3 teilbar ist und ungerade ist. Man könnte also auch schreiben: $$z = 2^{3 (2k-1)} + 1 = 8^{2k+1}+1; \quad k \in \mathbb{N}$$

Betrachtet man nun den Rest beim Teilen von Potenzen von 8 durch 3, so ergibt sich ein Muster: $$\begin{align}  8^1 &= 2 \cdot 3 + 2 \\ 8^2 &= 21 \cdot 3 + 1 \\ 8^3 &= 170 \cdot 3 + 2 \\ 8^4 &= 1365 \cdot 3 + 1\end{align}$$ Der Rest nach dem Teilen durch 3 ist also immer 2 bei ungeraden Exponenten. Es gilt also offensichtlich, dass

$$ 8^{2k+1} \equiv 2 \mod 3 \quad \Rightarrow  8^{2k+1} + 1\equiv 0 \mod 3$$ Daraus folgt, dass \(z\) durch 3 teilbar und somit keine Primzahl ist.

Gruß Werner

von 15 k

Da 3^n = u ungerade ist, folgt direkt, dass 2^u mod 3  =  (-1)^u = -1

Da 3n = u ungerade ist, folgt direkt, dass 2u mod 3  =  (-1)u = -1

Stimmt, so ist es noch einfacher.

0 Daumen

Hallo,

du kannst es ja schauen, was bei der Primfaktorzerlegung heraus kommt. Wenn das geht, dann ist es keine Primzahl.#

\({2^{3}}^{33 \ 333}\) Das ist eine Zahl der Form: \({2}^{x}\)

Das ist also dann auch die Primfaktorzerlegung \(2^x\). Da dort aber noch ein \(+1\) ist, kann man die Zerlegung nicht machen.

Deshalb würde ich sagen, dass diese Zahl eine Primzahl ist.

Sicher bin ich mir nicht.

Gruß

Smitty

von 4,3 k
0 Daumen

Lies Dir den Eintrag in der Wikipedia zu Fermat-Zahl durch. Da steht ziemlich weit am Anfang drin, warum Deine Zahl keine Primzahl sein kann (mit Beweis). Man kann den Teiler \(2^{3^{33332}}+1\) explizit angeben.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...