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={\left\{qi-pj\mid 1\leq i\leq t,\,1\leq j\leq u\right\}}\,.$

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\leq j=\left\lfloor {\frac {qi}{p}}\right\rfloor$  der Fall ist. Zu jedem ${}i$, ${}1\leq i\leq t$, gibt es also genau ${}\left\lfloor {\frac {qi}{p}}\right\rfloor$ Elemente in ${}M_{+}$. Damit hat ${}M_{+}$ genau

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

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

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

folgt.

Zur bewiesenen Aussage