Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Primitivwurzel modulo 17

Primitivwurzel modulo 17

Universität / Fachhochschule

Tags: Kongruenz, Primitivwurzel

Sukomaki aktiv_icon

18:17 Uhr, 08.03.2023

Hallo,

im Zusammenhang mit der Beschäftigung mit der Berechnung von

\cos (\frac{2 π}{17})

bin ich auf eine Kongruenz gestoßen, die ich gerne beweisen möchte. Und zwar geht es darum, zu zeigen, dass

(3^{2 a} + 3 \cdot 3^{2 b}) m o d 17 = m

genau vier Lösungen bei

(a, b) \in {0, \dots, 7}^{2}

für

m \in {1, \dots, 16}

hat.

Die

3

habe ich in der Gleichung gewählt, da sie die kleinste Primitivwurzel von

17

ist.

Leider habe ich keinen Ansatz. Und mein Versuch,

a

und

b

zusammenzufassen in der Formel

(3^{2 ⌊ \frac{k}{8} ⌋} + 3^{2 (k m o d 8) + 1}) m o d 17 = m

mit

k \in {0, \dots, 63}

ist auch nicht gerade zielführend.

Kann mir jemand einen Anstoß geben?

Sukomaki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Dreiecke und Kongruenz

HAL9000

13:55 Uhr, 09.03.2023

Warum rechnest du nicht einfach alle

8^{2} = 64

Kombinationen für

(a, b)

durch und verifizierst so die Behauptung? Kriegt zwar keinen Schönheitspreis, aber ist doch legitim.

-------------------------------------------------

Ok, ein anderer Versuch, ist aber nicht unbedingt kürzer: Man kann ja jedem

m \in {1, \dots, 16}

exakt einen Index

j \in {0, \dots, 15}

zuordnen mit

m \equiv 3^{j} mod 17

, da ja 3 schließlich Primitivwurzel ist.

Nun kann man aus dem Tripel

(a, b, j)

mit

3^{j} \equiv 3^{2 a} + 3^{2 b + 1} mod 17

ja durchaus schlussfolgern

3^{j + 1} \equiv 3^{2 a + 1} + 3^{2 b + 2} = 3^{2 (b + 1)} + 3^{2 a + 1} mod 17

,

d.h. wir haben ein neues Tripel

(b + 1, a, j + 1)

generiert. Das kann man nun reihum machen bis man nach 16 Schritten wieder auf das Ausgangstripel stößt (die

a, b

werden modulo 8 betrachtet, das

j

hingegen modulo 16).

Egal mit welchem Paar

(a, b)

(und zugehörigem

j

) man startet, man gerät immer in einen solchen 16er-Zyklus. Bei insgesamt

8^{2} = 64

Paaren gibt es also genau 4 solche 16er-Zyklen, welche paarweise disjukt sind.

Sukomaki aktiv_icon

16:11 Uhr, 09.03.2023

Ich habe es schon auf diese Weise verifiziert. Aber ich hätte es lieber ein wenig eleganter.

Für

(a, b) \in {0, \dots, 7}^{2}

ist jedes

m

4 mal vertreten.

Für

(a, b) \in {0, \dots, 15}^{2}

ist jedes

m

16 mal vertreten.

Für

(a, b) \in {0, \dots, 31}^{2}

ist jedes

m

64 mal vertreten.

u.s.w.

Für

(a, b) \in {0, \dots, 3}^{2}

gibt es jedoch kein Muster. Ich habe erwartet, dass jedes

m

da genau einmal auftritt. Ist aber nicht so.

HAL9000

16:34 Uhr, 09.03.2023

Also ich halte meine Ergänzung für elegant genug - wenn auch (wie gesagt) nicht kürzer. Man muss übrigens noch ergänzend begründen, warum niemals

3^{2 a} + 3^{2 b + 1} \equiv 0 mod 17

eintreten kann, aber das ist so schwer nicht.

Sukomaki aktiv_icon

17:29 Uhr, 09.03.2023

> Bei insgesamt

8^{2} = 64

Paaren gibt es also genau

4

solche

16

er-Zyklen, welche paarweise disjukt sind.

Und aus der Tatsache, dass wir die Menge der

64

Paare derart zerlegen können, folgt unmittelbar, dass für jedes

m \in {1, \dots, 16}

vier verschiedene Darstellungsmöglickeiten existieren?

> warum niemals

3^{2 a} + 3^{2 b + 1} \equiv 0 m o d 17

eintreten kann

Ich habe zuerst gedacht, das hätte damit zu tun, dass

3

Primitivwurzel von

17

ist.

Aber da gibt es ein Gegenbeispiel :

3

ist Primitivwurzel von

7

und trotzdem

a = 0

und

b = 1 \Rightarrow (3^{2 a} + 3^{2 b + 1}) m o d 7 = 0

HAL9000

17:39 Uhr, 09.03.2023

> Und aus der Tatsache, dass wir die Menge der 64 Paare derart zerlegen können, folgt unmittelbar, dass für jedes

m

vier verschiedene Darstellungsmöglickeiten existieren?

Im Zusammenhang damit, dass in jedem 16-er-Zyklus jedes

j

