3 ist Primitivwurzel von 65537 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | 3 ist Primitivwurzel von [mm] 2^{16}+1=65537 [/mm] und von jeder anderen Fermat-Primzahl [mm] 2^{2^n}+1. [/mm] |
Hallo zusammen!
Leider weiß ich überhaupt nicht, wie ich das zeigen soll. Ich hab mal so angefangen
1. Da [mm] F_4=2^{16}+1=65537 [/mm] eine Primzahl ist, haben wir die Gruppenordnung ord(G)=65536 vorliegen. (Allgemein: ord(G)=p-1, weil prim)
2. Es muss nun gezeigt werden, dass
[mm] 3^{ord(G)}\equiv [/mm] 1 mod 65537
3. Da 3 [mm] \in [/mm] G, gilt ord(3)|ord(G)=65536. Also muss ich "nur" die Ordnungen überprüfen, die Teiler von ord(G) sind... aber das sind verdammt viele...
Hat jemand eine Idee, wie ich das zeigen kann?
Vielen dank schon im Voraus
|
|
| |
|
moin Komplex,
Als erstes sollte man wohl nicht außer Acht lassen, dass $65536 = [mm] 2^{16} [/mm] = [mm] 2^{2^n}$ [/mm] für $n=4$ ist (du sollst es ja für alle $n [mm] \in \IN$ [/mm] zeigen, für die die so gebildete Zahl prim ist).
Das reduziert die zu untersuchenden Teiler nun doch schon drastisch, da sich diese aufsteigend teilen.
Es reicht also zu zeigen, dass [mm] $3^{2^{15}} \not \equiv [/mm] 1$ (mod [mm] $2^{16}+1)$ [/mm] (bzw. die selbe Aussage für allegemeines $n$).
Dafür würde ich an deiner Stelle wie folgt vorgehen:
Schreibe $3 = 2+1$ und berechne mit der allgemeinen binomischen Formel:
[mm] $(2+1)^{2^{15}}$.
[/mm]
Natürlich kannst du das nicht so einfach von Hand berechnen, aber du kannst dir überlegen, was modulo [mm] $2^{16} [/mm] + 1$ alles wegfällt und dass das, was übrig bleibt, keinesfalls 1 ergibt.
Also überleg nochmal ein wenig und wenn du nicht weiter kommst kannst du gerne fragen.
Solltest du die Aussage für diese spezielle Zahl ausreichend gezeigt haben wird es glaube ich kein Problem deine Argumentation zu verallgemeinern, da du ja eh nicht alles ausrechnen kannst sondern auch hier bei diesem speziellen Fall bereits geschickt überlegen musst.
lg
Schadow
|
|
|
| |
|
Vielen vielen Dank für deine Antwort. Gerade scheitert es bei mir daran, dass ich nicht weiß, was modulo [mm] 2^{16}+1 [/mm] alles wegfällt. Kannst du mir da nochmal helfen?
DANKE!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mi 01.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
