Quadratischer Rest

06.06.2012, 11:19

q.R.

Quadratischer Rest

Meine Frage:
Man bestimme alle $\begin{eqnarray*} m\in \mathbb Z_{\geq 1} \end{eqnarray*}$ , für die $\begin{eqnarray*} x^{2}\equiv 5 mod m \end{eqnarray*}$ lösbar ist.

Meine Ideen:
Als Hinweis wurde uns gegeben, dass man zunächst die $\begin{eqnarray*} m\in \mathbb Z_{\geq 1} \end{eqnarray*}$ , in deren Primfaktorzerlegung die 5 nicht auftritt untersuchen soll.

06.06.2012, 11:25

Captain Kirk

Auf diesen Beitrag antworten »

Habt ihr das Legendre-Symbol bereits durchgenommen?

06.06.2012, 11:30

q.R

Auf diesen Beitrag antworten »

Ja, haben wir smile

06.06.2012, 11:36

Captain Kirk

Auf diesen Beitrag antworten »

Ja, dann betrachte $\begin{eqnarray*} m \not\equiv 0 \mod 5 \end{eqnarray*}$ .
Drücke durch das Legendre-Symbol aus wann ein solches x existiert und berechne das Legendre-Symbol. (mit ein paar Fallunterscheidungen)

06.06.2012, 11:47

q.R

Auf diesen Beitrag antworten »

Laut dem Legendre Symbol ist $\begin{eqnarray*} (\frac{5}{m} ) = 1 \end{eqnarray*}$ .
Das $\begin{eqnarray*} m \not\equiv 0 \mod 5 \end{eqnarray*}$ ist, ist klar, da sonst $\begin{eqnarray*} \frac{5}{m}= 0 \end{eqnarray*}$ wäre.

06.06.2012, 11:55

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Laut dem Legendre Symbol

Meinst du nicht eher quadratisches Reziprozitätsgesetz?

Zitat:

$\begin{eqnarray*} (\frac{5}{m} ) = 1 \end{eqnarray*}$ .

Nein.
z.B. ist $\begin{eqnarray*} (\frac{5}{7} ) = -1 \end{eqnarray*}$ . Ich hab nicht umsonst vorher was von Fallunterscheidungen geschrieben.

Nächster Schritt: Wie ist dieses Rechenergebnis zu interpretieren?

06.06.2012, 12:01

q.R

Auf diesen Beitrag antworten »

Das $\begin{eqnarray*} (\frac{5}{m} ) = 1 \end{eqnarray*}$ nicht für alle m gilt, war mir bewusst, da wir diese m ja bestimmen müssen. Ich dachte darauf beruht die Fallunterscheidung?
Aber wie komme ich auf die Fallunterscheidung?

06.06.2012, 12:08

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Laut dem Legendre Symbol ist $\begin{eqnarray*} (\frac{5}{m} ) = 1 \end{eqnarray*}$ .

Sollte dieser Satz also heißen:
Die Gleichung $\begin{eqnarray*} x^2 \equiv 5 \mod m \end{eqnarray*}$ ist lösbar, falls (gdw?) $\begin{eqnarray*} (\frac{5}{m} ) = 1 \end{eqnarray*}$ ist?
Dann musst du aber noch fordern, dass m prim ist. (Ansonsten haben wir das Jacobi-Symbol und da ist der Zusammenhang mit quadr. Rest nicht ganz so eindeutig)

Zitat:

Aber wie komme ich auf die Fallunterscheidung?

Auch wenn wir hier aneinander vorbeireden schmeiße ich doch bereits nur so mit Brotkrumen um mich:

Zitat:

quadratisches Reziprozitätsgesetz

und dann gilt's 4 Fälle zu unterscheiden.

06.06.2012, 12:16

q.R

Auf diesen Beitrag antworten »

Also bringt uns das Legendre Symbol hier nicht weiter, da m in unserem Fall nicht zwingend prim ist.
Wir haben in der Vorlesung gelernt, dass auch das quadratische Reziprozitätsgesetz nur für Primzahlen p und q gilt.
Ich habe das zumindest so verstanden, und das nur bei Jacobi alle Zahlen verwendet werden dürfen.

06.06.2012, 12:27

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Also bringt uns das Legendre Symbol hier nicht weiter, da m in unserem Fall nicht zwingend prim ist.

