Beweis Anzahl der Lösungen einer Gleichung mit modulo

05.04.2012, 12:18	xlynax	Auf diesen Beitrag antworten »
Beweis Anzahl der Lösungen einer Gleichung mit modulo Meine Frage: Hallo, ich habe mal wieder ein Problem bei einem Beweis mit modulo: Und zwar soll ich beweisen, dass die Anzahl der Lösungen von $\begin{eqnarray} x^{2}-y^{2} \equiv a (mod\ p) \\ \end{eqnarray}$ mit $\begin{eqnarray} p \end{eqnarray}$ prim durch $\begin{eqnarray} \sum \limits_{y=0}^{p-1} (1+(y^{2}+a)) \end{eqnarray}$ gegeben ist. Meine Ideen: Ich habe mir gedacht, ich betrachte ein festes $\begin{eqnarray} y \end{eqnarray}$ zwischen 0 und p-1. Dann habe ich die Gleichung $\begin{eqnarray} x^{2}\equiv y^{2}+ a (mod\; p) \\ \end{eqnarray}$ , wobei die rechte Seite eine feste Zahl ist. Jetzt muss ich zeigen, dass ich für $\begin{eqnarray} \ x\\ \end{eqnarray}$ $\begin{eqnarray} (1+(y^{2}+a)) \end{eqnarray}$ Wahlmöglichkeiten habe und da liegt das Problem. Ich habe keine Ahnung, wie ich das machen soll... Wenn ich das gezeigt habe muss ich ja nur noch über alle möglichen $\begin{eqnarray} y \end{eqnarray}$ summieren. Schonmal vielen Dank!
05.04.2012, 20:41	HAL 9000	Auf diesen Beitrag antworten »
Da gibt es aber ein kleines Problem: Die Gleichung $\begin{eqnarray} x^2 \equiv y^2+a \bmod p \end{eqnarray}$ hat im Fall $\begin{eqnarray} y^2+a\not\equiv 0\bmod p \end{eqnarray}$ entweder keine oder genau zwei $\begin{eqnarray} x \end{eqnarray}$ -Lösungen. Insofern kann man deine Behauptung einfach nur als falsch bezeichnen.
05.04.2012, 20:57	xlynax	Auf diesen Beitrag antworten »
Hmmm.... Also ist der Ansatz komplett falsch? Hast du einen Tipp, wie ich dann beginnen kann?
05.04.2012, 21:00	HAL 9000	Auf diesen Beitrag antworten »
Was beginnen? Nach dem, was ich gesagt habe, genügt es, ein einziges Gegenbeispiel $\begin{eqnarray} p,a \end{eqnarray}$ anzugeben, schon ist die Behauptung widerlegt - und das sollte nicht allzu schwer zu finden sein. Es sei denn, du hast dich irgendwo arg verschrieben - vielleicht sollen ja in der Summe Legendre-Symbole stehen o.ä.? EDIT: Ok, mal Butter bei die Fische. Wenn da stattdessen $\begin{eqnarray} \sum \limits_{y=0}^{p-1} \left( 1+ \left( \frac{y^2+a}{p} \right) \right) \end{eqnarray}$ stehen würde, wobei man unter $\begin{eqnarray} \left( \frac{y^2+a}{p} \right) \end{eqnarray}$ ein Legendre-Symbol versteht, dann wäre das als Lösungsanzahlformel durchaus richtig. Der Beweis dessen ergibt sich dann unmittelbar aus der Definition des Legendre-Symbols, ohne die geringste Schwierigkeit. Daher nehme ich an, dass eigentlich dies gemeint war.
05.04.2012, 21:26	xlynax	Auf diesen Beitrag antworten »
Oh Mann!!! Gut, dass ich die Aufgabe hier gestellt habe. Denn sonst hätte ich noch ewig daran rumprobiert. Der Prof hat die Aufgabe für den Übungszettel falsch aus dem Buch abgeschrieben!!! Ich hab da jetzt mal nachgeschaut. Richtig lautet die Summe: $\begin{eqnarray} \sum_{y=0}^{p-1} (1+ (\frac{y^2+a}{p})) \end{eqnarray}$ Und du hattest Recht mit dem Legendresymbol. Ich weiß allerdings nicht, ob mich das viel weiterbringt, da ich das Legendresymbol noch nicht so ganz verstanden habe. Nach der Definition, die wir hatten, wäre in diesem Fall $\begin{eqnarray} (\frac{y^2+a}{p})=1 \end{eqnarray}$ wenn $\begin{eqnarray} y^2+a \end{eqnarray}$ quadratischer Rest modulo p ist $\begin{eqnarray} (\frac{y^2+a}{p})=0 \end{eqnarray}$ wenn $\begin{eqnarray} p\|(y^2+a) \end{eqnarray}$ $\begin{eqnarray} (\frac{y^2+a}{p})=-1 \end{eqnarray}$ wenn $\begin{eqnarray} y^2+a \end{eqnarray}$ quadratischer Nichtrest modulo p ist Wieso jetzt für ein festes y die Anzahl der Lösungen durch $\begin{eqnarray} (1+ (\frac{y^2+a}{p})) \end{eqnarray}$ gegeben ist (ich kann doch jetzt so beginnen?), ist mir nicht klar.
05.04.2012, 21:29	HAL 9000	Auf diesen Beitrag antworten »
Mein EDIT hat sich wohl mit deinem letzten Beitrag überkreuzt - mir war inzwischen dieselbe Idee gekommen. Wie gesagt, der Beweis beinhaltet dann eigentlich keine Schwierigkeiten, wenn man sich nur die Defintion des Legendre-Symbols genau anschaut.
Anzeige

05.04.2012, 21:53	xlynax	Auf diesen Beitrag antworten »
Ja, da haben sich unsere Beiträge echt überschnitten Und jetzt habe ich es auch verstanden.Die Aussage folgt ja dann wirklich einfach aus der Definition. Nochmal herzlichen Dank, dass du mich auf den Fehler in der Aufgabe aufmerksam gemacht hast. Ich hätte wahrscheinlich noch stundenlang weiter daran rumprobiert...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »