(mersennesche) primzahlen

12.09.2007, 19:58

Alexandra87

Auf diesen Beitrag antworten »

(mersennesche) primzahlen

hab mal wieder einen beweis:

Zeige: sind a, p natürliche zahlen $\begin{eqnarray*} \geq 2 \end{eqnarray*}$ , so ist $\begin{eqnarray*} a^p-1 \end{eqnarray*}$ höchstens dann eine Primzahl, wenn a=2 und p eine Primzahl ist.
(Primzahlen der Gestalt $\begin{eqnarray*} 2^p-1 \end{eqnarray*}$ nennt man Mersennesche Primzahlen)

zu meiner lösung:
wenn a eine ungerade zahl ist, ist $\begin{eqnarray*} a^p \end{eqnarray*}$ immer ungerade; $\begin{eqnarray*} a^p-1 \end{eqnarray*}$ ist somit gerade und daher keine primzahl.

doch wie kann ich zeigen, dass $\begin{eqnarray*} a^p-1 \end{eqnarray*}$ für gerade zahlen $\begin{eqnarray*} a \neq 2 \end{eqnarray*}$ keine Primzahl ist?

12.09.2007, 20:00

AD

Auf diesen Beitrag antworten »

Das hier ist der Schlüssel zum Beweis.

Du solltest deine Aufgaben also mal im Zusammenhang betrachten. Augenzwinkern

Augenzwinkern

12.09.2007, 20:06

Alexandra87

Auf diesen Beitrag antworten »

was?? wie?

das sind zwei völlig voneinander unabhängige aufgaben!!

wie soll ich denn die formel $\begin{eqnarray*} \sum_{k=0}^n~{a^kb^{n-k}} = \frac{a^{n+1}-b^{n+1}}{a-b} \end{eqnarray*}$ bei diesem Beweis anwenden?

12.09.2007, 20:07

Lazarus

Auf diesen Beitrag antworten »

Völlig verschieden ?
Setz mal $\begin{eqnarray*} n+1=p \end{eqnarray*}$ und $\begin{eqnarray*} b=1 \end{eqnarray*}$

12.09.2007, 20:08

tmo

Auf diesen Beitrag antworten »

mit diesem satz kannst du erstmal $\begin{eqnarray*} (a^p - 1) : (a-1) \end{eqnarray*}$ berechnen.

man sieht jetzt schon warum der beweis, dass $\begin{eqnarray*} a^p -1 \end{eqnarray*}$ dann zusammengesetzt ist, für a = 2 versagt Augenzwinkern

Augenzwinkern

12.09.2007, 20:21

Alexandra87

Auf diesen Beitrag antworten »

wenn ich $\begin{eqnarray*} (a^p - 1) : (a-1) \end{eqnarray*}$ über die summenformel berechne (mit p=n+1 und b=1), erhalte ich $\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k}=a^{p-1}\cdot(n+1) \end{eqnarray*}$

und wie mache ich dann weiter?

Anzeige

12.09.2007, 20:25

tmo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

bis dahin ist es noch richtig. jetzt schreibe die summe mal aus. also mit ganz "normalen" + zeichen und so.

12.09.2007, 20:27

Lazarus

Auf diesen Beitrag antworten »

Nanana!
$\begin{eqnarray*} \sum_{k=0}^{p-1}a^k\neq a^{p-1}(n+1) \end{eqnarray*}$
Das sit richtig:
$\begin{eqnarray*} \frac{a^p-1}{a-1}=\sum_{k=0}^{p-1}a^k \end{eqnarray*}$
Und das reicht ja schon, weil a^p-1 somit eine Zusammengesetzte Zahl ist, weil die Summe ja ganz ist.

12.09.2007, 20:29

tmo

Auf diesen Beitrag antworten »

hmm stimmt eigentlich, es ist gar nicht mehr nötig die summe noch auszuschreiben, denn die addition ist auf den ganzen zahlen ja eh abgeschlossen.

ist dir auch klar, warum der beweis für a = 2 versagt @ Alexandra?

12.09.2007, 20:30

Alexandra87

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k}=1+a+a^2+a^3+a^4+...+a^{p-1} \end{eqnarray*}$

so besser?

12.09.2007, 20:31

Alexandra87

Auf diesen Beitrag antworten »

Zitat:

Original von Lazarus
Und das reicht ja schon, weil a^p-1 somit eine Zusammengesetzte Zahl ist, weil die Summe ja ganz ist.

was meinst du damit?

12.09.2007, 20:32

tmo

Auf diesen Beitrag antworten »

deine letzte gleichung ist nun richtig.

jetzt multipliziere sie mal mit (a-1).

dann sollte dir etwas auffallen, was bei primzahlen nie der fall ist Augenzwinkern

Augenzwinkern

12.09.2007, 20:32

