Primitivwurzel

26.07.2015, 23:01

knutkarl

Primitivwurzel

Meine Frage:
Sei 2t+1 > 5 und prim und t prim.

Dann ist 2^t nicht kongruent 1 mod (2t+1), wenn (2t+1) kongruent 1 mod 4.
Dann ist 2^t kongruent 1 mod (2t+1), wenn (2t+1) kongruent 3 mod 4.

Beweis?

Meine Ideen:
CarmichaelLambda (2t+1) = 2t. 2 ist Primitivwurzel bezüglich (2t+1), wenn die multiplikative Ordnung von 2 bezüglich (2t+1) gleich CarmichaelLambda (2t+1) = 2t ist. 2 kann die Ordnung 2, t oder 2t haben.

Zwei scheidet aus weil 2² mod (2t+1) = 4 und damit nicht multiplikative Ordnung von 2 bezüglich (2t+1) ist. Bleibt t. Also ist die Frage, wann 2^t kongruent 1 mod (2t+1) ist und wann nicht.

Zwei Beiträge zusammengefasst. Steffen

27.07.2015, 10:22

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von knutkarl
Sei 2t+1 > 5 und prim und t prim.

Dann ist 2^t nicht kongruent 1 mod (2t+1), wenn (2t+1) kongruent 1 mod 4.
Dann ist 2^t kongruent 1 mod (2t+1), wenn (2t+1) kongruent 3 mod 4.

Beide Aussagen sind falsch, die erste für t=8 und die zweite für t=5:

$\begin{align*} 2^8 = 256\equiv 1\bmod 17 \end{align*}$ und $\begin{align*} 2^5 = 32\equiv -1 \not\equiv 1\bmod 11 \end{align*}$ .

EDIT: Entschuldige, ich hab die Auch-Bedingung "t prim" überlesen. Aber irgendwie ist dann deine erste Aussage sinnfrei:

Der Fall $\begin{align*} 2t+1\equiv 1\bmod 4 \end{align*}$ impliziert $\begin{align*} t\equiv 0\bmod 2 \end{align*}$ , es gibt aber keine solche Primzahlen t>2. unglücklich

Richtig wäre jedenfalls die Aussage

Zitat:

Sei 2t+1 prim.

Dann ist 2^t kongruent -1 mod (2t+1), wenn (2t+1) kongruent $\begin{align*} \pm 3 \bmod 8 \end{align*}$ .
Dann ist 2^t kongruent 1 mod (2t+1), wenn (2t+1) kongruent $\begin{align*} \pm 1 \bmod 8 \end{align*}$ .

27.07.2015, 13:40

knutkarl

Auf diesen Beitrag antworten »

Stimmt, da habe ich Blödsinn geschrieben. Das muß heißen: t kongruent 1 mod 4 respektive t kongruent 3 mod 4. Und t > 3.

Also 2 ist Primitivwurzel mod (2t+1), genau dann, wenn t kongruent 1 mod 4. Äquivalent zu 2^t nicht kongruent 1 mod (2t+1).

27.07.2015, 18:40

knutkarl

Auf diesen Beitrag antworten »

Wenn t > 3, wie kann dann 2t+1 kongruent 1 mod 8 sein? Entweder t=4k+1, dann ist 2t+1 = 8k+3 kongruent 3 mod 8. Oder t=4k+3, dann ist 2t+1 = 8k+7 kongruent 7 mod 8. Richtig?

Kannst Du bitte einen möglichst ausführlichen Beweis für die von Dir mitgeteilten Aussagen geben? Ich möchte das gerne verstehen und wäre dafür dankbar.

27.07.2015, 18:50

HAL 9000

Auf diesen Beitrag antworten »

Ehrlich gesagt habe ich nichts bewiesen, sondern mich lediglich auf den 2.Ergänzungssatz des Quadratischen Reziprozitätsgesetzes bezogen. Hoffentlich wolltest du nicht gerade den beweisen, ansonsten haben wir einen feinen Zirkelschluss. Big Laugh

27.07.2015, 18:57

knutkarl

Auf diesen Beitrag antworten »

Den verstehe ich nicht wirklich. Kannst Du den erläutern? Ich verstehe auch nicht, wie 2t+1 kongruent 1 mod 8 sein kann. Würde mir sehr helfen.

