Quadratisches Reziprozitätsgesetz/Fakt mit Beweisklappe

Quadratisches Reziprozitätsgesetz

Es seien ${}p$ und ${}q$ verschiedene ungerade Primzahlen. Dann gilt:

${}\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}={\begin{cases}-1\,,{\text{ wenn }}p=q=3\mod 4\,,\\1\,,{\text{ sonst}}\,.\end{cases}}\,$

Beweis

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)}$, so dass 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, und ${}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.

$\Box$