Prawo wzajemności reszt kwadratowych


Prawo wzajemności reszt kwadratowych w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Twierdzenie | 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 p   ( m o d   q ) {\displaystyle x^{2}\equiv p\ ({\rm {mod}}\ q)}

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

y 2 q   ( m o d   p ) {\displaystyle 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 p   ( m o d   q ) {\displaystyle x^{2}\equiv p\ ({\rm {mod}}\ q)}

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

y 2 q   ( m o d   p ) {\displaystyle y^{2}\equiv q\ ({\rm {mod}}\ p)}

nie ma rozwiązania y.

Korzystając z symbolu Legendre’a

( p q ) = 1 {\displaystyle \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:

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

Ponieważ ( p 1 ) ( q 1 ) 4 {\displaystyle {\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, ( p q ) ( q p ) {\displaystyle \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.

Znanych jest 246 różnych dowodów prawa wzajemności reszt kwadratowych[1].

Przypisy | edytuj kod

  1. Proofs of the Quadratic Reciprocity Law
Na podstawie artykułu: "Prawo wzajemności reszt kwadratowych" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy