Fermat Zahlen - Teiler, Ordnung etc.

09.05.2015, 13:13

Matheneuling1991

Fermat Zahlen - Teiler, Ordnung etc.

Hallo

Ich habe hier eine Aufgabe aus der Zahlentheorie - dabei geht es um Fermatzahlen

a) Sei $\begin{eqnarray*} F_N=2^{2^n}+1 \end{eqnarray*}$ , n=0,1,2,... (Fermat Zahlen) gegeben und p irgendein ungerader Primteiler von $\begin{eqnarray*} F_N \end{eqnarray*}$ ; Zeige, dass dann $\begin{eqnarray*} ord_p(2)=2^{n+1} \end{eqnarray*}$
b) Sei $\begin{eqnarray*} F_N \end{eqnarray*}$ eine Primzahl und n>1, dann gilt $\begin{eqnarray*} ord_{F_n}(2) \neq \phi(F_n) \end{eqnarray*}$
c) Sei p ungerader Primteiler von $\begin{eqnarray*} F_n \end{eqnarray*}$ . Zeigen sie dann, dass $\begin{eqnarray*} p \equiv 1 (mod \ 2^{n+1}) \end{eqnarray*}$

Das ist erst einmal die Aufgabe.. Nun habe ich leider nicht besonders viel nützliche Gedanken um die Aufgabe zu lösen;
Klar ist, dass $\begin{eqnarray*} \phi(p) \end{eqnarray*}$ in der a) (p-1) ist, da p eine Primzahl ist; Dies ist dann logischerweise eine gerade Zahl. Ebenso gilt, dass die ord(a) ein Teiler von p-1 sein muss;
Da ich aber unfähig bin, das p einzuschätzen, bringt mir diese Aussage momentan absolut nichts;
zur b) Da $\begin{eqnarray*} F_n \end{eqnarray*}$ Primzahl ist $\begin{eqnarray*} \phi(F_n)=2^{2^n} \end{eqnarray*}$ , aber was bringt mir das?

Über eine Anregung wäre ich sehr dankbar.. smile

09.05.2015, 14:32

HAL 9000

Auf diesen Beitrag antworten »

Zu a)

1) Rechne doch einfach mal schlicht $\begin{align*} 2^{2^{n+1}} \bmod F_N \end{align*}$ aus.

2) Die echten Teiler von $\begin{align*} 2^{n+1} \end{align*}$ sind die Zahlen $\begin{align*} 2^t \end{align*}$ für $\begin{align*} t=0,1,\ldots,n \end{align*}$ . Zeige, dass $\begin{align*} 2^{2^t} \not\equiv 1\bmod F_N \end{align*}$ ist.

Tipp zu beiden: Es ist $\begin{align*} 2^{2^n} = F_n-1 \equiv -1\bmod F_n \end{align*}$ .

09.05.2015, 16:00

Matheneuling1991

Auf diesen Beitrag antworten »

Wow, gibt es etwas, dass du nicht kannst?

Danke, dass du mir immer hilfst, egal um was es gerade geht, das ist großartig..!! smile

Jedenfalls: 1) ist mir gelungen.. Damit kann ich nachweisen, dass $\begin{eqnarray*} 2^{2^{n+1}} \equiv 1 \end{eqnarray*}$ (mod Fn) ist. Und da Fn ein Vielfaches von p ist, ist damit auch gezeigt, dass dies für mod p gilt;
Aber bei der 2) fehlt es mir an der Idee..Dass es für ein t=0,...,n nicht 1 (mod Fn) ist, ist trivial, weil $\begin{eqnarray*} 2^{2^{t}} \end{eqnarray*}$ ja kleiner als Fn selbst ist und sich zwischen 2 und Fn befindet;
Aber ich möchte ja zeigen, dass es für ein t=0,...,n nicht 1 (mod p) ist und da habe ich keine Ahnung wie ich den Übergang von mod Fn zu mod p schaffe

09.05.2015, 16:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Matheneuling1991
Dass es für ein t=0,...,n nicht 1 (mod Fn) ist, ist trivial, weil $\begin{eqnarray*} 2^{2^{t}} \end{eqnarray*}$ ja kleiner als Fn selbst ist und sich zwischen 2 und Fn befindet;
Aber ich möchte ja zeigen, dass es für ein t=0,...,n nicht 1 (mod p) ist und da habe ich keine Ahnung wie ich den Übergang von mod Fn zu mod p schaffe

Wir sprechen doch über $\begin{align*} p=F_n \end{align*}$ .

Außerdem kann es es nicht nur für ein solches t nachgewiesen werden, sondern für alle t=0,1,...,n.

P.S.: Vielleicht referenzierst du hier falsch: Meine Punkte 1) und 2) beziehen sich ausschließlich auf a). Wenn du jetzt über b) oder c) sprichst, dann kennzeichne dies bitte deutlich!

09.05.2015, 16:22