Lazarus

Auf diesen Beitrag antworten »

Die Summe besteht nur aus ganzen Zahlen, somit ist auch die Summe eine ganze Zahl. Damit ist a^p-1 eine Zusammengestze Zahl und nicht prim.

12.09.2007, 20:34

Alexandra87

Auf diesen Beitrag antworten »

zunächst mal, warum ist damit bewiesen, dass $\begin{eqnarray*} a^p-1 \end{eqnarray*}$ keine Primzahl ist für $\begin{eqnarray*} a \neq 2 \end{eqnarray*}$ ?

warum das bei 2 nicht stimmt ist mir auch nicht ganz klar (liegt wahrscheinlich daran, weil mir teil 1 noch nicht einleuchtend ist)

12.09.2007, 20:38

Alexandra87

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k}=1+a+a^2+a^3+a^4+...+a^{p-1} \end{eqnarray*}$

$\begin{eqnarray*} \cdot (a-1) \end{eqnarray*}$

$\begin{eqnarray*} ...=(a-1)+(a^2-a)+(a^3-a^2)+...+(a^p-1)=a^p-2 \end{eqnarray*}$ richtig?

12.09.2007, 20:39

Alexandra87

Auf diesen Beitrag antworten »

d.h. ich kann den beweis begründen mit a^p-1 lässt sich als summe darstellen und kann somit keine pz sein.
aber warum trifft das auf a=2 nicht zu?

12.09.2007, 20:41

Lazarus

Auf diesen Beitrag antworten »

Weil a-1, der Teiler von a^p-1 für a=2 gleich 1 ist.
Und eine Primzahl wird ja nur von 1 und sich selbt geteilt...

12.09.2007, 20:42

tmo

Auf diesen Beitrag antworten »

du denkst zu kompliziert.

$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

daraus folgt:

$\begin{eqnarray*} a^p - 1=(a-1) \cdot \sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

wenn a > 2 und ganzzahlig ist, dann sind beide faktoren auch ganzzahlig und > 1.

demnach lässt sich $\begin{eqnarray*} a^p -1 \end{eqnarray*}$ als produkt zweier ganzer zahlen darstellen und ist also nicht prim.

edit:
"ich kann den beweis begründen mit a^p-1 lässt sich als summe darstellen und kann somit keine pz sein."

7 ist eine primzahl und es gilt 7 = 3+4
das ist also keine begründung.

12.09.2007, 20:49

Alexandra87

Auf diesen Beitrag antworten »

Zitat:

du denkst zu kompliziert.

haben mir schon viele gesagt, muss wohl was dran sein. smile

smile

Zitat:

$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

daraus folgt:

$\begin{eqnarray*} a^p - 1=(a-1) \cdot \sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

ups, so einfach war das gemeint...

Zitat:

wenn a > 2 und ganzzahlig ist, dann sind beide faktoren auch ganzzahlig und > 1.

demnach lässt sich $\begin{eqnarray*} a^p -1 \end{eqnarray*}$ als produkt zweier ganzer zahlen darstellen und ist also nicht prim.

danke, jetzt hab ichs endgültig verstanden Wink

Wink

Zitat:

edit:
"ich kann den beweis begründen mit a^p-1 lässt sich als summe darstellen und kann somit keine pz sein."

7 ist eine primzahl und es gilt 7 = 3+4
das ist also keine begründung.

stimmt. der satz muss also abgeändert werden von summe zu produkt. ok, so der ähnlich Augenzwinkern

Augenzwinkern

12.09.2007, 20:52

Alexandra87

Auf diesen Beitrag antworten »

danke an euch beide. jetzt hab ich auch das mit der 2 verstanden! Wink

Wink

12.09.2007, 20:57

AD

Auf diesen Beitrag antworten »

Aber auch für $\begin{eqnarray*} a=2 \end{eqnarray*}$ und zusammengesetzte $\begin{eqnarray*} p \end{eqnarray*}$ , also $\begin{eqnarray*} p=rs \end{eqnarray*}$ mit $\begin{eqnarray*} r>1,s>1 \end{eqnarray*}$ hilft der genannte Quotient in der Form

$\begin{eqnarray*} \frac{2^p-1}{2^r-1} = \frac{2^{rs}-1}{2^r-1} = \frac{(2^r)^s-1}{2^r-1} = \cdots \end{eqnarray*}$ .

12.09.2007, 21:47

joeehhii

Auf diesen Beitrag antworten »

Um mich mal verständishalber einzumischen:
Ich verstehe bis zum folgendem Punkt alles.

Zitat:

wenn a > 2 und ganzzahlig ist, dann sind beide faktoren auch ganzzahlig und > 1.
demnach lässt sich $\begin{eqnarray*} a^p -1 \end{eqnarray*}$ als produkt zweier ganzer zahlen darstellen und ist also nicht prim.

