quadratische reste

Neue Frage »

goe.alexander Auf diesen Beitrag antworten »
quadratische reste
Hallo,
ich möchte das Legendre Symbol für (707/1009) berechnen und hab ein problem damit herrauszufinden,
ob 707 quadratischer Rest mod 1009 ist.
Kann mir bitte jemand dabei helfen?
alex
therisen Auf diesen Beitrag antworten »

Hallo,

es gilt

Jetzt musst du versuchen, diese beiden Jacobi-Symbole zu berechnen. Schaffst du das?


Gruß, therisen
goe.alexander Auf diesen Beitrag antworten »

Tut mir leid aber das ist ja mein problem,
ich muß herrausfinden ob 7 bzw 101 quadratischer rest ist.
Die def. hierfür kenn ich, versteh sie aber nich.
"Ein a mit ggT(a,n) heißt quadratischer rest mod n wenn es ein
x²==a (mod n)"
Also können nur die quadratischer rest sein, die zu n prim sind. Leider ist mein n eine primzahl also gib es viele mögliche.
Eine erklärung am Beispiel von n=9 würde mir eventuell auch helfen:
warum sind 1,4 und 7 quadratische reste und 2,5,8 nicht?
AD Auf diesen Beitrag antworten »

Zitat:
Original von goe.alexander
Eine erklärung am Beispiel von n=9 würde mir eventuell auch helfen:
warum sind 1,4 und 7 quadratische reste und 2,5,8 nicht?

Einfach mal alle möglichen Quadrate modulo 9 aufschreiben:



Also sind 0, 1, 4, 7 quadratische Reste modulo 9, der Rest hingegen nicht, und das sind 2, 3, 5, 6, 8 .


EDIT: Sorry, ich sehe gerade, die zum Modul nicht teilerfremden Reste sollen nicht klassifiziert werden ... Ok, dann lassen wir eben 0, 3, 6 aus der obigen Aufzählung weg. Augenzwinkern
goe.alexander Auf diesen Beitrag antworten »

Also wenn ich das richtig verstehe, ist es im beispiel n=9 wie folgt:
(Da nur 1,2,4,5,7,8 als quadratische reste in frage kommen werden ich auch nur die betrachten)
1²=1 == 1 mod 9
2²=4 == 4 mod 9
4²=16 ==7 mod 9
5²=25 == 7 mod 9
8²=64 == 1 mod 9
weil alle nur kongruent 1,2,7 sind, sind das meine quadratischen reste?

Dann zur ursprünglichen Aufgabe:
(707/1009) = (7/1009)*(101/1009)
demnach müsste das Jacobi Symbol für (7/1009)= 1 sein, da
45² = 2025 == 7 mod 1009.
101 ist kein quadratischer rest (hab durch probieren nichts gefunden) und hätte das symbol -1.
Damit währen dann die jacobi symbole von
(7/1009)*(101/1009)=1*(-1)= -1 (was das Legendre symbol von 707/1009 ist)

Gibt es eine elegantere Art außer das "rumprobieren" beim finden eines quadratischen rest?
AD Auf diesen Beitrag antworten »

Zitat:
Original von goe.alexander
Gibt es eine elegantere Art außer das "rumprobieren" beim finden eines quadratischen rest?

Bei großen Zahlen zweifelsohne das quadratische Reziprozitätsgesetz von Gauß.

Zitat:
Original von goe.alexander
101 ist kein quadratischer rest (hab durch probieren nichts gefunden)

Nicht genug probiert:



Kommt natürlich auch mit dem quadratischen Reziprozitätsgesetz raus, dass 101 ebenfalls quadratischer Rest modulo 1009 ist.
 
 
goe.alexander Auf diesen Beitrag antworten »

Hallo nachma, vielen dank ersteimal.
Ich habe mir das Reziprozitätsgesetz angeschaut und bei wikipedia einen verweis auf ein einfacherres verfahren zur bestimmung des legendre symbols gefungen was ähnlich wie der euklidische algorthmuss funktionieren muss. Mehr steht leider nicht dabei. Weiß jemand wovon hier die rede ist?
AD Auf diesen Beitrag antworten »

Naja, auf der Basis des Reziprozitätsgesetzes eben: Für zwei ungerade Primzahlen kann man das ja umschreiben:



Wegen kann man nun den "Zähler" in reduzieren a la euklidischen Algorithmus...

Am besten am konkreten Beispiel hier mit und



Nun ist , also



Dem zweiten Ausdruck sieht man wegen sofort an, dass hier ein quadratischer Rest vorliegt. Eine andere Möglichkeit ist die Berechnung von über den 1.Ergänzungssatz zum Reziprozitätsgesetz - da kommt natürlich ebenfalls das raus:

Neue Frage »
Antworten »



Verwandte Themen

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