Quadratisches Reziprozitätsgesetz/10 mod 13/Beispiel

Man möchte entscheiden, ob die Gleichung

x^{2} = 10 mod 13

eine Lösung besitzt. Dazu berechnet man

(\frac{10}{13}) = (\frac{2}{13}) (\frac{5}{13}) .

Der erste Faktor

(\frac{2}{13})

lässt sich mit Hilfe des zweiten Ergänzungssatzes zu $- 1$ bestimmen, weil $13 = 5 mod 8$ und dies das Vorzeichen $- 1$ ergibt.

Um den zweiten Faktor zu berechnen, wendet man das Reziprozitätsgesetz an:

(\frac{5}{13}) = + (\frac{13}{5}),

weil $5 mod 4 = 1$ gilt (der Rest $13 mod 4$ braucht gar nicht mehr berechnet zu werden, da es ausreicht, dass hier $5$ oder $13$ modulo $4$ den Rest $1$ lässt, damit das Vorzeichen $+$ ist). Jetzt nutzt man aus, dass $13 = 3 mod 5$ ist. Man schreibt:

(\frac{13}{5}) = (\frac{3}{5}) .

Wiederum wendet man hier das Quadratische Reziprozitätsgesetz an: Es ist

(\frac{3}{5}) = (\frac{5}{3}) = (\frac{2}{3}) = - 1,

da $5 mod 4 = 1$ ist und da $2 = - 1$ kein Quadrat modulo $3$ ist.

Setzt man nun beide Faktoren zusammen, so ergibt sich folgendes Resultat:

(\frac{10}{13}) = (\frac{2}{13}) (\frac{5}{13}) = (- 1) \cdot (- 1) = 1 .

Damit weiß man, dass die obige Gleichung eine Lösung besitzt (die beiden Lösungen lauten $6$ und $7$ ). Auf dieses Ergebnis kommt man leider nur durch Probieren. Hat man aber eine Lösung, z.B. die $6$ , so berechnet man die zweite Lösung, indem man das additive Inverse im Körper $ℤ / (13)$ bestimmt ( $13 - 6 = 7$ ).