Modulrechnung: Quadrat modulo einer Primzahl

01.06.2012, 13:37

Louis1991

Modulrechnung: Quadrat modulo einer Primzahl

Hallo,

Ich habe hier einen Beweis, in welchem mir eine gewisse Stelle etwas unklar ist. Ich ziehe mal die Stelle und alle dafür relevanten Informationen "raus":

Wir haben gezeigt: $\begin{eqnarray*} a \end{eqnarray*}$ ist eine ganze Zahl, $\begin{eqnarray*} z, x \in \mathbb{Q} \end{eqnarray*}$ und $\begin{eqnarray*} x \end{eqnarray*}$ ist kein Vielfaches von $\begin{eqnarray*} p \end{eqnarray*}$ , $\begin{eqnarray*} p \end{eqnarray*}$ ist Prim.

Außerdem gilt

$\begin{eqnarray*} z^2 - a x^2 \equiv 0 \end{eqnarray*}$ $\begin{eqnarray*} (mod p) \end{eqnarray*}$

Daraus soll folgen, dass a ein Quadrat modulo p ist, also

$\begin{eqnarray*} q^2 = a + p'p \end{eqnarray*}$

für irgendwelche $\begin{eqnarray*} q,p' \in \mathbb{Z} \end{eqnarray*}$ .

Meine Ideen.... :
Es gilt jedenfalls
$\begin{eqnarray*} \frac{z^2 + cp}{x^2}= a \end{eqnarray*}$
aber die beiden Zahlen auf der linken Seite (z^2/x^2 und cp/x^2) müssen ja erstmal leider keine integers sein.

Ich bin dankbar für jeden Tipp, Modulorechnung ist wohl schon eine Weile her, und ich weiß leider nicht so, was genau da gelten könnte, was mir hier auch noch weiterhilft.

lg
kai Wink

01.06.2012, 13:54

tmo

Auf diesen Beitrag antworten »

Multipliziere die Gleichung (in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ ) $\begin{eqnarray*} z^2-ax^2=cp \end{eqnarray*}$ doch einfach mit dem Quadrat des Nenners von x.

01.06.2012, 14:05

Louis1991

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Multipliziere die Gleichung (in $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ ) $\begin{eqnarray*} z^2-ax^2=cp \end{eqnarray*}$ doch einfach mit dem Quadrat des Nenners von x.

Hmm... ich wollte eigentlich noch dazuschreiben, dass ich o.B.d.A. davon ausgehen kann, dass z und x ganze Zahlen sind. Aber das hilft mir ja direkt auch nicht weiter, oder?

Beispiel:

$\begin{eqnarray*} 5^2 - 2 \cdot 3^2 = 1 \cdot 7 \end{eqnarray*}$

$\begin{eqnarray*} \frac{25}{9} - \frac{7}{9} = 2 \end{eqnarray*}$

Natürlich ist 2 ein Quadrat modulo 7 (und zwar 9), aber wie wird das aus der Gleichung jetzt klar?

01.06.2012, 14:15

tmo

Auf diesen Beitrag antworten »

Wenn es ganze Zahlen sind, dann geht es doch direkt:

Ist $\begin{eqnarray*} z^2-ax^2 \equiv 0 \pmod p \end{eqnarray*}$ , so ist $\begin{eqnarray*} a = (zx^{-1})^2 \pmod p \end{eqnarray*}$

$\begin{eqnarray*} x^{-1} \end{eqnarray*}$ existiert, da x kein Vielfaches von p ist...

01.06.2012, 14:18

Louis1991

Auf diesen Beitrag antworten »

Aber warum muss $\begin{eqnarray*} zx^{-1} \end{eqnarray*}$ eine ganze Zahl sein? Ich fordere ja oben, dass mein "q" eine ganze Zahl sein soll und das brauche ich später im Beweis auch. :/

E: Ein Beispiel dafür steht ja direkt oben, wo $\begin{eqnarray*} (zx^{-1}) ^2 = \frac{25}{9} \end{eqnarray*}$

01.06.2012, 14:24

tmo

Auf diesen Beitrag antworten »

Mit $\begin{eqnarray*} x^{-1} \end{eqnarray*}$ ist nicht die Inverse $\begin{eqnarray*} \frac{1}{x} \in \mathbb Q \end{eqnarray*}$ gemeint, sondern das Inverse in $\begin{eqnarray*} \mathbb Z/p\mathbb Z \end{eqnarray*}$ .

Wir rechnen also im Körper $\begin{eqnarray*} \mathbb Z/p\mathbb Z \end{eqnarray*}$ :

Dort gilt $\begin{eqnarray*} z^2-ax^2 = 0 \end{eqnarray*}$ und $\begin{eqnarray*} x \neq 0 \end{eqnarray*}$ . Nun formen wir um und erhalten gewünschtes.

01.06.2012, 14:26

Louis1991

Auf diesen Beitrag antworten »

Dann war das wohl, was mir im Punkte Modulrechnung gefehlt hat. Jetzt ist alles klar, danke! Freude

Neue Frage »

Antworten »

Modulrechnung: Quadrat modulo einer Primzahl

Verwandte Themen