28.07.2015, 09:15

ollie3

Auf diesen Beitrag antworten »

hallo,
falls HALL 9000 nicht da ist, kann ich kurz weiterhelfen.
Also, jede ungerade zahl hat ja die forn 2k+1. Und wenn man sie mod 8 betrachtet,
kann sie nur die form 8k+1, 8k+3, 8k+5 oder 8k+7 haben, also kongruent 1,3,5,7
sein.
Und die andere sache: Nach dem satz von carmichael giilt auf jeden fall
2^2k=1 mod (2k+1). Jetzt ist die frage, ob 2^k=1 oder 2^k=-1 gilt, denn
2^2k ist ja nichts anderes als (2^k)^2 .
gruss ollie3

28.07.2015, 09:31

HAL 9000

Auf diesen Beitrag antworten »

Kurze Erläuterung noch zu dem erwähnten zweiten Ergänzungssatz. Der besagt, dass 2 genau dann quadratischer Rest modulo einer ungeraden Primzahl $\begin{align*} p \end{align*}$ ist, wenn $\begin{align*} p\equiv \pm 1\bmod 8 \end{align*}$ gilt.

Wie hängt das mit deiner Fragestellung zusammen? Ist $\begin{align*} g \end{align*}$ eine beliebige Primitivwurzel modulo $\begin{align*} p \end{align*}$ , sowie $\begin{align*} 2\equiv g^s\bmod p \end{align*}$ , so ist 2 genau dann quadratischer Rest, wenn $\begin{align*} s \end{align*}$ gerade ist. Nun gilt aber auch $\begin{align*} 2^t \equiv g^{st}\equiv 1\bmod p \end{align*}$ genau dann, wenn $\begin{align*} st \end{align*}$ ein Vielfaches von $\begin{align*} 2t \end{align*}$ ist, was auch genau für gerade $\begin{align*} s \end{align*}$ der Fall ist.

28.07.2015, 13:12

knutkarl

Auf diesen Beitrag antworten »

@ ollie3:
(2t+1) mit t > 3 und prim kann nur 3 mod 8 oder 7 mod 8 sein. Und 7 mod 8 entspricht -1 mod 8, das habe ich jetzt verstanden.

@HAL9000:
Wo finde ich das, was Du schreibst? Mit Jacobi/Legrende-Symbol tue ich mich etwas schwer.

Ganz habe ich das nicht verstanden. Kann 2 Primitivwurzel mod p und gleichzeitig quadratischer Rest mod p sein?

Wofür ich das brauche? Ich suche nach Primzahlen der Form (2t+1), für die 2 Primitivwurzel ist. Das ist genau dann der Fall wenn 2^t nicht kongruent 1 mod (2t+1) ist. Das ist für t > 10^500 etwas lästig zu testen. t mod 4 ist leichter zu prüfen.

28.07.2015, 15:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von knutkarl
Wo finde ich das, was Du schreibst?

Wie jetzt? Das was ich geschrieben habe, findest du dort, wo ich es geschrieben habe.

Zitat:

Original von knutkarl
Mit Jacobi/Legrende-Symbol tue ich mich etwas schwer.

Dann schlag es nach.

Zitat:

Original von knutkarl
Kann 2 Primitivwurzel mod p und gleichzeitig quadratischer Rest mod p sein?

Natürlich nicht!!! Geht eigentlich auch indirekt aus meiner letzten Antwort hervor, aber nochmal deutlicher:

Für einen quadratischen Rest $\begin{align*} q \end{align*}$ mit dann ja existierendem $\begin{align*} x \end{align*}$ mit $\begin{align*} x^2\equiv q\bmod p \end{align*}$ gilt ja dann $\begin{align*} q^{\frac{p-1}{2}} \equiv x^{p-1}\equiv 1\bmod p \end{align*}$ , damit ist $\begin{align*} \operatorname{ord}(q)\leq \frac{p-1}{2} < p-1 \end{align*}$ , und $\begin{align*} q \end{align*}$ kann somit keine Primitivwurzel sein. unglücklich

28.07.2015, 16:05

knutkarl

Auf diesen Beitrag antworten »

Danke! Ich glaube, von hier aus komme ich selbst weiter.

Neue Frage »

Antworten »

Primitivwurzel

Verwandte Themen