...zusammengesetzte Primzahlen?? Ich bin so dumm.

Hallo Leute! Ich bin ein Mathedepp und brauchte ein bisserl Hilfe.

auf

http://www.primzahlen.de/index.htm

bin ich auf den folgenden Gedankengang gestossen und ich schnall ihn einfach nicht.

2.1 Mersennesche Primzahlen:

Dies sind Primzahl der Form: Primzahl Pm= 2^p-1
Bis ins Mittelalter glaubte man, daß für jede Primzahl p die Zahl = 2^p-1 wieder prim ist.
Man beachte aber, daß 2^r-1 für eine zusammengesetzte Zahl r=st wegen:

2^r-1=(2s-1)(2^(t-1)s+2(t-2)s +...+2^s+1)

nicht prim ist.

Mein Problem ist:
Wenn r eine Primzahl ist, wie soll sie dann aus r=st zusammengesetzt sein? Mann kann sie ja weder durch s oder t teilen, oder 'r' musste dann folglich doch keine Primzahl sein.

volkard

hä?
deien frage hat gar nix mit dem text zu tun.

probieren wir's mal anschaulich.

ich will mir mal die tollen zahlen 2^n-1 anschauen, also 1,3,7,15,31,63,127,...

2^2-1 (==3) könnte prim sein.
2^3-1 (==7) könnte prim sein.
2^5-1 (==31) könnte prim sein.
2^7-1 (==127) könnte prim sein.

und jetzt werde ich kurz mittelalterlich und glaube, daß alle 2^n-1 primzahlen sind, wenn n prim ist.
bei n==2,3,5,7 hat's ja geklappt.

und für die anderen zahlen hätte ich gerne einen grund. ich fange mal bei n==8 an. warum ist 2^8-1 nicht prim? nach dem dritten binomischen lehrsatz ist 2^8-1==(24-1)(2^4+1) oder 255==15*17 (,weil 256==16*16). hmm, (a+1)(a-1)==a^2-1. also imer, wenn 2^n-1 eine um 1 verminderte quadratzahl ist, klappt das. und das ist immer der fall, wenn n gerade ist.

ok, das war ein riesenschritt. der bringt uns echt weiter. und jetzt lassen wir uns ein argument dafür einfallen, daß immer, wenn n durch 3 teilbar ist, daß dann 2^n-1 keine primzahl sein kann.

wenn r=s*t
2^r-1=(2s-1)(2^(t-1)s+2(t-2)s +...+2^s+1)
steht in deiner klugen formel.

also für t==3
2^r-1==(2s-1) (4*s+2*s+2^s+1)
mal r==15 testen
2^15-1 == (2^5-1) * (4*5+2*5+2^5+1) == 31 * 62 == 1922

naja, die formel ist kaputt. aber generell sollte es funktionieren, so einen beweis aufzuziehen, daß 2^n-1 nicht prim sein kann, wenn n nicht prim ist.

dEUs

Hm volkard,

ich hab den Text auch so verstanden wie maciej64:
Man glaubte (2^p)-1 ist immer prim, wenn p auch prim ist. Und dann wird ein Gegenbeweis aufgeführt, dass das nicht immer stimmt. In diesem Gegenbeweis wird aber für p KEINE Primzahl verwendet. Deswegen hat der Gegenbeweis doch garnichts mit der urpsrünglichen Aufgabe zu tun.
Ich habe mir das auch mal bei Wikipedia angeschaut, dort steht das selbe:

Es gibt eine Reihe von bekannten Eigenschaften der Mersenne-Primzahlen. Um etwa zu untersuchen, ob eine große Zahl eine Primzahl ist, ist die wichtigste wohl die folgende:

Wenn Mp eine Primzahl ist, dann muss auch p eine Primzahl sein.
Diese Eigenschaft spielt eine wichtige Rolle bei der Suche nach Mersenne-Primzahlen, da man nur noch sehr wenige Kandidaten (nämlich die bei denen p eine Primzahl ist) testen muss.

Beispiel: Die Zahl M10 kann keine Primzahl sein, da 10 keine Primzahl ist. (In der Tat ist M10 = 2^10-1 = 1023 = 3·11·31.)

Oftmals wird diese Eigenschaft mit deren Umkehrung (wenn p eine Primzahl ist, dann ist auch Mp eine Primzahl) verwechselt. Da macht man aber einen Denkfehler, da z. B. 11 eine Primzahl ist, nicht aber M11 = 2^11-1 = 2047 = 23·89.

Der Beweis der oben genannten Eigenschaft ergibt sich folgendermaßen: Wenn p=rs zusammengesetzt ist, dann gilt:

2^rs-1 = (2^r - 1) (2^r(s-1) + 2^r(s-2) + ... + 2^r + 1)
und damit ist ein nichttrivialer Faktor von Mp gefunden.

D.h. Sie verwenden im Beispiel für p wieder eine Primzahl (11), sagen aber dann drunter, für p=r*s ...

Hi dEUs

dEUs schrieb:

Oftmals wird diese Eigenschaft mit deren Umkehrung (wenn p eine Primzahl ist, dann ist auch Mp eine Primzahl) verwechselt. Da macht man aber einen Denkfehler, da z. B. 11 eine Primzahl ist, nicht aber M11 = 2^11-1 = 2047 = 23·89.

Der Beweis bezieht sich aber auf

dEUs schrieb:

Wenn Mp eine Primzahl ist, dann muss auch p eine Primzahl sein.
Beispiel: Die Zahl M10 kann keine Primzahl sein, da 10 keine Primzahl ist. (In der Tat ist M10 = 2^10-1 = 1023 = 3·11·31.)

Jockel

volkard schrieb:

aber generell sollte es funktionieren, so einen beweis aufzuziehen, daß 2^n-1 nicht prim sein kann, wenn n nicht prim ist.

Steht doch oben:

Man beachte aber, daß 2^r-1 für eine zusammengesetzte Zahl r=st wegen:

2^r-1=(2s-1)(2^(t-1)s+2(t-2)s +...+2^s+1)

dEUs

Nein. Der Beweis bezieht sich auf M11!
Sonst wäre er sinnlos, weil man ja sowieso schon angenommen hat, dass es nur gilt, wenn p eine Primzahl ist. Für p=11 (prim!) ist Mp aber trotzdem keine Primzahl, und das soll der Beweis darunter verdeutlichen. Allerdings blicken wir ihn nicht.

Oder ist der Text einfach nur scheisse strukturiert?

dEUs schrieb:

Oder ist der Text einfach nur scheisse strukturiert?

Ja ist er. Trotzdem wird da bewiesen:

p nicht prim => Mp nicht prim.

Jockel

dEUs

Ja, wenn ich das so gesehen hätte, wär mir auch sofort klar gewesen, dass da bewiesen wird, wieso Mr keine Primzahl ist, wenn r keine ist. Nur hat mich dieses "Vorspiel" von wegen Mp muss nicht immer prim sein, wenn p prim ist, ganz gehörig verwirrt.

Ich weiss, "Vorspiel" ist halt scheisse