Reszta kwadratowa
Z Wikipedii
Reszta kwadratowa – liczbę całkowitą a nazywamy resztą kwadratową według modułu (lub: resztą kwadratową modulo) p jeżeli istnieje taka liczba całkowita x, że
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.
Spis treści |
[edytuj] Ważniejsze właściwości:
- 0 jest resztą kwadratową.
- 1 jest resztą kwadratową.
- Jeśli
i 
są resztami kwadratowymi, to 
też nią jest. - Jeśli
jest liczbą pierwszą to spośród elementów 
dokładnie połowa jest resztami kwadratowymi.
[edytuj] Dowód
- Oczywiste jest, że dla dowolnego n zachodzi
. Wobec tego 0 jest resztą kwadratową według modułu n. - Oczywiste jest też, że dla dowolnego n > 1 zachodzi
. Wobec tego 1 resztą kwadratową według modułu n. - do napisania
- Zauważmy, że dla dowolnej liczby naturalnej r z przedziału < 1,p − 1 > zachodzi wzór
. Stąd wniosek, że reszt kwadratowych modulo p jest w 
najwyżej połowa. Pokażemy, że dla dowolnej reszty kwadratowej k wyłącznie dwie powyższe liczby spełniają wzór 
. Załóżmy, że dwie liczby a2 i b2 z przystają do siebie modulo p. Wobec tego p | a2 − b2, skąd p | (a − b)(a + b), a zatem p | a − b lub p | a + b. Skoro 
, 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 
spełniają nasz wzór. Zatem reszt kwadratowych modulo p jest w dokładnie połowa.
[edytuj] Przykłady
- 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.