Die Begründung verstehe ich nicht ganz. Wer/was sind die beiden Faktoren?

12.09.2007, 21:58

therisen

Auf diesen Beitrag antworten »

$\begin{eqnarray*} a-1>1 \end{eqnarray*}$ ist ein Faktor und der "Rest" $\begin{eqnarray*} q\in\mathbb Z \end{eqnarray*}$ , sodass $\begin{eqnarray*} a^p-1=(a-1)q \end{eqnarray*}$ .

12.09.2007, 22:00

joeehhii

Auf diesen Beitrag antworten »

Danke!

Freude

22.04.2008, 15:42

Sandra87

Auf diesen Beitrag antworten »

Hallo,
erstmal bin ich froh, dass es dieses Thema hier schon gibt. Mit der Summenformel hatte ich auch schon als Idee. Hab ich soweit auch alles verstanden, allerdings ist mir nur eine Sache noch nicht klar.
Ich hab somit gezeigt, dass nur für a=2 gilt, dass a^k - 1 Prim ist. Allerdings gilt dieses ja auch nur unter der Voraussetzung, dass k schon Prim ist, aber mir ist noch nicht klar, wie ich dieses nun zeige.
Wäre froh wenn mir da jemand helfen kann, auch wenn dieses Thema schon älter ist!
Liebe Grüße,
Sandra

22.04.2008, 15:50

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von Sandra87
Allerdings gilt dieses ja auch nur unter der Voraussetzung, dass k schon Prim ist, aber mir ist noch nicht klar, wie ich dieses nun zeige.

Das hat Arthur Dent doch schon geschrieben:

Zitat:

Original von Arthur Dent
Aber auch für $\begin{eqnarray*} a=2 \end{eqnarray*}$ und zusammengesetzte $\begin{eqnarray*} p \end{eqnarray*}$ , also $\begin{eqnarray*} p=rs \end{eqnarray*}$ mit $\begin{eqnarray*} r>1,s>1 \end{eqnarray*}$ hilft der genannte Quotient in der Form

$\begin{eqnarray*} \frac{2^p-1}{2^r-1} = \frac{2^{rs}-1}{2^r-1} = \frac{(2^r)^s-1}{2^r-1} = \cdots \end{eqnarray*}$ .

22.04.2008, 16:11

Sandra87

Auf diesen Beitrag antworten »

Mir ist nur erstma schon mal nicht klar, wie er auf diese Gleichung kommt, müsste das nicht so aussehen:
$\begin{eqnarray*} \frac{2^p-1}{2-1} = \frac{2^{rs}-1}{2-1} \end{eqnarray*}$
oder woher kommt das 2^r im Nenner?
und zu dem ist mir leider nicht klar, wie ich da weiter machen soll.

22.04.2008, 16:21

tmo

Auf diesen Beitrag antworten »

Er hat das $\begin{eqnarray*} 2^r \end{eqnarray*}$ im Nenner einfach hingeschrieben. Weil es halt so klappt.

Zitat:

Original von tmo
$\begin{eqnarray*} \frac{(a^p - 1)}{(a-1)}=\sum_{k=0}^{p-1}~{a^k} \end{eqnarray*}$

Wende diese Formel auf den Ansatz von Arthur Dent an.

22.04.2008, 16:35

Sandra87

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{((2^r)^s - 1)}{(2^r-1)}=\sum_{k=0}^{s-1}~{2^k} \end{eqnarray*}$
daraus folgt dann:
$\begin{eqnarray*} ((2^r)^s - 1)=(2^r-1) \sum_{k=0}^{s-1}~{2^k} \end{eqnarray*}$
[/quote]

Ist das so dann richtig? Und Danke für deine Hilfe Mit Zunge

Mit Zunge

22.04.2008, 16:37

tmo

Auf diesen Beitrag antworten »

Du hast doch $\begin{eqnarray*} a = 2^r \end{eqnarray*}$ gewählt. Also musst du überall (auch auf der rechten Seite) das a durch $\begin{eqnarray*} 2^r \end{eqnarray*}$ ersetzen.

22.04.2008, 16:40

Sandra87

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{((2^r)^s - 1)}{(2^r-1)}=\sum_{k=0}^{s-1}~{(2^r)^k} \end{eqnarray*}$
daraus folgt dann:
$\begin{eqnarray*} ((2^r)^s - 1)=(2^r-1) \sum_{k=0}^{s-1}~{(2^r)^k} \end{eqnarray*}$

Kleiner Flüchtigkeitsfehler Augenzwinkern

Augenzwinkern

Nun sollte es stimmen

22.04.2008, 16:41

tmo

Auf diesen Beitrag antworten »

Genau. Und jetzt kannst du folgern, dass die rechte Seite keine Primzahl ist.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »