potenzen in Z mod...

26.06.2007, 18:51

goe.alexander

potenzen in Z mod...

Hallo, ich hab eine frage:
wie finde ich harraus ob 709 eine 4. Potenz in Z mod 1741 ist?
Ich habe schon viel versucht und bin der meinung, dass es kein ist, aber sicher binn ich mir nicht. Gibt es ein Verfahren um das zu testen?
alex

26.06.2007, 19:05

Auf diesen Beitrag antworten »

Z.B. zweistufig: Erstmal überprüfen, ob 709 quadratischer Rest modulo 1741 ist. Falls nein, bist du fertig - keine Lösung.

Falls ja: Dann bestimme man eine Wurzel $\begin{eqnarray*} x \end{eqnarray*}$ von $\begin{eqnarray*} x^2\equiv 709\mod 1741 \end{eqnarray*}$ , die andere ist dann $\begin{eqnarray*} -x \end{eqnarray*}$ . Jetzt das Spiel von neuen: Überprüfe, ob $\begin{eqnarray*} x \end{eqnarray*}$ quadratischer Rest modulo 1741 ist...

Die Überprüfung von -x in der gleichen Richtung erübrigt sich, denn es ist ja $\begin{eqnarray*} -x=(-1)\cdot x \end{eqnarray*}$ und -1 ist bekanntermaßen quadratischer Rest modulo 1741, wegen $\begin{eqnarray*} 1741\equiv 1\mod 4 \end{eqnarray*}$ . Also sind $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} -x \end{eqnarray*}$ entweder beides quadratische Reste, oder beides quadratische Nichtreste.

P.S.: Natürlich klappt auch die Brute-Force-Methode: Einfach alle Werte $\begin{eqnarray*} z^4\mod 1741 \end{eqnarray*}$ für $\begin{eqnarray*} z=1,\ldots,870 \end{eqnarray*}$ durchklappern ... aber das hast du sicher nicht im Sinn. Augenzwinkern

26.06.2007, 19:57

goe.alexander

Auf diesen Beitrag antworten »

Um rauszfinden ob quadratischer rest, muss ich versuchen ob z.B.:
eine Wurzel exitiert von 709
wenn nicht, dann von 709 + 1741
wenn nicht, dann von 709 + 1741 + 1741 usw. oder?
(Die währen dann alle kongruent zu 709 mod 1741)
Das hab ich jetzt ma für ein paar gemacht und nix rausbekommen.
Gibts nen leichteren weg?

26.06.2007, 19:59

Auf diesen Beitrag antworten »

Gibt es - aber offenbar hast du Thread

quadratische reste

schon wieder vollständig aus dem Gedächtnis gestrichen. Schade!

26.06.2007, 20:31

goe.alexander

Auf diesen Beitrag antworten »

Dann starte ich einfach mal einen Versuch:
(nach dem Reziprozitätsgesetz)
Da 709 und 1741 ungerade primzahlen sind dürfte es anwendbar sein.

709/1741 = (-1)^((708/2)*(1740/2)) * 1741/709
= 1 * 1741/709

1749 = 2 * 709 + 323
709 = 2 * 323 + 63
323 = 5 * 63 + 8
63 = 7 * 8 + 7
8 = 1 * 7 + 1

Jetzt wirds kritisch: (1741/709) = (7/709) = (1/709) ?
Soweit richtig?

26.06.2007, 20:38

Auf diesen Beitrag antworten »

Zitat:

Original von goe.alexander
1749 = 2 * 709 + 323
709 = 2 * 323 + 63
323 = 5 * 63 + 8
63 = 7 * 8 + 7
8 = 1 * 7 + 1

Was soll das? Wir sind hier nicht beim euklidischen Algorithmus! Das Verfahren mag ähnlich sein, aber es ist nicht dasselbe. unglücklich

Die erste Zeile ist noch zu gebrauchen, die liefert nämlich

