Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

ggT von zwei Mersenne-Zahlen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> ggT von zwei Mersenne-Zahlen
 
Autor Nachricht
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 12 Feb 2009 - 19:21:19    Titel: ggT von zwei Mersenne-Zahlen

Hi,

die Aufgabe lautet: Zeigen Sie, dass für zwei voneinander verschiedene Primzahlen p und q die Zahlen 2^p - 1 und 2^q - 1 teilerfremd sind, ihr ggT also 1 ist.

Ich habe versucht, einen indirekten Beweis zu führen, also angenommen, 2^p - 1 und 2^q - 1 hätten einen gemeinsamen Teiler a ≠ 1.

--> 2^p - 1 ≡ 0 mod a und 2^q - 1 ≡ 0 mod a
--> 2^p ≡ 1 mod a und 2^q ≡ 1 mod a
--> 2^p ≡ 2^q mod a
--> 2^p - 2^q ≡ 0 mod a
--> 2^q (2^(p-q) - 1) ≡ 0 mod a

Da a nicht 2^q teilt, muss 2^(p-q) - 1 ≡ 0 mod a sein, also 2^(p-q) ≡ 1 mod a.

Ist das nun schon ein Widerspruch? Ich bin mir nicht ganz sicher...
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 12 Feb 2009 - 20:54:38    Titel:

Noch ist da kein Widerspruch zu erkennen...

Allerdings schau dir mal den Euklidischen Algorithmus an, und wende ihn auf deine Zahlen an. Hier hast du gerade einen Schritt dafür ausgeführt, das geht aber noch weiter.


Cyrix
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 12 Feb 2009 - 21:14:36    Titel:

Okay:

Sei p > q, also p = k*q + r

Einmal Division mit Rest durchgeführt:
2^p - 1 : (2^q - 1) = 2^(p-q) + 2^(p-2q) + 2^(p-3q) + ... + 2^(p-kq) + 2^r / (2^q - 1)

--> 2^p - 1 = (2^q - 1)*(2^(p-q) + 2^(p-2q) + ... + 2^r) + 2^r

Sei q = m*r + s
Noch einmal Division mit Rest:
2^q - 1 : 2^r = 2^(q-r)
-(2^q)
---------
-1

--> 2^q - 1 = 2^r * 2^(q-r) - 1

--> ggT(2^p - 1, 2^q - 1) = 1

Etwas konfus aufgeschrieben, aber im Prinzip doch richtig, oder?
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 12 Feb 2009 - 22:35:58    Titel:

Der Rest bei der ersten Division ist nicht 2^r, sondern 2^r-1.

Cyrix
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 15 Feb 2009 - 12:45:35    Titel:

Okay, danke, die Aufgabe habe ich inzwischen geknackt. Als Teil b) ist nun zu zeigen, dass für p ≥ 3 jeder Primteiler von 2^p - 1 die Form 2kp + 1 (k € N) hat.

Sei q ein Primteiler von 2^p - 1, dann gilt 2^p - 1 ≡ 0 mod q, also 2^p ≡ 1 mod q. Nach Fermat-Euler gilt aber auch 2^(q-1) ≡ 1 mod q, also gibt es zwei Möglichkeiten:

1. p ist Vielfaches von q-1
--> geht nicht, da dann, weil p prim ist, schon p = q-1 gelten müsste; da q-1 aber gerade ist, müsste schon p = 2 sein, was der Voraussetzung p ≥ 3 widerspricht.

2. q-1 ist Vielfaches von p
--> q-1 = k*p (k € N)
--> q = k*p + 1

Jetzt wäre ich eigentlich fertig, aber woher kommt der Faktor 2 vor dem k*p? Ich habe den Verdacht, dass man statt k eigentlich 2m schreiben müsste, denn q-1 ist ja gerade, und wenn man k ungerade wählt (p ist als Primzahl ja ohnehin ungerade), könnte man q-1 nicht erzeugen.
Passt das ungefähr?
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 15 Feb 2009 - 12:46:35    Titel:

Okay, danke, die Aufgabe habe ich inzwischen geknackt. Als Teil b) ist nun zu zeigen, dass für p ≥ 3 jeder Primteiler von 2^p - 1 die Form 2kp + 1 (k € N) hat.

Sei q ein Primteiler von 2^p - 1, dann gilt 2^p - 1 ≡ 0 mod q, also 2^p ≡ 1 mod q. Nach Fermat-Euler gilt aber auch 2^(q-1) ≡ 1 mod q, also gibt es zwei Möglichkeiten:

1. p ist Vielfaches von q-1
--> geht nicht, da dann, weil p prim ist, schon p = q-1 gelten müsste; da q-1 aber gerade ist, müsste schon p = 2 sein, was der Voraussetzung p ≥ 3 widerspricht.

2. q-1 ist Vielfaches von p
--> q-1 = k*p (k € N)
--> q = k*p + 1

Jetzt wäre ich eigentlich fertig, aber woher kommt der Faktor 2 vor dem k*p? Ich habe den Verdacht, dass man statt k eigentlich 2m schreiben müsste, denn q-1 ist ja gerade, und wenn man k ungerade wählt (p ist als Primzahl ja ohnehin ungerade), könnte man q-1 nicht erzeugen.
Passt das ungefähr?

Edit: Sorry für den Doppelpost, das Forum spinnt mal wieder...
cyrix42
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 14.08.2006
Beiträge: 24252

BeitragVerfasst am: 15 Feb 2009 - 12:54:12    Titel:

Jo, passt. Die 2 ist nur dafür da, dass der Primteiler ungerade ist.

Cyrix
Tiamat
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 25.01.2008
Beiträge: 2092
Wohnort: Aurich

BeitragVerfasst am: 15 Feb 2009 - 13:08:04    Titel:

Spitze! Very Happy
Dann hab ich hier nochmal so eine ähnliche. Zu zeigen ist, dass aus 2^(2^n) ≡ - 1 mod p schon folgt, dass p = k*2^(n+2) + 1 ist. (k und n sind natürliche Zahlen).
Als Tipp wurde gegeben, zu untersuchen, ob 2 quadratischer Rest mod p ist.

Ich habe mir jetzt gedacht, dass nach dem Eulerkriterium ja gilt:
2^((p-1)/2) ≡ (2/p) ≡ -1 mod p, also überlege ich mir, für welche p das Legendresymbol (2/p) = -1 wird --> p ≡ +/-3 mod 8

Dann müsste aber auch (p-1)/2 = 2^n sein - wie bekomme ich das mit p ≡ +/-3 mod 8 unter einen Hut...?
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> ggT von zwei Mersenne-Zahlen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum