www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - fast MersenneProblem
fast MersenneProblem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

fast MersenneProblem: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:49 Fr 02.11.2007
Autor: BobBoraxo

Aufgabe
sei m element N. Ist [mm] (2^m)+1 [/mm] Primzahl, so ist [mm] m=2^n [/mm] mit n element N.

Ich hab mir da schon den Wolf gerechnet und im Endeffekt nicht mal nen Ansatz, kann mir vielleicht irgendjemand nen Tipp geben wie ich daran gehen könnte?
ich hab grade etwas ähnliches für [mm] (2^n)-1 [/mm] bewiesen. aber da soll n prim sein und es ist wesentlich einfacher, weil ich annehmen kann das n nicht prim ist und alles läuft...
aber hier tu ich mich schwer !

        
Bezug
fast MersenneProblem: Antwort
Status: (Antwort) fertig Status 
Datum: 09:51 Sa 03.11.2007
Autor: felixf

Hallo!

> sei m element N. Ist [mm](2^m)+1[/mm] Primzahl, so ist [mm]m=2^n[/mm] mit n
> element N.
>
>  Ich hab mir da schon den Wolf gerechnet und im Endeffekt
> nicht mal nen Ansatz, kann mir vielleicht irgendjemand nen
> Tipp geben wie ich daran gehen könnte?

Wenn $p$ eine Primzahl ist, dann gilt ja [mm] $2^{p-1} \equiv [/mm] 1 [mm] \pmod{p}$. [/mm] Rechne das doch mal fuer $p = [mm] 2^m [/mm] + 1$ aus, wobei du den Exponent $p-1$ schreibst als $k m + [mm] \ell$ [/mm] mit $0 [mm] \le \ell [/mm] < m$.

Du bekommst dann eine Bedingung an [mm] $\ell$ [/mm] heraus (naemlich dass es nur genau einen Wert haben kann), und das wiederum sagt dir etwas ueber $m$ aus.

LG Felix


Bezug
                
Bezug
fast MersenneProblem: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 19:41 Sa 03.11.2007
Autor: BobBoraxo

hmm... ich bin mir nicht wirklich sicher ob es nun stimmt, wär nett wenn du dir das nochmal anschaust.

Sei p:= [mm] (2^m)+1 [/mm] prim z.z. => [mm] m=2^n [/mm]

da p prim
=> [mm] 2^p-1 \equiv [/mm] 1 (mod p)    mit p-1:= k*m+l 0 [mm] \le [/mm] l < m
<=> 2^(k*m+l) - 1 [mm] \equiv [/mm] 0 (mod p)

=> [mm] p-1=2^m+1-1=2^m=k*m+l [/mm] => l=0 und [mm] m=2^n [/mm]

wenn ich ehrlich bin Blick ich es grade nicht... irgendwie seh ich den Wald wahrscheinlich vor lauter Bäumen nicht

Bezug
                        
Bezug
fast MersenneProblem: Antwort
Status: (Antwort) fertig Status 
Datum: 23:16 Sa 03.11.2007
Autor: felixf

Hallo

> hmm... ich bin mir nicht wirklich sicher ob es nun stimmt,
> wär nett wenn du dir das nochmal anschaust.
>  
> Sei p:= [mm](2^m)+1[/mm] prim z.z. => [mm]m=2^n[/mm]
>  
> da p prim
> => [mm]2^p-1 \equiv[/mm] 1 (mod p)

Du meinst: [mm] $2^p \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] oder [mm] $2^p [/mm] - 1 [mm] \equiv [/mm] 0 [mm] \pmod{p}$. [/mm]

>    mit p-1:= k*m+l 0 [mm]\le[/mm] l < m
>  <=> 2^(k*m+l) - 1 [mm]\equiv[/mm] 0 (mod p)

>  
> => [mm]p-1=2^m+1-1=2^m=k*m+l[/mm] => l=0 und [mm]m=2^n[/mm]

Wie kommst du auf die letzte Implikation?!