$\begin{eqnarray*} \left( \frac{1741}{709} \right) = \left( \frac{323}{709} \right) \end{eqnarray*}$

Dann geht's aber anders weiter: Bekanntlich gilt $\begin{eqnarray*} \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right) \end{eqnarray*}$ , es folgt also aus $\begin{eqnarray*} 323 = 17\cdot 19 \end{eqnarray*}$ :

$\begin{eqnarray*} \left( \frac{323}{709} \right) = \left( \frac{17}{709} \right) \cdot \left( \frac{19}{709} \right) \end{eqnarray*}$

usw.

EDIT: Hmmm, Ok, es geht wohl alternativ auch ohne die Primfaktorzerlegung $\begin{eqnarray*} 323=17\cdot 19 \end{eqnarray*}$ , nur dann mit dem Jacobi- statt Legendre-Symbol. Das ganze nützt aber nur was, wenn du die diversen laut Reziprozitätsgesetz entstehenden (oder eben nicht entstehenden) Vorzeichen auch mitführst, was du oben versäumt hast.

26.06.2007, 21:22

goe.alexander

Auf diesen Beitrag antworten »

Also in die nächste runde:

(323/709) = (17/703) * (19/709)

Zuerst 17/709
(-1)^((708/2)*(16/2) * 709/17 = 709/17 = 12/17 = 17/12 = 5/12
weil 709==12 mod 17 ; 17==5 mod 12
= -1

Jetzt 19/709
(-1)^((708/2)*(18/2)) * 709/19 = 709/19 = 6/19 = 19/6 = 1/6
weil 709==6 mod 19 ; 19==1 mod 6
= 1
Beide zusammen ergeben -1 was bedeuted, dass es kein Lösung gibt.

26.06.2007, 21:27

Auf diesen Beitrag antworten »

Das Ergebnis ist richtig, einige Umformungen sind aber zweifelhaft, z.B.

Zitat:

Original von goe.alexander
12/17 = 17/12

Mit welcher Begründung? Jedenfalls nicht über das (erweiterte) Reziprozitätsgesetz, da müssen beide Zahlen ungerade sein ...

26.06.2007, 21:36

goe.alexander

Auf diesen Beitrag antworten »

schonwieder ein fehler,
kann man dann schon bei 6/19 bzw 12/17 aufhören?
6 ist quadratischer rest von 19 => 1
12 ist kein quadratischer rest von 17 => -1
1*(-1) = -1
??

26.06.2007, 21:41

Auf diesen Beitrag antworten »

Zitat:

Original von goe.alexander
kann man dann schon bei 6/19 bzw 12/17 aufhören?

Nur, wenn du jetzt schon erkennst, ob es quadratische Reste/Nichtreste sind...

Die Zweien wirst du seriöserweise so los:

$\begin{eqnarray*} \left( \frac{12}{17} \right) = \left( \frac{2^2}{17} \right) \cdot \left( \frac{3}{17} \right) = \left( \frac{3}{17} \right) \end{eqnarray*}$

bzw.

$\begin{eqnarray*} \left( \frac{6}{19} \right) = \left( \frac{2}{19} \right) \cdot \left( \frac{3}{19} \right) = (-1)^{\frac{19^2-1}{8}}\cdot \left( \frac{3}{19} \right) \end{eqnarray*}$

(Ergänzungssatz zum Reziprozitätsgesetz).

Natürlich kannst du im Erfolgsfall (also quadratischer Rest) auch abkürzen, wenn du es siehst, wie z.B.

$\begin{eqnarray*} 6 \equiv 25 = 5^2\mod 19 \end{eqnarray*}$ .

Aber man kann auch stur wie oben vorgehen, bis zum Ende...

26.06.2007, 22:01

goe.alexander

Auf diesen Beitrag antworten »

okay habs verstanden, danke nochma und bis zum nächsten mal

Neue Frage »

Antworten »

potenzen in Z mod...

Verwandte Themen