Kongruenz mittels Primitivwurzel lösen

Neue Frage »

NeFa3 Auf diesen Beitrag antworten »
Kongruenz mittels Primitivwurzel lösen
Meine Frage:
Ich habe folgende Problemstellung:

Finde alle Lösungen der Kongruenz x^11?2(mod17)

Ich habe gezeigt, dass 3 eine Primitivwurzel modulo 17 ist und ab da komme ich nicht weiter. Ich weiß nicht wie mir diese Eigenschaft hilft das zu lösen.

Meine Ideen:
Ich denke ich muss das irgendwie mit der Ordnung verknüpfen, aber im Skript habe ich keine Sätze gefunden, die mir helfen könnten.
HAL 9000 Auf diesen Beitrag antworten »

Könnte es sein, dass du meinst? Aber sonderliches Interesse scheinst du ja nicht an der Aufgabe zu haben, sonst hättest du das ja zeitnah korrigiert.
NeFa3 Auf diesen Beitrag antworten »

Oh das ist mir nicht aufgefallen.. Ja das war eigentlich gemeint. Das ist mein erster Beitrag und jetzt ist er auch nicht mehr editierbar.
tatmas Auf diesen Beitrag antworten »

hallo,

du hast 3 als Primtivwurzel. als lässt sich jedes x deiner Gruppe als für ein schreiben, insb, für ein festes a.
Damit ergibt sich für die Gleichung.
Und das gibt eine Gleichung in den Exponenten die sich leicht lösen lässt.
NeFa3 Auf diesen Beitrag antworten »

Folgt daraus auch dass 2 mod 17 ist? Dann müsste ich nur verschiedene y zwischen 0 und 16 ausprobieren. Zumindest hab ich das jetzt so verstanden.
HAL 9000 Auf diesen Beitrag antworten »

Richtig, hier ist schlicht etwas Handarbeit nötig. Modul 17 ist klein genug, dass man das eben einfach mal tut:



D.h. jedem ist genau ein mit zugeordnet, auch diskreter Logarithmus genannt:



Wenn man will, kann man diese "Logarithmentafel" natürlich auch nach geordnet aufschreiben:



D.h. ist äquivalent zu , mit sowie ist daher zunächst die lineare Kongruenz zu lösen. Anschließend findet man via die gesuchte Lösung.
 
 
NeFa3 Auf diesen Beitrag antworten »

Das hab ich nicht so ganz verstanden. Wieso genau folgt, dass äquivalent zu ist? Die erste Tabelle gibt mir die Reste von mod 17 an. Demnach müsste y doch 14 sein oder? Wie folgere ich aus der ersten Tabelle, dass jedem x mod 17 genau ein y mod 16 zugeordnet wird?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von NeFa3
Wieso genau folgt, dass äquivalent zu ist?

Hast du den Kleinen Fermat verstanden? Und was eine Primitivwurzel ist?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »