fast MersenneProblem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| 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 !
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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 !
|
|
|
|
