Reszta kwadratowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Jeżeli nie jest resztą kwadratową według modułu p, to 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]

  1. 0 jest resztą kwadratową.
  2. 1 jest resztą kwadratową.
  3. Jeśli i są resztami kwadratowymi, to też nią jest.
  4. Jeśli jest liczbą pierwszą to spośród elementów dokładnie połowa jest resztami kwadratowymi.

Dowód[edytuj]

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

Przykłady[edytuj]

  • 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]