Reszta kwadratowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Reszta kwadratowaliczbę całkowitą a nazywamy resztą kwadratową według modułu (lub: resztą kwadratową modulo) p jeżeli istnieje taka liczba całkowita x, że

x^2\equiv a\,\pmod{p}

Jeżeli a nie jest resztą kwadratową według modułu p, to a nazywamy nieresztą kwadratową.

Reszty kwadratowe są zatem liczbami, dla których istnieją pierwiastki stopnia 2 względem kongruencji modulo p.

Prawo wzajemności reszt kwadratowych dostarcza wielu informacji o resztach kwadratowych i liczbach pierwszych.

Ważniejsze właściwości[edytuj | edytuj kod]

  1. 0 jest resztą kwadratową.
  2. 1 jest resztą kwadratową.
  3. Jeśli a_1=b_1^2 i a_2=b_2^2 są resztami kwadratowymi, to a_1a_2=(b_1b_2)^2\; też nią jest.
  4. Jeśli p>2\; jest liczbą pierwszą to spośród elementów 1,2,\dots p-1 dokładnie połowa jest resztami kwadratowymi.

Dowód[edytuj | edytuj kod]

  1. Oczywiste jest, że dla dowolnego n zachodzi 0^2 \equiv 0 \mod n. Wobec tego 0 jest resztą kwadratową według modułu n.
  2. Oczywiste jest też, że dla dowolnego n>1 zachodzi 1^2 \equiv 1 \mod n. Wobec tego 1 resztą kwadratową według modułu n.
  3. do napisania
  4. Zauważmy, że dla dowolnej liczby naturalnej r z przedziału <1,p-1> zachodzi wzór r^2 \equiv (p-r)^2 \mod p. Stąd wniosek, że reszt kwadratowych modulo p jest w \{1,\,2,\ldots,p-1\} najwyżej połowa. Pokażemy, że dla dowolnej reszty kwadratowej k wyłącznie dwie powyższe liczby spełniają wzór x^2 \equiv k \mod p. Załóżmy, że dwie liczby a^2 i b^2 z \{1,\,2,\ldots,p-1\} przystają do siebie modulo p. Wobec tego p|a^2-b^2, skąd p|(a-b)(a+b), a zatem p|a-b lub p|a+b. Skoro 1 \leqslant a,b<p, to z pierwszej możliwości wynika a-b=0, czyli a=b. W drugim przypadku otrzymujemy a+b=p, a więc b=p-a. Innych możliwości nie ma, wobec czego tylko dwie liczby a,\,p-a spełniają nasz wzór. Zatem reszt kwadratowych modulo p jest w \{1,\,2,\ldots,p-1\} dokładnie połowa.

Przykłady[edytuj | edytuj kod]

  • Kwadrat dowolnej liczby całkowitej kończy się jedną z cyfr: 0, 1, 4, 5, 6, 9. Oznacza to, że liczby te są resztami kwadratowymi modulo 10. Liczby 2, 3, 7 i 8 są nieresztami modulo 10.
  • Resztami kwadratowymi modulo 8 są liczby 0, 1 i 4. Nieresztami są liczby 2, 3, 5, 6, 7. Wynika stąd, że kwadrat dowolnej liczby nieparzystej daje z dzielenia przez 8 resztę 1.

Zobacz też[edytuj | edytuj kod]