Ungerade Primzahl, Vielfache < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:59 Sa 03.11.2012 | | Autor: | icarus89 |
| Aufgabe | | Sei p eine ungerade Primzahl. Zeigen Sie, dass p unendlich viele Zahlen der Form [mm] n*2^{n}+1 [/mm] teilt (mit [mm] n\in \IN) [/mm] |
Hallo!
Durch Probieren bin ich auf die Idee gekommen, dass für jedes p und jedes n p ein Teiler von [mm] (p^{n}-1)*2^{p^{n}-1}+1 [/mm] ist und hab auch noch kein Gegenbeispiel gefunden, da diese Zahlen ja auch sehr schnell zu groß werden, um sie noch mitm CAS berechnen zu können.
Die Aussage scheint für n=1 zu stimmen, denn diese Zahl ist gleich
[mm] p^{n}*2^{p^{n}-1} [/mm] - [mm] M_{p^{n}-1}
[/mm]
(Mersenne-Zahl) und es ist wohl so, dass jede ungerade Primzahl p [mm] M_{p-1} [/mm] teilt (steht zumindest so bei wikipedia). Wie man das beweist, weiß ich auch noch nicht. Vielleicht lässt sich das dann ja verallgemeinern auf [mm] M_{p^{n}-1} [/mm]
Oder ich nehme, die noch unbewiesene Tatsache von wikipedia als Induktionsanfang und zeige noch, dass p ein Teiler von
[mm] 2^{p^{n+1}-1}-2^{p^{n}-1} [/mm] ist. Aber warum das so sein sollte, sehe ich auch nicht.
Stimmt das überhaupt? Oder stimmt es zufälligerweise nur für die Paare (p,n), für die ich es nachrechnen konnte?
Kann man vielleicht irgendwie eine Folge [mm] a_{n} [/mm] angeben, für die sich einfacher ergibt, dass [mm] a_{n}*2^{a_{n}}+1 [/mm] durch p teilbar ist?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:29 Sa 03.11.2012 | | Autor: | hippias |
Ich finde Deine Idee ist prima; zur Begruendung, warum das funktioniert, benoetigt man aber keine Mersenne-Zahlen: der kleine Satz von Fermat genuegt.
|
|
|
| |
|
Hallo icarus,
Du bist auf dem richtigen Weg.
Man kann zeigen, dass für [mm] n=p^k-1 [/mm] der angegebene Term durch p teilbar ist.
Dazu ist im einzelnen zu zeigen:
1) [mm] p^k-1\equiv -1\mod{p} [/mm] (das dürfte offensichtlich sein  )
2) [mm] (p-1)|(p^k-1) [/mm] (Tipp: Polynomdivision)
3) [mm] 2^{p-1}\equiv 1\mod{p} [/mm] (das ist der "kleine Fermat")
...und dann müsste man noch -1*1+1=0 ausrechnen können.
Alles klar?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:50 So 04.11.2012 | | Autor: | icarus89 |
> Hallo icarus,
>
> Du bist auf dem richtigen Weg.
> Man kann zeigen, dass für [mm]n=p^k-1[/mm] der angegebene Term
> durch p teilbar ist.
>
> Dazu ist im einzelnen zu zeigen:
>
> 1) [mm]p^k-1\equiv -1\mod{p}[/mm] (das dürfte offensichtlich sein
> )
>
> 2) [mm](p-1)|(p^k-1)[/mm] (Tipp: Polynomdivision)
>
> 3) [mm]2^{p-1}\equiv 1\mod{p}[/mm] (das ist der "kleine Fermat")
>
> ...und dann müsste man noch -1*1+1=0 ausrechnen können.
>
> Alles klar?
Ja, danke, mit dem kleiner Fermat geht das ganze dann ja ruckzuck.
>
> Grüße
> reverend
>
|
|
|
|
