Verteilung der quadratischen Reste im Resklassensystem mod p (Primzahl)

Question

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:

X² - Y² = 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.

Answer 1

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$$

Comments

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.