primzahl der Form 2^n + 1

Neue Frage »

11.06.2007, 20:46	kiste	Auf diesen Beitrag antworten »
primzahl der Form 2^n + 1 Hi, ich möchte beweisen das wenn $\begin{eqnarray} 2^n + 1 \end{eqnarray}$ eine Primzahl ist gilt $\begin{eqnarray} n=2^m \end{eqnarray}$ . Da ich keiner Zahlentheorievorlesung oder so höre hab ich leider überhaupt keine Ahnung wie ich überhaupt anfangen soll. Irgendwie hab ich mir gedacht ich nehme an $\begin{eqnarray} 2^n + 1 \end{eqnarray}$ ist eine Primzahl aber n hat nicht die gewünschte Form und führe es zum Widerspruch aber weiter kam ich leider nicht Ein kleiner Anstuppser wo man den anfangen kann wäre nett, Gruß kiste
11.06.2007, 20:49	therisen	Auf diesen Beitrag antworten »
Hallo, das liegt daran, dass $\begin{eqnarray} 2^n+1 \end{eqnarray}$ durch $\begin{eqnarray} 3 \end{eqnarray}$ teilbar ist, falls $\begin{eqnarray} n \end{eqnarray}$ keine Zweierpotenz ist. EDIT: Sorry, hätte mir das nochmal kurz hinschreiben sollen. Natürlich wollte ich auf die u.g. Faktorisierung von $\begin{eqnarray} 2^n+1^n \end{eqnarray}$ hinaus (meine Aussage stimmt nur für ungerades n). Gruß, therisen
11.06.2007, 20:58	Tomtomtomtom	Auf diesen Beitrag antworten »
Angenommen n=pq wobei 2 kein Teiler von q ist. (Also es existiert ein ungerader Teiler). Dann kannst du zeigen, daß 2^p+1 ein Teiler von 2^n+1 ist. Und Therisen hat nicht recht, wie 2^6+1=65 zeigt.
11.06.2007, 21:41	kiste	Auf diesen Beitrag antworten »
Danke für die Antworten, bin aber wohl nicht so begabt in dem Teil der Mathematik Also ich habe rausgefunden das wenn $\begin{eqnarray} 2^n + 1 \end{eqnarray}$ teilbar durch $\begin{eqnarray} 2^p + 1 \end{eqnarray}$ ist der Teiler ungerade sein muss, aber ich glaube das bringt nichts oder? Wie kann man den Teilbarkeit allgemein von solchen Zahlen zeigen? In der vorigen Teilaufgabe musste ich für einen Beweis den euklidischen algorithmus anwenden aber der bringt mich hier nicht weiter oder? Auch die explizite Darstellung der 1 als Potenz 1^n hat mich leider nicht weitergebracht. Gruß, ein leicht verwirrter, kiste
11.06.2007, 21:45	AD	Auf diesen Beitrag antworten »
Du solltest den Tipp von Tomtomtomtom wirklich befolgen, er hat doch ziemlich exakt beschrieben, was zu machen ist.
11.06.2007, 21:49	therisen	Auf diesen Beitrag antworten »
Als Vorbereitung kannst du auch mal z.B. mit Hilfe von Polynomdivision $\begin{eqnarray} (a^n-b^n) : (a-b) = \dots \end{eqnarray}$ berechnen. Gruß, therisen
Anzeige

11.06.2007, 22:03	AD	Auf diesen Beitrag antworten »
@kiste Mit Modulorechnung (falls du sie kennst) geht's fast noch schneller, in einer Zeile.
11.06.2007, 22:06	kiste	Auf diesen Beitrag antworten »
Mhhh $\begin{eqnarray} (a^n - b^n) : (a-b) =a^{n-1} + a^{n-2}b + \dots + ab^{n-2} + b^{n-1} \end{eqnarray}$ Folgt das dann mit $\begin{eqnarray} a=2^p \end{eqnarray}$ und $\begin{eqnarray} b= -1 \end{eqnarray}$ ? Also $\begin{eqnarray} ((2^p)^q - (-1)^q) : (2^p - (-1)) = ((2^p)^q + 1) : (2^p + 1) \end{eqnarray}$ . Da q ungerade folgt dass das (-1)^q = -1, also ist es teilbar? Edit: Nein hatte noch fast nichts mit modulo-Rechnung zu tun bis auf die wahren Basics, soll heißen nicht mehr als die Definition. Aber falls das obenstehende richtig ist würde es mich sehr interessieren wie es damit geht
11.06.2007, 22:08	AD	Auf diesen Beitrag antworten »
Eigentlich steckt genau dasselbe dahinter, nur der Aufschrieb ist kürzer: $\begin{eqnarray} 2^n = (2^p)^q \equiv (-1)^q = -1 \mod (2^p+1) \end{eqnarray}$
11.06.2007, 22:16	kiste	Auf diesen Beitrag antworten »
Ok danke euch Jetzt ist der Tag voll gerettet g Gruß kiste PS: Welcher Satz ist es das man die Modulo-Rechnung einfach in die Potenz ziehen darf?
11.06.2007, 22:21	Lazarus	Auf diesen Beitrag antworten »
Grundrechenregeln für Modulo Rechnung. Ist $\begin{eqnarray} a \equiv \alpha \pmod m \end{eqnarray}$ und $\begin{eqnarray} b\equiv \beta \pmod m \end{eqnarray}$ so gilt $\begin{eqnarray} ab\equiv \alpha\beta \pmod m \end{eqnarray}$ Hier gilt eben $\begin{eqnarray} a=b \end{eqnarray}$ und das ganz in $\begin{eqnarray} q \end{eqnarray}$ -facher Vielfachheit.

Neue Frage »

Antworten »

primzahl der Form 2^n + 1

Verwandte Themen