Mersenne < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie: Wenn [mm] a^n-1 [/mm] f"ur n>1 eine Primzahl ist, dann ist n eine Zweierpotenz. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo!
Auch hier fehlt mir komplett der Ansatz. Ich weiß, dass es etwas mit den Mersenne-Zahlen zu tun hat
[mm] a^n-1=M_n
[/mm]
1. [mm] M_n=2^n-1 [/mm] --> Annahme: Sei n zusammengesetzt
so ist auch [mm] M_n [/mm] eine zusammengesetzte Zahl. Ist nämlich n ein Vielfaches von r>1, so ist [mm] M_r>1 [/mm] und [mm] M_r [/mm] Teiler von [mm] M_n.
[/mm]
Rechenbeispiel:
z.B. n=4 ist zusammengesetzt aus 2*2, und somit ist [mm] M_4 [/mm] auch zusammengesetzt.
[mm] M_4=2^4-1=15=3*5 [/mm]
Für r=2 gilt [mm] M_2=3 [/mm] ist ein Teiler von [mm] M_4.
[/mm]
Weiter weiß leider nicht. Kann mir jemand helfen?
|
|
| |
|
Hallo Stephanie,
an der Aufgabe kann doch was nicht stimmen. Das Gegenbeispiel per se sind doch gerade die Mersenneprimzahlen wie [mm] 31=2^5-1, 8191=2^{13}-1 [/mm] etc. Da ist n doch gerade prim und damit sicher keine Zweierpotenz.
Dafür kannst Du zeigen, dass a eine Zweierpotenz sein muss. [mm] a^n-1 [/mm] ist ja immer durch a-1 teilbar...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:28 Sa 16.10.2010 | | Autor: | reverend |
Hallo nochmal,
die Aufgabe muss so lauten:
| Aufgabe | | Zeigen Sie: Wenn $ [mm] a^n\red{+}1 [/mm] $ für n>1 eine Primzahl ist, dann ist n eine Zweierpotenz. |
Tipp: Zeige erst, dass [mm] a^{2k+1} [/mm] zerlegbar ist.
edit: toller Tipp. Zeige lieber, dass [mm] \blue{a^{2k+1}+1} [/mm] zerlegbar ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:36 So 17.10.2010 | | Autor: | felixf |
Moin!
> Hallo nochmal,
> die Aufgabe muss so lauten:
>
> Zeigen Sie: Wenn [mm]a^n\red{+}1[/mm] für n>1 eine Primzahl ist,
> dann ist n eine Zweierpotenz.
>
>
>
> Tipp: Zeige erst, dass [mm]a^{2k+1}[/mm] zerlegbar ist.
Aber fuer $a$ prim und $k = 0$ ist das doch nicht zerlegbar 
Eine andere moegliche Aufgabenstellung:
Ist [mm] $a^n [/mm] - 1$ prim, so ist $a = 2$ und $n$ prim. (Und das ganze ist eine Mersenne-Primzahl.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:43 So 17.10.2010 | | Autor: | felixf |
Moin!
> k=0 habe ich heimlich ausgeschlossen. Ich mag Peanos
> Frühfassung lieber.
:)
> Und wieso verrätst Du für die erste geratene
> Aufgabenstellung schon, um welche Zweierpotenz es sich
> handelt?
> ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
Ach, da du ja schon verraten hast, warum $a = 2$ sein muss, wollte ich noch etwas dalassen, was man zeigen kann :)
LG Felix
|
|
|
| |
|
Hallo!!
Du hattest recht, ich hab zwei Aufgaben vertauscht.
Die erste Aufgabe ist:
Zeigen Sie: Wenn [mm] a^n-1 [/mm] für n>1 eine Primzahl ist, dann ist a=2 und n eine primzahl.
Die zweite Aufgabe ist:
Zeigen Sie: Wenn [mm] 2^n+1 [/mm] eine Primzahl ist, dann ist n eine Zweierpotenz.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:04 Mo 18.10.2010 | | Autor: | reverend |
Hallo Stephanie,
nu guck.
Da sind ja gleich beide geratenen Aufgaben dabei.
Und, wie weit bist Du? Brauchst Du noch Tipps?
Grüße
reverend
|
|
|
| |
|
| Aufgabe | Aufgabe 1: Wenn [mm] a^n-1 [/mm] für n>1 eine Primzahl ist, dann ist a=2 und n eine Primzahl.
Aufgabe 2: Wenn [mm] 2^n [/mm] eine Primzahl ist, dann ist n eine 2er-Potenz. |
Hallo!
Ich brauch auf jeden Fall noch eure Hilfe.
So, zu Aufgabe 1:
a.) Annahme: [mm] a^n-1 [/mm] ist nicht zerlegbar, dann aber [mm] a^{n+1}-1
[/mm]
[mm] a^{n+1}-1=a^n [/mm] * a -1 -> ist zerlegbar.
Welche Aussage kann ich damit machen?
Wie zeige ich aber jetzt, dass a=2 und n eine Primzahl ist?
b.) [mm] Annahme:2^n [/mm] +1 ist nicht zerlegbar, dann aber
[mm] 2^{n+1}+1=2^n*2+1
[/mm]
Rechenbeispiel: für n=1 -> [mm] 2^3+1=9 [/mm] -> zerlegbar
für n=2 -> [mm] 2^5+1=33 [/mm] -> zerlegbar
Und nu?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:46 Di 19.10.2010 | | Autor: | statler |
Hallo!
> Aufgabe 1: Wenn [mm]a^n-1[/mm] für n>1 eine Primzahl ist, dann ist
> a=2 und n eine Primzahl.
>
> Aufgabe 2: Wenn [mm]2^n[/mm] eine Primzahl ist, dann ist n eine
> 2er-Potenz.
Jetzt haben wir uns schon mal der richtigen Aufgabenstellung genähert. Allerdings ist [mm] 2^n [/mm] nie eine Primzahl. Höchstens [mm] 2^n [/mm] + 1. Deswegen wäre die Aussage in der gegebenen Form übrigens wahr.
> Ich brauch auf jeden Fall noch eure Hilfe.
> So, zu Aufgabe 1:
> a.) Annahme: [mm]a^n-1[/mm] ist nicht zerlegbar, dann aber
> [mm]a^{n+1}-1[/mm]
> [mm]a^{n+1}-1=a^n[/mm] * a -1 -> ist zerlegbar.
> Welche Aussage kann ich damit machen?
> Wie zeige ich aber jetzt, dass a=2 und n eine Primzahl
> ist?
Hier ist dein Gedankengang zumindest mir unklar. Versuch es doch mal andersherum: Wenn a [mm] \not= [/mm] 2 oder n keine Primzahl ist, dann ist [mm] a^n [/mm] - 1 zerlegbar. Gib die Zerlegung einfach an.
> b.) [mm]Annahme:2^n[/mm] +1 ist nicht zerlegbar, dann aber
> [mm]2^{n+1}+1=2^n*2+1[/mm]
> Rechenbeispiel: für n=1 -> [mm]2^3+1=9[/mm] -> zerlegbar
> für n=2 -> [mm]2^5+1=33[/mm] ->
> zerlegbar
> Und nu?
Wie oben! Wenn n keine 2er-Potenz ist, hat es einen ungeraden Teiler. Und damit findest du eine Zerlegung von [mm] 2^n [/mm] + 1, vielleicht erst mit etwas Probieren für kleine Zahlen und dann allgemein.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Zu Aufgabe a.) [mm] a^n-1
[/mm]
- Wenn [mm] a\ne2, [/mm] dann ist [mm] a^n-1 [/mm] zerlegbar und somit keine Primzahl.
Rechenbeispiel: [mm] 3^3-1=26 [/mm] -> zerlegbar
[mm] 3^6-1=728 [/mm] -> zerlegbar
[mm] 4^3-1=63 [/mm] -> zerlegbar
- Wenn [mm] n\ne [/mm] prim, dann ist n zerlegbar in p und q und somit ist
[mm] 2^n-1=2^{p*q}-1 [/mm] zerlegbar.
Rechenbeispiel: [mm] 2^4-1=2^2*2^2-1=15 [/mm] -> zerlegbar
[mm] 2^9-1=2^3*2^3-1=511 [/mm] -> zerlegbar
-Wenn [mm] a\ne2 [/mm] und [mm] n\ne [/mm] prim, dann ist [mm] a^n-1 [/mm] zerlegbar und somit keine
Primzahl.
Rechenbeispiel: [mm] 4^4-1=2^2*2^2*2^2*2^2-1=255 [/mm] -> zerlegbar
[mm] 5^8-12= [/mm] 390624 ->zerlegbar
Ist mein Beweis so richtig und vollständig?
Zu Aufgabe b.) [mm] 2^n+1
[/mm]
- Wenn n keine Zweierpotenz ist, dann ist [mm] 2^n+1 [/mm] ungerade und hat somit einen ungeraden Teiler. Das heißt, [mm] 2^n+1 [/mm] wäre in diesem Fall zerlegbar.
Reicht diese Argumentation bereits aus?
Vielen Vielen Dank
|
|
|
| |
|
Hallo Stephanie,
zu Aufgabe a:
nein, das Durchrechnen einiger Beispiele ist kein Beweis. Überhaupt nicht.
Es ist doch klar, dass für ungerades a sich [mm] a^n-1 [/mm] als gerade Zahl ergibt und somit durch zwei teilbar ist.
Betrachten wir nun mal die Funktion [mm] f(x)=x^n-1 [/mm] mit n>1. Wo hat sie eine Nullstelle? Wenn du eine Nullstelle [mm] x_N [/mm] kennst, dann kannst Du doch das Polynom zerlegen, weil es den Faktor [mm] (x-x_N) [/mm] enthält ...
So ähnlich für [mm] x^{m*n}-1=\left(x^m\right)^n-1=\left(x^n\right)^m-1 [/mm] ...
Du kannst also explizit jeweils einen Faktor angeben, ohne überhaupt ein Zahlenbeispiel zu bemühen.
Zu Aufgabe b:
> - Wenn n keine Zweierpotenz ist, dann ist $ [mm] 2^n+1 [/mm] $ ungerade und hat
> somit einen ungeraden Teiler. Das heißt, $ [mm] 2^n+1 [/mm] $ wäre in diesem Fall
> zerlegbar.
Das ist Unsinn. Wieso folgt denn aus der Tatsache, dass eine Zahl ungerade ist, dass sie einen ungeraden Teiler hat und somit zerlegbar ist? Stimmt das denn für 19,37,101 etc.?
Auch hier kannst Du ähnlich überlegen wie in Aufgabe a.
Gegeben sei eine Funktion [mm] f(x)=x^n+1.
[/mm]
Wenn nun n ungerade ist, kennst Du dann eine Nullstelle? Wenn ja, kannst Du das Polynom faktorisieren.
Und wenn Du das kannst, kannst Du auch zeigen, dass n überhaupt keinen ungeraden Teiler haben kann.
Grüße
reverend
|
|
|
|