Du hast [mm] $(2^m)^k \cdot 2^l [/mm] = [mm] 2^{k m + l} \equiv [/mm] 1 [mm] \pmod{p}$, [/mm] und du weisst (per Definition von $p$), dass [mm] $2^m \equiv [/mm] -1 [mm] \pmod{p}$ [/mm] ist. Also was ist [mm] $(2^m)^k \cdot 2^l$ [/mm] modulo $p$? Und wann ist das gleich 1?

LG Felix


Bezug
                                
Bezug
fast MersenneProblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:53 Mo 05.11.2007
Autor: BobBoraxo

Okay Danke erst einmal für all die Tipps die du mir gegeben hast, sonst wär ich glaub ich noch am Anfang.
Ich hab mich aber nochmal schlau gemacht... Mathe macht zwar unglaublich Spass, aber manchmal zweifel ich an meinem Verständnis.
Also:
z.z. [mm] 2^k+1 [/mm] prim => [mm] k=2^n [/mm]

Angenommen [mm] k=(2^n)+l [/mm] mit l>0 und l ungerade

dann ist [mm] (2^k)+1 [/mm] = [mm] (2^{2^n})^l [/mm] +1

Ich weiß jetzt : [mm] x+1|x^l+1 [/mm]

=> [mm] (2^{2^n})+1|(2^k)+1 [/mm]

=> [mm] k=2^n [/mm]

es ist glaub ich etwas anders als den Weg den du genommen hast, da ich nicht modulo gerechnet habe, aber wäre das möglich...
das Problem ist nur, dass ich hierbei auch nicht bewiesen habe, dass [mm] x+1|x^l+1 [/mm] für ungerade l

Bezug
                                        
Bezug
fast MersenneProblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:05 Di 06.11.2007
Autor: felixf

Hallo

> Okay Danke erst einmal für all die Tipps die du mir gegeben
> hast, sonst wär ich glaub ich noch am Anfang.
>  Ich hab mich aber nochmal schlau gemacht... Mathe macht
> zwar unglaublich Spass, aber manchmal zweifel ich an meinem
> Verständnis.
>  Also:
>  z.z. [mm]2^k+1[/mm] prim => [mm]k=2^n[/mm]

>  
> Angenommen [mm]k=(2^n)+l[/mm] mit l>0 und l ungerade

Also z.B. $k = 6$ kannst du nicht in dieser Form schreiben. Aber vielleicht meinst du auch $k = [mm] 2^n \cdot [/mm] l$ mit $l$ ungerade?

> dann ist [mm](2^k)+1[/mm] = [mm](2^{2^n})^l[/mm] +1

Das gilt naemlich nur, wenn $k = [mm] 2^n \cdot [/mm] l$ ist, und nicht wenn $k = [mm] 2^n [/mm] + l$ ist.

> Ich weiß jetzt : [mm]x+1|x^l+1[/mm]

Das gilt nicht: Setze $x = 2$, $l = 2$, dann ist $x + 1 = 3$ und [mm] $x^l [/mm] + 1 = 5$, und 3 teilt sicher nicht 5.

> => [mm](2^{2^n})+1|(2^k)+1[/mm]
>  
> => [mm]k=2^n[/mm]

Wie kommst du jetzt hier drauf?

> es ist glaub ich etwas anders als den Weg den du genommen
> hast, da ich nicht modulo gerechnet habe, aber wäre das
> möglich...

So scheint's zumindest nicht zu gehen...

>  das Problem ist nur, dass ich hierbei auch nicht bewiesen
> habe, dass [mm]x+1|x^l+1[/mm] für ungerade l

Das gilt ja i.A. auch nicht (siehe oben)...

LG Felix


Bezug
                                                
Bezug
fast MersenneProblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:14 Di 06.11.2007
Autor: BobBoraxo


> Also z.B. [mm]k = 6[/mm] kannst du nicht in dieser Form schreiben.
> Aber vielleicht meinst du auch [mm]k = 2^n \cdot l[/mm] mit [mm]l[/mm]
> ungerade?

richtig, da habe ich mich vertan, sorry !


> > Ich weiß jetzt : [mm]x+1|x^l+1[/mm]
>  
> Das gilt nicht: Setze [mm]x = 2[/mm], [mm]l = 2[/mm], dann ist [mm]x + 1 = 3[/mm] und
> [mm]x^l + 1 = 5[/mm], und 3 teilt sicher nicht 5.

