Quadratische Reste modulo 10^5 |
22.02.2010, 20:08 | mathe760 | Auf diesen Beitrag antworten » | ||||
Quadratische Reste modulo 10^5 ich habe hier eine kleine Aufgabe, von der ich gerade nicht weiß wie man sie löst: Zu bestimmen sind alle quadratischen Reste modulo 10^5 also alle Lösungen der Gleichung Ich wäre sehr froh über mögliche Lösungsansätze. Bis denn mathe760 |
||||||
23.02.2010, 11:06 | Reksilat | Auf diesen Beitrag antworten » | ||||
RE: Quadratische Reste modulo 10^5 Ich hab's mal den Rechner machen lassen. Der hat mir 9121 Reste ausgegeben. Meinst Du, dass das die Idee der Aufgabe war oder geht es vielleicht eher darum, zu einem festen Wert alle modulo verschiedenen Lösungen z bestimmen? Gruß, Reksilat. |
||||||
03.03.2010, 20:05 | mathe760 | Auf diesen Beitrag antworten » | ||||
Entschuldigung, dass ich mich lange nicht gemeldet habe. Also gut eigentlich reicht auch aus yu wissen ob 54321 quadratscher Rest ist, alternativ statt 54321 eine möglichst nah dran liegende Zahl. Ich weiß, dass man das über das Legendre-Symbol und dem quadratischem Reziprozitätsgesetzt ausrechnen kann, aber geht das auch anders? Bis denn mathe760 |
||||||
03.03.2010, 21:28 | AD | Auf diesen Beitrag antworten » | ||||
Klar ist . Ich nehme jetzt mal an, es geht dir nur um Werte , die zu (was gleichbedeutend ist mit "zu 10") teilerfremd sind? In dem Fall ist genau dann lösbar, wenn ; sowie genau dann lösbar, wenn lösbar ist, d.h. oder . Auf bezogen erkennt man und , daher ist dieses ein quadratischer Rest modulo . |
||||||
04.03.2010, 11:18 | Reksilat | Auf diesen Beitrag antworten » | ||||
Dass das nicht das gleiche ist, ist Dir jetzt aber hoffentlich klar. Gruß, Reksilat. |
||||||
04.03.2010, 11:32 | AD | Auf diesen Beitrag antworten » | ||||
Es ist auch ein Unterschied, ob man alle quadratischen Reste bestimmen soll, oder nur die Anzahl aller quadratischen Reste. |
||||||
Anzeige | ||||||
|
||||||
04.03.2010, 12:52 | Reksilat | Auf diesen Beitrag antworten » | ||||
@Arthur: Weiß ich ja, aber da es hier keine vernünftige Spoiler-Funktion gibt, wollte ich nicht alle Reste in den Thread schreiben. Letztlich war es ja klar, dass niemand in einer Übungsaufgabe eine Liste mit tausenden von Resten erwartet. btw.: Bei Deinem ersten Beitrag, Ende der vorletzten Zeile: reicht. @mathe760: Das Legendre-Symbol oder das QRG hätte Dir hier auch nicht geholfen, da diese nur quadratische Reste modulo Primzahlen behandeln. Gruß, Reksilat. |
||||||
04.03.2010, 17:32 | AD | Auf diesen Beitrag antworten » | ||||
Mal wieder ein Opfer des Copy+Paste - klar, der Exponent sollte dort weg sein. |
||||||
04.03.2010, 18:15 | mathe760 | Auf diesen Beitrag antworten » | ||||
Ok vielen Dank auch beiden, aber eines ist mir nocht nicht so ganz klar:
Wie genau kommt man darauf, kann man das nur "sehen" oder auch aus der gegebenen Kongruenz erschließen? \Edit: wie findet man denn die Lösung x der Kongruenz x²=54321 (mod 10^5)? Bis denn mathe760 |
||||||
04.03.2010, 18:38 | Reksilat | Auf diesen Beitrag antworten » | ||||
Meiner Meinung nach hat Arthur sowieso schon zu viel verraten - ein kleines Stück des Weges musst Du schon selbst ausfüllen. Da oben stehen doch zwei "genau dann wenn"-Behauptungen. Zumindest die eine Richtung sollte dabei problemlos zu machen sein. Und das:
hilft auch beim finden der Lösungen. Gruß, Reksilat. |
||||||
04.03.2010, 18:45 | AD | Auf diesen Beitrag antworten » | ||||
Na schau dich mal etwas um im Gebiet quadratischer Kongruenzen, da gibt es gewisse Sätze, die man nun (wie das Rad) nicht jedes Mal neu erfinden will. Als da wären:
Kern des Beweises ist die Konstruktion einer Lösung von aus einer bereits bekannten Lösung von . Dieser Gedanke erschließt dann auch gleich eine Berechnungsmöglichkeit der Lösungen, die zumindest für kleine und große ganz praktisch ist. @Reksilat Ich weiß nicht, ob ich zuviel verraten habe - jeder fängt ja mal klein an. |
||||||
04.03.2010, 19:50 | mathe760 | Auf diesen Beitrag antworten » | ||||
Ok vielen Dank nochmal, ich habe leider nicht ganz so ein großes Reservoir an Sätzen aus der Zahlentheorie auf die ich zurückgreifen kann. Ich werde dann jetzt mal eine Lösung herausfinden . Bis denn mathe760 |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|