Primzahlen Primteiler < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:18 Do 11.12.2014 | | Autor: | capri |
| Aufgabe | Für eine Primzahl n sei [mm] 2^n-1 [/mm] zusammengesetzt. Zeige: Für alle Primteiler
p gilt p [mm] \equiv [/mm] 1 (mod n)
Bemerkung:
Dies sieht man schön am Minimalbeispiel $ [mm] 2^1^1-1 [/mm] = 23 * 89 $ |
Guten Abend,
kann mir jemand hier einen Ansatz geben, sodass ich weiter machen kann.
Mir fehlt leider gerade nichts ein.
MfG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:32 Do 11.12.2014 | | Autor: | abakus |
> Für eine Primzahl n sei [mm]2^n-1[/mm] zusammengesetzt. Zeige: Für
> alle Primteiler
> p gilt p [mm]\equiv[/mm] 1 (mod n)
> Bemerkung:
> Dies sieht man schön am Minimalbeispiel [mm]2^1^1-1 = 23 * 89[/mm]
>
> Guten Abend,
>
> kann mir jemand hier einen Ansatz geben, sodass ich weiter
> machen kann.
> Mir fehlt leider gerade nichts ein.
>
>
> MfG
Hallo,
ich habe leider keine Ahnung.
Mir fällt nur auf, dass 23 der Nachfolger von 2*11 und 89 der Nachfolger eines Vielfachen von 2*11 ist.
Findest du nach dem Minimalbeispiel noch weitere Beispiele und spiegelt sich dort ein ähnlicher Zusammenhang wider?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:04 Do 11.12.2014 | | Autor: | capri |
Hallo nochmal,
um die Uhrzeit noch so ironisch? ^^
Aufjedenfall mit bisschen rechnen habe ich eins gefunden was so ähnlich ist.
$ [mm] 2^1^5-1 [/mm] $
habe ausversehen schon auf senden gedrückt -.-
$ [mm] 2^1^5-1 [/mm] $ = 32767
$ 32767 = 31 * 1057 $
mir fällt es nun schwer es für alle zu zeigen. Ich weiß nicht wie ich anfangen soll es zu formulieren.
LG
|
|
|
| |
|
Hallo nochmal,
> um die Uhrzeit noch so ironisch? ^^
Ich glaube gar nicht, dass abakus das ironisch gemeint hat.
> Aufjedenfall mit bisschen rechnen habe ich eins gefunden
> was so ähnlich ist.
>
> [mm]2^1^5-1[/mm]
>
> habe ausversehen schon auf senden gedrückt -.-
>
>
> [mm]2^1^5-1[/mm] = 32767
>
> [mm]32767 = 31 * 1057[/mm]
>
> mir fällt es nun schwer es für alle zu zeigen. Ich weiß
> nicht wie ich anfangen soll es zu formulieren.
Ich denke nicht, dass man das für alle zeigen kann. Klar ist allerdings, dass wenn [mm] $p\equiv 1\bmod{n}$ [/mm] und $n>2$ ist, $p=k*2n+1$ mit [mm] k\in\IN [/mm] sein muss, sonst kann $p$ ja nicht prim sein.
Diese Beobachtung darf hier noch als eher trivial gelten.
Ob allerdings $2n+1$ selbst immer ein Teiler von [mm] 2^n-1 [/mm] ist, wenn dieses zusammengesetzt ist, möchte ich bezweifeln. Ich such mal nach einem Gegenbeispiel.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:34 Sa 13.12.2014 | | Autor: | reverend |
Hi,
da muss man nicht sehr weit suchen:
[mm] 2^{29}-1=233*1103*2089
[/mm]
Im übrigen möchte ich noch darauf hinweisen, dass [mm] 2^{15}-1=31*1057 [/mm] zwei Probleme hat: zum einen ist 15 nicht prim und das Beispiel daher nutzlos, zum andern ist die vollständige Faktorisierung: [mm] 2^{15}-1=32767=7*31*151.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Do 11.12.2014 | | Autor: | hippias |
Der kleine Satz von Fermat liefert Dir alles, was Du brauchst. Mache Dir vielleicht zuerst klar, dass ueberhaupt [mm] $2^{n}-1=1$ [/mm] mod $n$ gilt; denn das ist doch das wenigste, was man erwarten kann, wenn die Behauptung stimmt.
Fuer die eigentliche Behauptung ist es interessanterweise praktisch Modulo $p$ zu rechnen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:57 Sa 13.12.2014 | | Autor: | capri |
Hallo,
dass $ [mm] 2^n-1= [/mm] 1 $ mod n gilt,
ist mir klar.
Aber ich komme damit nicht weiter.
Habe mir den Satz von Fermat zwar angeguckt,
aber auf meine Behauptung komme ich darauf leider nicht.
LG
|
|
|
| |
|
Hallo capri,
Na, ein paar Schritte mehr sind hier schon zu denken.
> dass [mm]2^n-1= 1[/mm] mod n gilt,
>
> ist mir klar.
>
> Aber ich komme damit nicht weiter.
> Habe mir den Satz von Fermat zwar angeguckt,
> aber auf meine Behauptung komme ich darauf leider nicht.
Der heißt doch: Für [mm] n\in\IP [/mm] ist [mm] 2^{n-1}\equiv 1\bmod{n}. [/mm] Nur ist das hier nicht die interessante Herangehensweise. Hippias hatte doch den Tipp gegeben, das ganze [mm] $\bmod{p}$ [/mm] zu betrachten.
[mm] 2^n-1 [/mm] soll zusammengesetzt sein. Für jeden Teiler $p$ gilt dann:
[mm] 2^n-1\equiv 0\bmod{p}\;\;\gdw\;\; 2^n\equiv 1\bmod{p}
[/mm]
Nun wissen wir, ebenfalls mit dem "kleinen Fermat"
[mm] 2^{p-1}\equiv 1\bmod{p}
[/mm]
[mm] \Rightarrow\;2^n\equiv 2^{p-1}\bmod{p}
[/mm]
Da $n$ prim ist, kannst Du nun etwas über den Zusammenhang von $p$ und $n$ folgern.
Grüße
reverend
PS: Du solltest den Tipps hier mehr Vertrauen schenken. Der von hippias war vollkommen richtig und zielführend.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:42 So 14.12.2014 | | Autor: | capri |
Vielen Dank reverend,
habe mir die Umformungen angeschaut und zurzeit alles verstanden,
außer was du meintest mit dem Zusammenhang von p und n, da habe ich mir gestern einige gedanken dazu gemacht, aber hab nichts gefunden.
LG
|
|
|
| |
|
Hallo,
> habe mir die Umformungen angeschaut und zurzeit alles
> verstanden,
>
> außer was du meintest mit dem Zusammenhang von p und n, da
> habe ich mir gestern einige gedanken dazu gemacht, aber hab
> nichts gefunden.
Ich glaube auch nicht, dass man da etwas finden kann.
Man kann allerdings folgern, dass [mm] \ggT(n,p-1)>1 [/mm] ist, woraus mit n prim weiter folgt: [mm] n|(p-1)\gdw p\equiv 1\bmod{n}.
[/mm]
Überleg Dir diese beiden Schritte mal genau.
Grüße
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:02 So 14.12.2014 | | Autor: | capri |
Okay danke nochmal,
nachdem Frühstück schaue ich es mir mal an. :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:28 Mo 15.12.2014 | | Autor: | reverend |
Hach, Neid...
Ich möchte auch mal wieder sooo lange frühstücken. 
Heute (Montag) bin ich fast gar nicht im Forum, sondern unterwegs. Aber natürlich gibt es mehr Leute, die hier Deine Fragen beantworten können, wenn Du dazu noch welche hast. Also nur zu!
Grüße
rev
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:35 Mo 15.12.2014 | | Autor: | Teufel |
Hi!
Als kleine Anmerkung noch: Da auch trivialerweise [mm] $p\equiv [/mm] 1 [mm] \mod{2}$ [/mm] gilt, folgt sogar [mm] $p\equiv [/mm] 1 [mm] \mod{2n}$ [/mm] falls [mm] $2^n-1$ [/mm] zusammengesetzt ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:54 Mo 15.12.2014 | | Autor: | reverend |
Teufel noch eins,
> Als kleine Anmerkung noch: Da auch trivialerweise [mm]p\equiv 1 \mod{2}[/mm]
> gilt, folgt sogar [mm]p\equiv 1 \mod{2n}[/mm] falls [mm]2^n-1[/mm]
> zusammengesetzt ist.
Das kommt mir irgendwie bekannt vor.
Hölle, Hölle, Hölle...
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:44 Mo 15.12.2014 | | Autor: | Teufel |
Ah, ich sehe! War wohl schon zu spät gestern. :)
n muss natürlich auch prim sein.
|
|
|
|
