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.