0 Daumen
432 Aufrufe

Aufgabe: Verteilung der quadratischen Reste mod p∈ℙ im Restklassensytem mod p: Zeige es gibt \( \frac{1}{4} \)*(p-4-(-1)(p-1)/2 ) viele Aufeinanderfolgende quadrartische Reste mod p. Also falls a und a+1 quadratische Reste sind, so ist das ein solches paar.


Problem/Ansatz: hab bisher leider nur:

X2 - Y2 = 1 mod p , Die Anzahl der Lösungen dieser Kongruenz müsste die gesuchte Anzahl sein. Komme aber leider nicht weiter :/

Freue mich über jede Hilfe.

Avatar von

1 Antwort

+2 Daumen
 
Beste Antwort

Man betrachtet die Summe

$$ \sum_{k=1}^{p-2} \left( 1 + \begin{pmatrix}k\\\hline p\end{pmatrix} \right) \left( 1 + \begin{pmatrix}k+1\\\hline p\end{pmatrix} \right)$$

Mit den Legendre Symbolen.

Der k-te Summand ist =4 wenn k und k+1 quadratische Reste mod p sind (beide Legendre Symbole sind hier = 1), ansonsten =0 (eines der beiden Legendre Symbole ist dann = -1)

Wenn wir also die Summe mal 1/4 betrachten erhalten wir die Anzahl der Paare $$ 0.25 \sum_{k=1}^{p-2} \left( 1 + \begin{pmatrix}k\\\hline p\end{pmatrix} \right) \left( 1 + \begin{pmatrix}k+1\\\hline p\end{pmatrix} \right) \\= 0.25 \sum_{k=1}^{p-2} 1 + \begin{pmatrix}k\\\hline p\end{pmatrix} + \begin{pmatrix}k+1\\\hline p\end{pmatrix} + \begin{pmatrix}k\\\hline p\end{pmatrix} \begin{pmatrix}k+1\\\hline p\end{pmatrix} $$ Du solltest wissen, dass $$ \sum_{k=1}^{p-1} \begin{pmatrix}k\\\hline p\end{pmatrix} = 0 $$
(Es gibt genauso viele quadratische Reste wie Nichtreste mod p)
Also vereinfacht sich die Summe $$ 0.25 \sum_{k=1}^{p-2} 1 + \begin{pmatrix}k\\\hline p\end{pmatrix} + \begin{pmatrix}k+1\\\hline p\end{pmatrix} + \begin{pmatrix}k\\\hline p\end{pmatrix} \begin{pmatrix}k+1\\\hline p\end{pmatrix} \\ = 0.25\left[ (p-2) - \begin{pmatrix}p-1\\\hline p\end{pmatrix} - \begin{pmatrix}1\\\hline p\end{pmatrix} + \sum_{k=1}^{p-2} \begin{pmatrix}k\\\hline p\end{pmatrix} \begin{pmatrix}k+1\\\hline p\end{pmatrix} \right] $$ Mit QRG beziehungsweise den Ergänzungssätzen:$$  = 0.25 \left[ p-3 - (-1)^{\frac{p-1}{2}} + \sum_{k=1}^{p-2} \begin{pmatrix}k\\\hline p\end{pmatrix} \begin{pmatrix}k+1\\\hline p\end{pmatrix} \right]$$

Jetzt muss man sich noch überlegen, warum $$ \sum_{k=1}^{p-2} \begin{pmatrix}k\\\hline p\end{pmatrix} \begin{pmatrix}k+1\\\hline p\end{pmatrix} =  \sum_{k=1}^{p-2} \begin{pmatrix}k(k+1)\\\hline p\end{pmatrix} = -1 $$ ist.

Dazu überlege man sich zuerst, dass

\( k(k+1) \) quadratischer Rest g.d.w. \( k^{-1}(k+1) \) quadratrischer Rest

Insbesondere ist dann

$$ \sum_{k=1}^{p-2} \begin{pmatrix}k(k+1)\\\hline p\end{pmatrix} = \sum_{x=1}^{p-2} \begin{pmatrix}1+x\\\hline p\end{pmatrix} = \sum_{x=2}^{p-1} \begin{pmatrix}x\\\hline p\end{pmatrix} = -\begin{pmatrix}1\\\hline p\end{pmatrix} = -1 $$

Avatar von 1,3 k

Danke für die ausführliche Antwort! im 2. Satz meinst du wahrscheinlich mod p :D


Und das k(k+1) quadratischer Rest gdw k-1(k-1) quadratischer Rest folgt wahrscheinlich aus k quadratischer Rest gdw inverses von k quadratischer Rest oder?

Danke für die ausführliche Antwort! im 2. Satz meinst du wahrscheinlich mod p :D

Jap, vertippt. Ist korrgiert.

Und das k(k+1) quadratischer Rest gdw k^(-1) (k-1) quadratischer Rest folgt wahrscheinlich aus k quadratischer Rest gdw inverses von k quadratischer Rest oder?

ja, zum Beispiel. Beide Terme unterscheiden sich einfach um ein Quadrat: \( k^2 \)

Zur letzen Zeile sollte ich evtl. noch sagen: statt \( k^{1}(k+1) = 1 + k^{-1} \) mit k=1,...,p-2 schreibe ich \( 1+x \) mit x=1,...p-2.

Das geht da eine Bijektion

$$ \mathbb F_p \backslash \{ 0, p-1 \} \to \mathbb F_p \backslash \{ 0, p-1\}, k \mapsto k^{-1} $$

existiert.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community