Matheneuling1991

Auf diesen Beitrag antworten »

Nein, es geht doch darum, dass ord(2) = 2^(n+1) (mod p) ist, also 2^(2^(n+1))=1 (mod p)
Dabei ist p irgendein ungerader Primteiler von F_n, also nicht zwangsläufig F_n selbst..

Und wenn du mod F_n rechnest gilt die Aussage doch für alle t=0,...,n, dass 2^(2^t) irgendetwas zwischen 2 und (F_n) -1 ist und damit insbesondere nicht 1 (mod F_n)
Aber das reicht ja noch nicht, weil es ja um mod p gilt..

EDIT: Ich spreche noch über die a)... Wenn die ord(2)=2^(n+1) (mod p) sein soll muss ich ja zwei Dinge nachweisen; Erstens, dass 2^(2^(n+1))=1(mod p)
und dass es keine kleinere Zahl als 2^(n+1) gibt, wodurch dies gilt..
Die 1) denke ich, kann ich definitiv so übertragen; d.h. wenn es (mod F_n) gilt, dann auch (mod p)
Nur die 2) ist reicht so eben nich nicht ganz.. unglücklich

09.05.2015, 16:24

HAL 9000

Auf diesen Beitrag antworten »

Achso, hast Recht, da habe ich schlecht gelesen: Ich dachte, es geht um Fermatsche Primzahlen $\begin{align*} p=F_n \end{align*}$ in a).

Über eine kurze Zwischenüberlegung sind wir doch trotzdem fertig:

Aus $\begin{align*} 2^{2^n}\equiv -1\bmod F_n \end{align*}$ folgt doch sofort $\begin{align*} 2^{2^n}\equiv -1\bmod q \end{align*}$ für alle Teiler $\begin{align*} q \mid F_n \end{align*}$ , speziell auch für $\begin{align*} q=p \end{align*}$ . Und dass $\begin{align*} -1\not\equiv 1\bmod p \end{align*}$ für alle $\begin{align*} p>2 \end{align*}$ gilt, sollte dir doch klar sein.

09.05.2015, 16:38

Matheneuling1991

Auf diesen Beitrag antworten »

Kannst du mir erklären, weshalb du das auf alle t=0,..,n übertragen kannst?

Klar, für 2^n ist -1 nicht 1 (mod p), aber wieso gilt dieses Argument für t=0,.., n-1?

09.05.2015, 16:55

ollie3

Auf diesen Beitrag antworten »

hallo,
falls HALL 9000 gerade nicht da ist, das kann ich dir auch beantworten.
Nehmen wir an es gäbe ein t<n mit 2^(2^t)= -1 mod p, dann wäre 2^(2^(t+1))=
2^(2^t) mal 2^(2^t)=(-1)*(-1)=1, und bei allen höheren t´s erst recht, dann
könnte 2^(2^n)=-1 nicht gelten...
gruss ollie3

09.05.2015, 17:11

Matheneuling1991

Auf diesen Beitrag antworten »

Ah, ein Denkfehler meinerseits.. Danke!
Fehlt nur noch die b und die c.. smile

Hat mir da jemand einen Tipp?? smile

09.05.2015, 17:14

HAL 9000

Auf diesen Beitrag antworten »

@ollie3

Die Annahme muss sich natürlich auf $\begin{align*} 2^{2^t}\equiv 1\bmod p \end{align*}$ beziehen. Augenzwinkern

Und diese führt mit $\begin{align*} 1 \equiv \left( 2^{2^t} \right)^{2^{n-t}} \equiv 2^{2^t\cdot 2^{n-t}} = 2^{2^n} \equiv -1\bmod p \end{align*}$ zum Widerspruch.

b) folgt doch sofort aus a), wenn man noch $\begin{align*} n+1 < 2^n \end{align*}$ für $\begin{align*} n>1 \end{align*}$ berücksichtigt.

09.05.2015, 18:01

Matheneuling1991

Auf diesen Beitrag antworten »

Natürlich.. smile

Habe ich bei der c) auch etwas offensichtliches übersehen? Oder ist die schwerer?

09.05.2015, 19:14

HAL 9000

Auf diesen Beitrag antworten »

c) Elementordnung ist Teiler der Gruppenordnung, d.h. es muss $\begin{align*} \operatorname{ord}_p(2) \mid \varphi(p) \end{align*}$ gelten, nach (a) also $\begin{align*} 2^{n+1} \mid (p-1) \end{align*}$ .

09.05.2015, 19:53

Matheneuling1991

Auf diesen Beitrag antworten »

Ich fühle mich gerade wahnsinnig dumm, weil die Lösungen, so offensichtlich erscheinen, sobald du sie sagst..
Aber jetzt ist alles klar.. smile

Vielen Dank!! smile

Neue Frage »

Antworten »

Fermat Zahlen - Teiler, Ordnung etc.

Verwandte Themen