3 Primitivwurzel modulo Fermat Primzahl

27.03.2012, 13:52

xlynax

3 Primitivwurzel modulo Fermat Primzahl

Meine Frage:
Hallo,
Ich habe ein Problem bei der Aufgabe zu beweisen, dass 3 eine Primitivwurzel modulo Primzahlen der Form $\begin{eqnarray*} p=2^{n}+1 \\ \end{eqnarray*}$ ist.

Meine Ideen:
Ich muss ja zeigen, dass die Ordnung von 3 mod p $\begin{eqnarray*} p-1 =2^{n} \end{eqnarray*}$ ist.
D.h. $\begin{eqnarray*} 3^{m}\not\equiv1 \ mod\ p \end{eqnarray*}$ wenn $\begin{eqnarray*} m < 2^{n} \end{eqnarray*}$
Ich hab $\begin{eqnarray*} 3 \end{eqnarray*}$ in $\begin{eqnarray*} (2 + 1) \end{eqnarray*}$ umgeschrieben und dann den binomischen Lehrsatz angewendet, aber irgendwie bringt mich das wohl nicht weiter, denn mir ist nicht klar, warum die erhaltene Summe nicht equivalent zu 1 sein kann...
Schonmal danke!

27.03.2012, 14:05

Mystic

Auf diesen Beitrag antworten »

RE: 3 Primitivwurzel modulo Fermat Primzahl

Zitat:

Original von xlynax
Meine Frage:
Hallo,
Ich habe ein Problem bei der Aufgabe zu beweisen, dass 3 eine Primitivwurzel modulo Primzahlen der Form $\begin{eqnarray*} p=2^{n}+1 \\ \end{eqnarray*}$ ist.

Erstens ist das so klar falsch, denn 3 ist sicher nicht Primitivwurzel für p=3... Zum zweiten gilt offenbar, dass für jede feste Primitivwurzel g mod p dann alle anderen einfach durch g^k mod p mit einem ungeradem k im Bereich {1,2,...,p-2} gegeben sind... Woran erinnert dich das? Grübel, grübel... Big Laugh

27.03.2012, 17:18

xlynax

Auf diesen Beitrag antworten »

RE: 3 Primitivwurzel modulo Fermat Primzahl

Zitat:

Original von Mystic
Erstens ist das so klar falsch, denn 3 ist sicher nicht Primitivwurzel für p=3...

Das stimmt. Es muss wohl fuer $\begin{eqnarray*} n>1 \end{eqnarray*}$ gemeint sein, aber in der Aufgabe ist das nicht erwähnt.

Zitat:

Original von Mystic
Zum zweiten gilt offenbar, dass für jede feste Primitivwurzel g mod p dann alle anderen einfach durch g^k mod p mit einem ungeradem k im Bereich {1,2,...,p-2} gegeben sind... Woran erinnert dich das?

Leider muss ich zugeben, dass mich das jetzt an nichts erinnert und warum muss k ungerade sein?
Vielleicht stehe ich aber auch dermassen auf dem Schlauch...

27.03.2012, 18:06

xlynax

Auf diesen Beitrag antworten »

Komme ich da vielleicht mit Induktion weiter?
Aber da habe ich dann das Problem, dass z. B. fuer $\begin{eqnarray*} n=3 \end{eqnarray*}$ also $\begin{eqnarray*} p=9\\ \end{eqnarray*}$ ja keine Primzahl ist!?!

27.03.2012, 18:24

Mystic

Auf diesen Beitrag antworten »

RE: 3 Primitivwurzel modulo Fermat Primzahl

Zitat:

Original von xlynax
Leider muss ich zugeben, dass mich das jetzt an nichts erinnert und warum muss k ungerade sein?
Vielleicht stehe ich aber auch dermassen auf dem Schlauch...

Hm, es sollte dich eigentlich daran erinnern, dass genau die Potenzen mit einer geraden Hochzahl die quadratischen Rest mod p sind, wobei p dafür nur eine ungerade Primzahl zu sein braucht... Damit gilt dann speziell für unsere Primzahlen hier, nach dem was oben schon gesagt wurde, dass die Primitivwurzeln mod p genau mit den quadratischen Nichtresten mod p übereinstimmen... Ich hoffe, das hilft dir jetzt endlich weiter, sonst bin ich mit meiner Weisheit am Ende...

Neue Frage »

Antworten »

3 Primitivwurzel modulo Fermat Primzahl

Verwandte Themen