Prawo wzajemności reszt kwadratowych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Prawo wzajemności reszt kwadratowych – twierdzenie teorii liczb, które pozwala rozstrzygnąć, czy dana kongruencja stopnia 2 ma rozwiązanie. Prawo wzajemności udowodnił Gauss, choć znali je już Euler i Legendre.

Twierdzenie[edytuj | edytuj kod]

Niech p i q będą dwiema różnymi, nieparzystymi liczbami pierwszymi. Wynika stąd natychmiast, że p i q przystają modulo 4 albo do 1, albo do 3 – jeśli choć jedna z tych liczb przystaje do 1 modulo 4, to kongruencja

x^2\equiv p\ ({\rm mod}\ q)

ma rozwiązanie x wtedy i tylko wtedy, gdy kongruencja

y^2\equiv q\ ({\rm mod}\ p)

ma rozwiązanie y; na ogół rozwiązania te będą różne. Jeśli natomiast obie liczby p i q przystają do 3 modulo 4, to kongruencja

x^2\equiv p\ ({\rm mod}\ q)

ma rozwiązanie x wtedy i tylko wtedy, gdy kongruencja

y^2\equiv q\ ({\rm mod}\ p)

nie ma rozwiązania y.

Korzystając z symbolu Legendre'a

\left(\tfrac{p}{q}\right)=1 jeśli p jest resztą kwadratową modulo q i   -1 w przeciwnym wypadku,

oba stwierdzenia można zapisać następująco:

 \left(\tfrac{p}{q}\right) \left(\tfrac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}.

Ponieważ \tfrac{(p-1)(q-1)}{4} jest parzyste jeśli któraś z liczb p lub q przystaje do 1 modulo 4, i nieparzyste wtedy i tylko wtedy, gdy obie liczby p i q przystają do 3 modulo 4,  \left(\tfrac{p}{q}\right) \left(\tfrac{q}{p}\right) jest równe 1 jeśli któraś z liczb p lub q przystaje do 1 modulo 4 i –1 jeśli obie liczby p i q przystają do 3 modulo 4.

Ciekawy jest fakt, że znanych jest około 200 różnych dowodów prawa wzajemności reszt kwadratowych.