Quadratische Reste modulo 10^5

22.02.2010, 20:08

mathe760

Quadratische Reste modulo 10^5

Hallo,

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

$\begin{eqnarray*} x^2\equiv a (mod 10^5) \end{eqnarray*}$

Ich wäre sehr froh über mögliche Lösungsansätze.

Bis denn mathe760 Wink

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. Augenzwinkern

Meinst Du, dass das die Idee der Aufgabe war oder geht es vielleicht eher darum, zu einem festen Wert $\begin{eqnarray*} a \end{eqnarray*}$ alle modulo $\begin{eqnarray*} 10^5 \end{eqnarray*}$ 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 Wink

03.03.2010, 21:28

Auf diesen Beitrag antworten »

Klar ist

$\begin{eqnarray*} x^2 \equiv a \bmod 10^5 \quad \Leftrightarrow\quad \left( x^2 \equiv a \bmod 2^5 \,\wedge\, x^2 \equiv a \bmod 5^5 \right) \end{eqnarray*}$ .

Ich nehme jetzt mal an, es geht dir nur um Werte $\begin{eqnarray*} a \end{eqnarray*}$ , die zu $\begin{eqnarray*} 10^5 \end{eqnarray*}$ (was gleichbedeutend ist mit "zu 10") teilerfremd sind?

In dem Fall ist $\begin{eqnarray*} x^2 \equiv a \bmod 2^5 \end{eqnarray*}$ genau dann lösbar, wenn $\begin{eqnarray*} a\equiv 1\mod 8 \end{eqnarray*}$ ; sowie $\begin{eqnarray*} x^2 \equiv a \bmod 5^5 \end{eqnarray*}$ genau dann lösbar, wenn $\begin{eqnarray*} x^2 \equiv a \bmod 5 \end{eqnarray*}$ lösbar ist, d.h. $\begin{eqnarray*} a\equiv 1\mod 5 \end{eqnarray*}$ oder $\begin{eqnarray*} a\equiv 4\bmod 5^5 \end{eqnarray*}$ .

Auf $\begin{eqnarray*} a=54321 \end{eqnarray*}$ bezogen erkennt man $\begin{eqnarray*} a\equiv 1\bmod 8 \end{eqnarray*}$ und $\begin{eqnarray*} a\equiv 1\bmod 5 \end{eqnarray*}$ , daher ist dieses $\begin{eqnarray*} a \end{eqnarray*}$ ein quadratischer Rest modulo $\begin{eqnarray*} 10^5 \end{eqnarray*}$ .

04.03.2010, 11:18

Reksilat

Auf diesen Beitrag antworten »

Zitat:

Zu bestimmen sind alle quadratischen Reste modulo 10^5

Zitat:

Also gut eigentlich reicht auch aus zu wissen ob 54321 quadratscher Rest ist.:

Dass das nicht das gleiche ist, ist Dir jetzt aber hoffentlich klar. smile

Gruß,
Reksilat.

04.03.2010, 11:32

Auf diesen Beitrag antworten »

Es ist auch ein Unterschied, ob man alle quadratischen Reste bestimmen soll, oder nur die Anzahl aller quadratischen Reste. Augenzwinkern

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: $\begin{eqnarray*} a\equiv 4\bmod 5 \end{eqnarray*}$ 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

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat
btw.: Bei Deinem ersten Beitrag, Ende der vorletzten Zeile: $\begin{eqnarray*} a\equiv 4\bmod 5 \end{eqnarray*}$ reicht.

Mal wieder ein Opfer des Copy+Paste - klar, der Exponent sollte dort weg sein. Augenzwinkern

04.03.2010, 18:15

mathe760

Auf diesen Beitrag antworten »

Ok vielen Dank auch beiden, aber eines ist mir nocht nicht so ganz klar:

Zitat:

In dem Fall ist $\begin{eqnarray*} x^2 \equiv a \bmod 2^5 \end{eqnarray*}$ genau dann lösbar, wenn $\begin{eqnarray*} a\equiv 1\mod 8 \end{eqnarray*}$ ; sowie $\begin{eqnarray*} x^2 \equiv a \bmod 5^5 \end{eqnarray*}$ genau dann lösbar, wenn $\begin{eqnarray*} x^2 \equiv a \bmod 5 \end{eqnarray*}$ lösbar ist

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 Wink

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. Augenzwinkern

Da oben stehen doch zwei "genau dann wenn"-Behauptungen. Zumindest die eine Richtung sollte dabei problemlos zu machen sein.

Und das:

Zitat:

$\begin{eqnarray*} x^2 \equiv a \bmod 10^5 \quad \Leftrightarrow\quad \left( x^2 \equiv a \bmod 2^5 \,\wedge\, x^2 \equiv a \bmod 5^5 \right) \end{eqnarray*}$

hilft auch beim finden der Lösungen.

Gruß,
Reksilat.

04.03.2010, 18:45

Auf diesen Beitrag antworten »

Zitat:

Original von mathe760
Wie genau kommt man darauf, kann man das nur "sehen" oder auch aus der gegebenen Kongruenz erschließen?

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:

Zitat:

Es sei $\begin{eqnarray*} a \end{eqnarray*}$ nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar.

Für $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ sowie Primzahlen $\begin{eqnarray*} p>2 \end{eqnarray*}$ ist dann $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} p^k \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} p \end{eqnarray*}$ ist.

Im Sonderfall $\begin{eqnarray*} p=2 \end{eqnarray*}$ verhält es sich etwas anders: Dort ist für $\begin{eqnarray*} k\geq 3 \end{eqnarray*}$ die Zahl $\begin{eqnarray*} a \end{eqnarray*}$ quadratischer Rest modulo $\begin{eqnarray*} p^k \end{eqnarray*}$ genau dann wenn $\begin{eqnarray*} a\equiv 1\bmod 8 \end{eqnarray*}$ gilt. Die Fälle $\begin{eqnarray*} k=1,k=2 \end{eqnarray*}$ kannst du dir getrost selbst überlegen.

Kern des Beweises ist die Konstruktion einer Lösung $\begin{eqnarray*} x' \end{eqnarray*}$ von $\begin{eqnarray*} x'^2\equiv a\bmod p^k \end{eqnarray*}$ aus einer bereits bekannten Lösung $\begin{eqnarray*} x \end{eqnarray*}$ von $\begin{eqnarray*} x^2\equiv a \bmod p^{k-1} \end{eqnarray*}$ . Dieser Gedanke erschließt dann auch gleich eine Berechnungsmöglichkeit der Lösungen, die zumindest für kleine $\begin{eqnarray*} p \end{eqnarray*}$ und große $\begin{eqnarray*} k \end{eqnarray*}$ ganz praktisch ist.

@Reksilat

Ich weiß nicht, ob ich zuviel verraten habe - jeder fängt ja mal klein an. Augenzwinkern

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. unglücklich

Ich werde dann jetzt mal eine Lösung herausfinden smile

.

Bis denn mathe760 Wink

Neue Frage »

Antworten »

Quadratische Reste modulo 10^5

Verwandte Themen