dass hab ich ja außgeschlossen, weil l ungerade . und da gehts

> > => [mm](2^{2^n})+1|(2^k)+1[/mm]
>  >  
> > => [mm]k=2^n[/mm]
>  
> Wie kommst du jetzt hier drauf?

naja, wenn [mm] (2^{2^n})+1|(2^k)+1 [/mm] dann muss [mm] (2^{2^n})+1=(2^k)+1 [/mm] sein, denn sonst wäre [mm] (2^k)+1 [/mm] nicht prim und deswegen muss [mm] k=2^n [/mm] sein.

> >  das Problem ist nur, dass ich hierbei auch nicht bewiesen

> > habe, dass [mm]x+1|x^l+1[/mm] für ungerade l
>
> Das gilt ja i.A. auch nicht (siehe oben)...

ich hab halt gelesen, dass das für l ungerade gilt und nach nen paar Polynomdivision war ich auch davon überzeugt nur nen beweis hab ich nicht.  



Bezug
                                                        
Bezug
fast MersenneProblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:21 Di 06.11.2007
Autor: felixf

Hallo

> > Also z.B. [mm]k = 6[/mm] kannst du nicht in dieser Form schreiben.
> > Aber vielleicht meinst du auch [mm]k = 2^n \cdot l[/mm] mit [mm]l[/mm]
> > ungerade?
>  
> richtig, da habe ich mich vertan, sorry !

Ok. Kein Problem :)

> > > Ich weiß jetzt : [mm]x+1|x^l+1[/mm]
>  >  
> > Das gilt nicht: Setze [mm]x = 2[/mm], [mm]l = 2[/mm], dann ist [mm]x + 1 = 3[/mm] und
> > [mm]x^l + 1 = 5[/mm], und 3 teilt sicher nicht 5.
>  
> dass hab ich ja außgeschlossen, weil l ungerade . und da
> gehts

Stimmt... Hab's verpennt :-)

>  > > => [mm](2^{2^n})+1|(2^k)+1[/mm]

>  >  >  
> > > => [mm]k=2^n[/mm]
>  >  
> > Wie kommst du jetzt hier drauf?
>  
> naja, wenn [mm](2^{2^n})+1|(2^k)+1[/mm] dann muss
> [mm](2^{2^n})+1=(2^k)+1[/mm] sein, denn sonst wäre [mm](2^k)+1[/mm] nicht
> prim und deswegen muss [mm]k=2^n[/mm] sein.

Ah stimmt, das war ja als prim vorausgesetzt... Das hatte ich schon wieder vergessen ;-) (Ich geh auch gleich ins Bett...)

> > >  das Problem ist nur, dass ich hierbei auch nicht bewiesen

> > > habe, dass [mm]x+1|x^l+1[/mm] für ungerade l
> >
> > Das gilt ja i.A. auch nicht (siehe oben)...
>  
> ich hab halt gelesen, dass das für l ungerade gilt und nach
> nen paar Polynomdivision war ich auch davon überzeugt nur
> nen beweis hab ich nicht.  

Hab grad kurz drueber nachgedacht, am einfachsten beweist man es per Induktion nach $k$, wenn man $l = 2 k + 1$ schreibt. Fuer $k = 0$ ist es klar, und fuer den Induktionsschritt schreibt man [mm] $x^{2 (k + 1) + 1}$ [/mm] als Vielfaches von [mm] $x^{2 k + 1}$ [/mm] plus etwas, was durch $x + 1$ teilbar ist (erhaelt man, imdem man Polynomdivision von [mm] $x^{2 (k + 1) + 1}$ [/mm] zwei Schritte durchfuehrt).

LG Felix


Bezug
                                                                
Bezug
fast MersenneProblem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 00:24 Di 06.11.2007
Autor: BobBoraxo

stimmt, dann ist ja alles klar, ich hab aber auch nochmal drüber nachgedacht und wenn mann [mm] x^p+1 [/mm] hat, mit p ungeraden, dann ist (-1) ja ne Nullstelle von [mm] x^p+1 [/mm] und deswegen kann mann (x+1) abspalten. aber Induktion is natürlich auch elegant. Vielen Dank für deine Hilfe !

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de