Kongruenz mittels Primitivwurzeln lösen

07.05.2018, 13:46

SoulOfMidgard

Kongruenz mittels Primitivwurzeln lösen

Meine Frage:
Ich soll die Kongruenz x^7=1 mod 29 lösen.

Meine Ideen:
Es ist (alles in mod 29) 2^28=1 und 2^28=(2^7)^4=1^4, also 2^7=12 eine Lösung. Wie finde ich nun aber alle weiteren oder Zeige dass es keine weiteren gibt?

07.05.2018, 14:04

HAL 9000

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} g \end{eqnarray*}$ Primitivwurzel modulo 29. Dann ist $\begin{eqnarray*} x=g^k \end{eqnarray*}$ genau dann Lösung von $\begin{eqnarray*} x^7\equiv 1\bmod 29 \end{eqnarray*}$ , wenn $\begin{eqnarray*} g^{7k}\equiv 1\bmod 29 \end{eqnarray*}$ , und das ist gleichbedeutend mit $\begin{eqnarray*} 7k\equiv 0\bmod 28 \end{eqnarray*}$ , umgestellt $\begin{eqnarray*} k\equiv 0\bmod 4 \end{eqnarray*}$ ...

Zitat:

Original von SoulOfMidgard
und 2^28=(2^7)^4=1^4, also 2^7=12 eine Lösung.

Nein, nicht $\begin{eqnarray*} 2^7 \end{eqnarray*}$ , sondern $\begin{eqnarray*} 2^4=16 \end{eqnarray*}$ ist eine Lösung. unglücklich

09.05.2018, 10:10

SoulOfMidgard

Auf diesen Beitrag antworten »

Okay das würde ich vermutlich dann mithilfe des chinesischen Restsatzes lösen nehme ich an? Klingt logisch. Mein Problem ist nur, dass ich explizit dazu aufgefordert bin zu verwenden, dass 2 eine Primitivwurzel modulo 29 ist. Das würde ich bei einem Beweis dieser Form nicht machen. Eine Idee zu dieser speziellen Herangehensweise?

Und ja damit hast du natürlich rechst, dass habe ich verdreht.

09.05.2018, 10:13

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von SoulOfMidgard
Mein Problem ist nur, dass ich explizit dazu aufgefordert bin zu verwenden, dass 2 eine Primitivwurzel modulo 29 ist. Das würde ich bei einem Beweis dieser Form nicht machen.

Zitat:

Original von SoulOfMidgard
Eine Idee zu dieser speziellen Herangehensweise?

Ja: $\begin{eqnarray*} g=2 \end{eqnarray*}$ , und dann genau wie oben.

09.05.2018, 10:18

SoulOfMidgard

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Sei $\begin{eqnarray*} g \end{eqnarray*}$ Primitivwurzel modulo 29. Dann ist $\begin{eqnarray*} x=g^k \end{eqnarray*}$ genau dann Lösung von $\begin{eqnarray*} x^7\equiv 1\bmod 29 \end{eqnarray*}$ , wenn $\begin{eqnarray*} g^{7k}\equiv 1\bmod 29 \end{eqnarray*}$ , und das ist gleichbedeutend mit $\begin{eqnarray*} 7k\equiv 0\bmod 28 \end{eqnarray*}$ , umgestellt $\begin{eqnarray*} k\equiv 0\bmod 4 \end{eqnarray*}$ ...

Also mein Prof verlangt von mir eben explizit dass ich diese Aufgabe löse indem ich verwende dass 2 eine Primitivwurzel mod 29 ist.

Würde ich den Beweis so durchführen würde ich ja zu keinem Zeitpunkt 2 als Primitivwurzel nutzen oder verstehe ich das falsch?

09.05.2018, 10:28

HAL 9000

Auf diesen Beitrag antworten »

Ich sehe die Probleme nicht, die du da herbeireden willst:

Du musst doch nach den Ausführungen oben jetzt lediglich noch die Werte $\begin{eqnarray*} 2^k\bmod 29 \end{eqnarray*}$ für alle durch vier teilbaren $\begin{eqnarray*} k \end{eqnarray*}$ bestimmen, als da wären $\begin{eqnarray*} k=0,4,8,12,16,20,24 \end{eqnarray*}$ , was insgesamt sieben Lösungen der Kongruenz ergibt.

09.05.2018, 10:33

SoulOfMidgard

Auf diesen Beitrag antworten »

Ich will nicht sagen, dass der Beweis nicht funktioniert. Weil ganz offensichtlich tut er das ja, dass will ich gar nicht abstreiten. Jedoch muss ich wie gesagt die Kongruenz x^7=1 lösen, indem ich verwende dass 2 eine Primitivwurzel mod 29 ist und das tue ich ja mit dieser Art Beweis nicht. Was ich versuche zu fragen ist ob es einen äquivalenten Beweis gibt der die Primitivwurzel 2 zur Lösung benutzt?

Also wie ich es in der ursprünglichen Frage angedeutet hatte nutze ich ja 2 als Primitivwurzel um (2^4)^7 als Lösung der Kongruenz zu zeigen. Kann ich von diesem Wissen auf alle anderen Lösungen schliessen?

09.05.2018, 11:30

SoulOfMidgard

Auf diesen Beitrag antworten »

Ich war so verwirrt. Natürlich haben Sie Recht. Bitte entschuldigen Sie meine Verwirrung! Ich sehe es jetzt. Vielen Dank!

Neue Frage »

Antworten »

Kongruenz mittels Primitivwurzeln lösen

Verwandte Themen