moduł kwadratu dwoch liczb

[wolk]

niech p bedzie liczba pierwsza \(\displaystyle{ P = \{0, 1, ..., p - 1\}}\).
Czy istnieja dwie rozne liczby \(\displaystyle{ k,j \in P}\), takie ze \(\displaystyle{ k^2 mod~p = j ^ 2 mod~p}\)?
Innymi slowy czy jezeli bede bral kolejne liczby ze zbioru P i obliczal modul ich kwadratu to czy po przeiterowaniu przez caly zbior P w wyniku otrzymam zbior P.

[Qń]

Tak, istnieją - dla dowolnego \(\displaystyle{ k \in P \backslash \{ 0 \}}\) mamy \(\displaystyle{ k^2 \equiv (p -k)^2 \mod p}\). W ogólności jest tak, że możliwymi resztami z dzielenia kwadratu liczby niepodzielnej przez \(\displaystyle{ p}\) (liczbę pierwszą nieparzystą) jest dokładnie połowa spośród liczb \(\displaystyle{ 1,2, \dots, p-1}\). Tęże połowę nazywa się resztami kwadratowymi, a drugą połowę nieresztami kwadratowymi (więcej np. w Arytmetyce teoretycznej Sierpińskiego). Np. dla \(\displaystyle{ p=3}\) resztą kwadratową jest \(\displaystyle{ 1}\), dla \(\displaystyle{ p=5}\) resztami kwadratowymi są \(\displaystyle{ 1}\) i \(\displaystyle{ 4}\), a dla \(\displaystyle{ p=7}\) resztami kwadratowymi są \(\displaystyle{ 1,2,4}\).

Q.