Quadratisches Reziprozitätsgesetz/Fakt/Beweis

Beweis

Es sei  $t=\frac{p-1}{2}$  und  $u=\frac{q-1}{2}$.  Nach Fakt  (3) gilt  $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{S(p,q)+S(q,p)}$,  sodass also  $tu=S(p,q)+S(q,p)$  zu zeigen ist. Betrachte

$M=\{qi-pj\mid 1\le i\le t,1\le j\le u\}.$

Diese Menge besitzt $tu$ Elemente. Es ist ferner  $0\notin M$,  da ja $p$ und $q$ teilerfremd sind. Es seien $M_{-}$ die negativen Elemente aus $M$ und $M_{+}$ die positiven Elemente aus $M$. Es ist  $qi-pj>0$  genau dann, wenn

$\frac{qi}{p}>j$

ist, was genau für  $1\le j=\lfloor \frac{qi}{p}\rfloor$  der Fall ist. Zu jedem $i$, $1\le i\le t$, gibt es also genau $\lfloor \frac{qi}{p}\rfloor$ Elemente in $M_{+}$. Damit hat $M_{+}$ genau

$\sum _{i=1}^t\lfloor \frac{qi}{p}\rfloor =S(q,p)$

Elemente. Die entsprechende Überlegung liefert, dass $M_{-}$ genau $S(p,q)$ Elemente besitzt, woraus

$tu=\mathrm{\#}\left(M\right)=\mathrm{\#}\left(M_{+}\right)+\mathrm{\#}\left(M_{-}\right)=S(q,p)+S(p,q)$

folgt.

Zur bewiesenen Aussage