Aufgabe zu Primzahlen

21.02.2012, 18:42

gästlicherGast

Aufgabe zu Primzahlen

Meine Frage:
Hallo Leute,

mein Problem bezieht sich auf folgende aufgabe:
Zeige: Wenn $\begin{eqnarray*} p=2^r-1 \end{eqnarray*}$ eine Primzahl ist, dann ist auch r eine Primzahl.

Dazu hab ich folgende Musterlösung:
Sei r keine Primzahl, dann gilt $\begin{eqnarray*} r=q*a \end{eqnarray*}$ .
Und man kann dann die Gleichung so umschreiben: $\begin{eqnarray*} p=(2^q)^a-1^a \end{eqnarray*}$

Dann kann mit einem Satz aus der Vorlesung $\begin{eqnarray*} x^{n+1}-y^{n+1}=(x-y)*\sum\limits_{j=0}^n x^{n-j}*y^j \end{eqnarray*}$
als Summe so aufschreiben:
$\begin{eqnarray*} (2-1)\sum\limits_{k=0}^{a-1} (2^q)^{a-1-j}*a^{a-1} \end{eqnarray*}$
Nun zieht man eine 2 aus der Summe raus und begründet,
dass 2 kein Teiler von p sein kann (wegen Primzahl etc.)

Alles klar soweit,

Meine Ideen:
Aber ich frage mich, ob der Schrit mit $\begin{eqnarray*} r=q*a \end{eqnarray*}$ nicht overkill ist???
Kann man denn nicht einfach sagen r sei keine Primzahl und dann mit $\begin{eqnarray*} p=2^r-1^r \end{eqnarray*}$
den Satz aus der Vorlesung arbeiten?

21.02.2012, 18:48

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von gästlicherGast
als Summe so aufschreiben:
$\begin{eqnarray*} (2-1)\sum\limits_{k=0}^{a-1} (2^q)^{a-1-j}*a^{a-1} \end{eqnarray*}$

Wohl etwas zu hastig von der Tafel abgeschrieben? Das strotzt ja nur so vor Fehlern. unglücklich

Richtig wäre

$\begin{eqnarray*} (2^q)^a-1 = (2^q-1)\sum\limits_{k=0}^{a-1} (2^q)^{a-1-j} \cdot 1^{a-1} \end{eqnarray*}$ ,

d.h. also $\begin{eqnarray*} x=2^q,y=1,n=a-1 \end{eqnarray*}$ in deine Formel eingesetzt.

21.02.2012, 18:58

marioschluse

Auf diesen Beitrag antworten »

Oh, ne da hab ich bei dem Formeleditor etwas gepennt XD

Aber, das ändert sich ja auch nichts am ergebnis.
$\begin{eqnarray*} 2^q \end{eqnarray*}$ ist ja immmer noch ein vielfaches von 2,
und somit kann das kein Teiler von p sein. Also muss r=q*a eine Primzahl sein...

Aber hier nochmal was mich verwirrt. Vielleicht hast du das ja nicht gesehen:
Wieso kann man nicht einfach r gleich r lassen und mit der Formel arbeiten?

21.02.2012, 19:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von marioschluse
Oh, ne da hab ich bei dem Formeleditor etwas gepennt XD

Aber, das ändert sich ja auch nichts am ergebnis.
$\begin{eqnarray*} 2^q \end{eqnarray*}$ ist ja immmer noch ein vielfaches von 2,
und somit kann das kein Teiler von p sein. Also muss r=q*a eine Primzahl sein...

Was erzählst du denn da für einen Unsinn? Augenzwinkern

Die Argumentation läuft so: Aufgrund des obigen

$\begin{eqnarray*} (2^q)^a-1 = (2^q-1)\sum\limits_{k=0}^{a-1} (2^q)^{a-1-j} \end{eqnarray*}$

mit $\begin{eqnarray*} 1<q<r \end{eqnarray*}$ ist $\begin{eqnarray*} (2^q-1)>1 \end{eqnarray*}$ ein echter Teiler von $\begin{eqnarray*} (2^r-1) \end{eqnarray*}$ , und somit kann $\begin{eqnarray*} (2^r-1) \end{eqnarray*}$ keine Primzahl sein.

21.02.2012, 21:11

marioschluse

Auf diesen Beitrag antworten »

Ok, danke.

Aber ist es nicht einfacher zu sagen,
P= 2 * einer Summe keine Primzahl sein kann?
(Die zwei vor der Summe bekommt man, wen man einfach eine 2 aus der Summe rauszieht (natürlich muss man dann den exponenten etwas verändern.)

Hm, leider ist meine Frage, ob man nicht einfach r als r lassen kann, beantwortet...

Trotzdem danke für deine Antwort

22.02.2012, 15:28

Cacul

Auf diesen Beitrag antworten »

Zitat:

Original von marioschluse

Hm, leider ist meine Frage, ob man nicht einfach r als r lassen kann, beantwortet...

Trotzdem danke für deine Antwort

Nein r muss Primzahl sein, für $\begin{eqnarray*} r = 2k \Rightarrow (2^k-1) (2^k+1) \end{eqnarray*}$
ist die Zahl ja teilbar.

Für ungerade $\begin{eqnarray*} r= pq \end{eqnarray*}$ , gilt ja, $\begin{eqnarray*} p+q = r \end{eqnarray*}$ also vorsicht!
Nun aber solltest du zeigen können warum r Primzahl sein muss!

22.02.2012, 16:29

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Cacul
Nein r muss Primzahl sein, für $\begin{eqnarray*} r = 2k \Rightarrow (2^k-1) (2^k+1) \end{eqnarray*}$
ist die Zahl ja teilbar.

Fehlt da irgendetwas? verwirrt

Das auf der rechten Seite ist keine Aussage, insofern macht der Folgerungspfeil da keinen Sinn.

Zitat:

Original von Cacul
Für ungerade $\begin{eqnarray*} r= pq \end{eqnarray*}$ , gilt ja, $\begin{eqnarray*} p+q = r \end{eqnarray*}$ also vorsicht!

Es kann im Allgemeinen nicht gleichzeitig $\begin{eqnarray*} r= pq \end{eqnarray*}$ und $\begin{eqnarray*} p+q = r \end{eqnarray*}$ gelten verwirrt

Zitat:

Original von Cacul
Nun aber solltest du zeigen können warum r Primzahl sein muss!

Falls du, wie in deinem vorangegangenen Satz, $\begin{eqnarray*} r= pq \end{eqnarray*}$ wählst, so ist r ja eben keine Primzahl, falls $\begin{eqnarray*} p,q>1 \end{eqnarray*}$

Neue Frage »

Antworten »

Aufgabe zu Primzahlen

Verwandte Themen