Quadratische Kongruenzen

21.01.2009, 04:09

Bjoern1982

Quadratische Kongruenzen

Hallo,

ich soll alle Lösungen der folgenden beiden Kongruenzen angeben:

a) x²= 31 mod 77

b) x²= 53 mod 77

Durch die Berechnung des jeweiligen Jacobi Symbols bin ich zum Ergebnis gekommen, dass nur b) lösbar ist.

Wie ich nun an die Lösungen komme weiss ich leider nicht, getrennt modulo 7 und modulo 11 zu rechnen führt auch zu nichts - weiss jemand Rat ?

Gruß Björn

21.01.2009, 07:18

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
getrennt modulo 7 und modulo 11 zu rechnen führt auch zu nichts

Wieso nicht?

$\begin{eqnarray*} x^2 \equiv a \mod p \end{eqnarray*}$ hat für Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ sowie $\begin{eqnarray*} a\neq 0 \end{eqnarray*}$ entweder zwei oder gar keine Lösung. Bei so kleinen Modulen wie 7 oder 11 kann man die "von Hand" durch Probieren ermitteln.

Wenn es sowohl für p=7 als auch p=11 je zwei Lösungen hat, hast du dann die $\begin{eqnarray*} 4=2\cdot 2 \end{eqnarray*}$ Lösungen modulo 77, über den chinesischen Restsatz kommst du dann auch an die zugehörigen Darstellungen.

21.01.2009, 11:58

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

Bei so kleinen Modulen wie 7 oder 11 kann man die "von Hand" durch Probieren ermitteln.

Ok, das hatte ich nämlich schon gemacht, bin aber nur auf jeweils verschiedene Werte für x gekommen, was dann in meinen Augen zu "nichts führte" bzw ich dachte, dass wenn ich für x² = 4 mod 7 (x1=2 oder x2=5) und x²=9 mod 11 (x1=3 oder x2=8) keine gemeinsamen Lösungen erhalte, dass dann bedeuten würde, dass es gar keine Lösung modulo 77 gibt, was ja ein Widerspruch zu der Berechnung des Jacobi Symbols wäre.

Gut, du sprichst nun den CRS an - ich erkenne leider aber noch nicht wie dieser mir nu helfen kann, welches System simultaner Kongruenzen sprichst du an ?

Danke für die Hilfe smile

Gruß Björn

21.01.2009, 12:10

Auf diesen Beitrag antworten »

Na ich meine die vier Doppelkongruenzen

$\begin{eqnarray*} x \equiv 2 \mod 7, \; x\equiv 3 \mod 11 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv -2 \mod 7, \; x\equiv 3 \mod 11 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 2 \mod 7, \; x\equiv -3 \mod 11 \end{eqnarray*}$
$\begin{eqnarray*} x \equiv -2 \mod 7, \; x\equiv -3 \mod 11 \end{eqnarray*}$ ,

jede davon führt zu einer Lösung modulo 77. Selbstverstänlich genügt es, die ersten zwei zu lösen - durch Vorzeichenwechsel fallen dann die beiden anderen mit ab.

21.01.2009, 13:09

Bjoern1982

Auf diesen Beitrag antworten »

Wunderbar damit komme ich dann auf die beiden Lösungen 47 und 58.

Nochmal zur Sicherheit:

Das Modul ist hier ja nicht prim und insofern macht das Jacobi Symbol ja keine Aussage darüber, ob a nun QR ist oder nicht.
Jedoch kann man ja dann die Multiplikativität ausnutzen um dann (hier) 2 Jacobisymbole miteinander zu multiplizieren.

Bin ich da richtig vorgegangen ?

21.01.2009, 13:17

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Jedoch kann man ja dann die Multiplikativität ausnutzen um dann (hier) 2 Jacobisymbole miteinander zu multiplizieren.

Wie meinst du das in der konkret vorliegenden Situation verwirrt

21.01.2009, 13:20

Bjoern1982

Auf diesen Beitrag antworten »

Doch ich meinte es so wie vor deinem Edit Augenzwinkern

21.01.2009, 13:25

Auf diesen Beitrag antworten »

Ich zitiere mal aus dem Wikipedia-Eintrag:

Zitat:

Auszug aus http://de.wikipedia.org/wiki/Jacobi-Symbol:

Achtung: Falls $\begin{eqnarray*} n \end{eqnarray*}$ keine Primzahl ist, gibt das Jacobi-Symbol nicht an, ob $\begin{eqnarray*} a \end{eqnarray*}$ ein Quadratischer Rest modulo $\begin{eqnarray*} n \end{eqnarray*}$ ist (wie beim Legendre-Symbol). Eine notwendige Bedingung für $\begin{eqnarray*} a \end{eqnarray*}$ , ein quadratischer Rest modulo $\begin{eqnarray*} n \end{eqnarray*}$ zu sein, ist allerdings, dass das Jacobi-Symbol ungleich -1 ist.

Nehmen wir mal $\begin{eqnarray*} x^2\equiv 5\mod 77 \end{eqnarray*}$ . Dann sind beide Einzelkongruenzen $\begin{eqnarray*} x^2\equiv 5\mod 7 \end{eqnarray*}$ und $\begin{eqnarray*} x^2\equiv 5\mod 11 \end{eqnarray*}$ nicht lösbar, es gilt aber

$\begin{eqnarray*} \left( \frac{5}{77} \right) = \left( \frac{5}{7} \right) \cdot \left( \frac{5}{11} \right) = (-1) \cdot (-1) = 1 \end{eqnarray*}$ .

Das Nichtbestehen einer Einzelkongruenz reicht aus, um die Gesamtkongruenz unlösbar zu machen - das sollte auch ohne das Jacobi-Symbol-Brimborium klar sein.

21.01.2009, 13:35

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

Das Nichtbestehen einer Einzelkongruenz reicht aus, um die Gesamtkongruenz unlösbar zu machen - das sollte auch ohne das Jacobi-Symbol-Brimborium klar sein.

Genau das dachte ich mir gerade auch - das war wirklich Unsinn Hammer

Sprich mit diesem Symbol ist da (in diesem Fall) nichts bgzl der Lösbarkeit zu machen oder wie könnte ich bei "x²= 31 mod 77" noch argumentieren, dass es dafür keine Lösung gibt ?

21.01.2009, 13:36

Auf diesen Beitrag antworten »

Für $\begin{eqnarray*} x^2 \equiv 31 \mod 77 \end{eqnarray*}$ ist notwendig $\begin{eqnarray*} x^2 \equiv 3 \mod 7 \end{eqnarray*}$ , und die ist unlösbar.

21.01.2009, 13:38

Bjoern1982

Auf diesen Beitrag antworten »

Ich danke dir smile

Neue Frage »

Antworten »

Quadratische Kongruenzen

Verwandte Themen