(und damit jedes

m

) GENAU einmal vorkommt (wie oben nachgewiesen): Ja!

Sukomaki aktiv_icon

12:40 Uhr, 10.03.2023

Wie sieht der Beweis für

3^{2 a} + 3^{2 b + 1} \neq 0 m o d 17

richtig aus?

HAL9000

12:47 Uhr, 10.03.2023

Naja, wegen

3^{2 a} + 3^{2 b + 1} = 3^{2 a} (1 + 3^{2 (b - a) + 1})

ist das gleichbedeutend damit, dass

3^{c} \neq - 1 mod 17

für alle ungeraden

c

ist. Da 3 Primitivwurzel modulo 17 ist, gilt aber

3^{\frac{17 - 1}{2}} = 3^{8} \equiv - 1 mod 17

, und damit eben wegen jener Primitivwurzeleigenschaft dann auch

3^{c} \neq - 1 mod 17

für alle

c \neq 8 mod 16

, speziell also auch alle ungeraden

c

.

P.S.: Dein Beispiel

p = 7

ist schlecht gewählt: Die Argumentation wie bei

p = 17

klappt nur, wenn auch

\frac{p - 1}{2}

gerade ist, d.h. für Primzahlen

p \equiv 1 mod 4

Sukomaki aktiv_icon

09:33 Uhr, 11.03.2023

Das kann ich nachvollziehen. Aber ich verstehe noch nicht, warum

3^{\frac{p - 1}{2}} = - 1 m o d p

für

p = 1 m o d 4

allgemein gilt.

HAL9000

10:00 Uhr, 11.03.2023

Es gilt für sogar für ALLE ungeraden

p

, allerdings muss eben 3 Primitivwurzel ist. Dass es auch "allgemein" gilt, habe ich ja gar nicht behauptet.

Und nochmal: Das

p \equiv 1 mod 4

ist lediglich dafür nötig, dass der Exponent

\frac{p - 1}{2}

auch gerade ist. Wenn er nämlich ungerade wäre, dann klappt ja die obige Argumentation "

3^{c} \neq - 1 mod p

für alle UNGERADEN

c

" nicht mehr.

Irgendwie schrecklich, dass du die Argumente so bunt durcheinander würfelst. Lies doch das nächste mal bitte genauer!

Sukomaki aktiv_icon

11:47 Uhr, 11.03.2023

> Es gilt für sogar für ALLE ungeraden p, allerdings muss eben 3 Primitivwurzel ist.

Gibt es so ein

p

mit der Eigenschaft, dass es ungerade, aber nicht prim ist, so dass

3

eine Primitivwurzel zu

p

ist?

> Wenn er (der Exponent

\frac{p - 1}{2}

) nämlich ungerade wäre, dann klappt ja die obige Argumentation "

3^{c} \neq - 1 m o d p

für alle UNGERADEN

c

" nicht mehr.

Das ist mir schon klar.

Hey, ich habe so die Angewohnheit, dass ich manchmal das Richtige meine, aber etwas Falsches schreibe. :-D)

Sorry dafür.

Ich meinte, dass wenn

3

Primitivwurzel zu der Primzahl

p

ist und

p \equiv 1 m o d 4

DANN gilt :

3^{\frac{p - 1}{2}} \equiv - 1 m o d p

Das ist z.B. der Fall für

p \in {5, 17, 53, \dots}

(das meinte ich mit "allgemein")

Und unter diesen Voraussetzungen, frage ich mich eben, warum

3^{\frac{p - 1}{2}} \equiv - 1 m o d p

ist.

Nicht mehr und nicht weniger.

HAL9000

16:52 Uhr, 11.03.2023

Ok, ausführlichst: Allgemein gilt für alle ungeraden Primzahlen

p

sowie nicht durch

p

teilbaren

a

laut Kleinem Fermat

(a^{\frac{p - 1}{2}} - 1) \cdot (a^{\frac{p - 1}{2}} + 1) = a^{p - 1} - 1 \equiv 0 mod p

.

Damit gilt entweder

a^{\frac{p - 1}{2}} \equiv 1 mod p

oder

a^{\frac{p - 1}{2}} \equiv - 1 mod p

. Ist nun zudem

a

Primitivwurzel modulo

p

, dann darf ersteres nicht gelten, somit gilt in dem Fall zwangsläufig

a^{\frac{p - 1}{2}} \equiv - 1 mod p

Sukomaki aktiv_icon

17:31 Uhr, 11.03.2023

Dann habe ich das jetzt verstanden. Danke. Es ist einfacher als ich vermutet habe.

Ich erkenne mal wieder, wie wichtig es ist, Sätze zu kennen. Und diese natürlich auch anzuwenden.

Z.B. würde ich bei so mancher Grenzwert-Berechnung ohne den de l'Hopital nicht weiter wissen.

Aber auch der mathematische Blick ist von Nutzen. Ich staune des öfteren über Deine Klarheit, die mir leider ein wenig abgeht.

Ich könnte zwar sagen, was es mit der Zahl

1, 64493 \dots

auf sich hat, aber denke zuweilen zu kompliziert.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1568447

1568244

	Status: nicht eingeloggt	Noch nicht registriert?