Möglichkeit 1: Ich hab dir hier die ganze Zeit Blödsinn erzählt und alles ist sinnlos. (Wobei deine Schlußfolgerung basiert wohl auf einen Hinweis von mir -> Logic-Bomb)
Möglichkeit 2: Nimm doch einfach mal an m wäre prim.
(Dann könntest du zumindest für einen nicht unwesentlichen Teil der natürlichen zahlen zeigen ob sie eine der gesuchten Zahlen ist oder nicht)

Zitat:

Wir haben in der Vorlesung gelernt, dass auch das quadratische Reziprozitätsgesetz nur für Primzahlen p und q gilt. Ich habe das zumindest so verstanden, und das nur bei Jacobi alle Zahlen verwendet werden dürfen.

Das q.R.-gesetz formuliert man normalerweise nur für zwei Primzahlen. Das heißt aber nicht, dass man es nicht schnell verallgemeinern kann. (Es reicht z.B. dass nu eines von p oder q prim ist.)

06.06.2012, 13:12

tmo

Auf diesen Beitrag antworten »

Noch eine Amerkung:

Wegen dem chin. Restsatz reicht es natürlich sich auf Primzahlpotenzen zu beschränken.

Und da reicht es sich für $\begin{eqnarray*} p \geq 3 \end{eqnarray*}$ wirklich nur auf p selbst zu beschränken, denn wegen $\begin{eqnarray*} (x^2-5)' = 2x \neq 0 \pmod p \end{eqnarray*}$

$\begin{eqnarray*} x^2 \equiv 5 \mod p \text{ lösbar} \Longleftrightarrow x^2 \equiv 5 \mod {p^n} \text{ lösbar für alle n} \end{eqnarray*}$ .

Zu untersuchen sind also alle Primzahlen mit dem Legendre-Symbol und danach die 2er-Potenzen gesondert.

PS: Wenn du diese Formulierung mit der Ableitung (Hensel-Lemma) nicht kennst, kannst du in diesem Fall auch explizit die Hinrichtung (Das ist ja die, die wir hier brauchen) schnell per Induktion zeigen. Da geht man im Schritt von einer Lösung - sagen wir x - mod $\begin{eqnarray*} p^n \end{eqnarray*}$ aus und setzt dann man mit $\begin{eqnarray*} (x+ap^n) \end{eqnarray*}$ als Lösung mod $\begin{eqnarray*} p^{n+1} \end{eqnarray*}$ an. Nach ein paar Umformungen sieht man direkt, dass es so ein a gibt.

06.06.2012, 15:39

q.R

Auf diesen Beitrag antworten »

Mir ist klar, wie ich das für einzelne Primzahlen prüfe. Aber wie prüfe ich das für jede beliebige Primzahl? Ich kann ja nicht jede Primzahl einzeln überprüfen. verwirrt

06.06.2012, 15:41

tmo

Auf diesen Beitrag antworten »

Das Stichwort "quadratisches Reziprozitätsgesetz" ist nun echt oft genug gefallen.

11.06.2012, 17:46

FeLa12

Auf diesen Beitrag antworten »

Hallo zusammen,

ich muss diese Aufgabe ebenfalls lösen.

Habe leider auch nicht ganz verstanden, was ihr meint. Aber ich habe eventuell noch einen anderen Weg gefunden und als Lösung $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ , $\begin{eqnarray*} \pm 9 \end{eqnarray*}$ , $\begin{eqnarray*} \pm 11 \end{eqnarray*}$ und $\begin{eqnarray*} \pm 19 \end{eqnarray*}$ für m raus.

Stimmt das? verwirrt

11.06.2012, 18:04

Captain Kirk

Auf diesen Beitrag antworten »

@FeLa12:
Wenn du die exakt selbe Aufgabe zu lösen hast, sind negative m als Lösung nicht zulässig.

Außerdem fehlen noch ziemlich viele m als Lösungen, z.B. 29, 59,...

Und da's anscheinend zu ungenau formuliert war von mir ein 4.Mal.

Berechne $\begin{eqnarray*} (\frac{5}{m}) \end{eqnarray*}$ mittels quadratischem Reziprozitätsgesetz.
Wie tmo schön ausgeführt hat genügt sich auf prime m zu beschränken.

Neue Frage »

Antworten »

Quadratischer Rest

Verwandte Themen