MetaMath '22

Definirajmo cijeli broj $m$ kao \textit{kvadratni ostatak modulo n} ako postoji cijeli broj $a$ takav da je $a^2 \equiv m (mod \, n)$. Dokažimo za neparan prosti broj $p$ postoji točno $\frac{p+1}{2}$ kvadratnih ostataka modulo $p$. \textbf{Rješenje:} Najprije primijetimo da je $0$ očito uvijek kvadratni ostatak jer je, primjerice, $p^2$ uvijek djeljiv s $p$. Neka je sada $1 \leq m \leq p-1$. Primijetimo da je $m^2 \equiv m^2 + p(p-2m) \equiv p^2 - 2pm +m^2 \equiv (p-m)^2 (mod \, n).$ Dakle, kvadrati od $m$ i $p-m$ daju jednake ostatke modulo $p$, za svaki promatrani $m$, što znači da možemo imati maksimalno $\frac{p-1}{2}$ kvadratnih ostataka u skupu $\{1,...,p-1\}$. S druge strane, pretpostavimo da su $1 \leq m,n \leq p-1$ takvi da je $m^2 \equiv n^2 (mod \, p)$. U tom je slučaju $(m-n)(m+n) \equiv 0 (mod \, p)$, tj neki od brojeva $m-n$ i $m+n$ je djeljiv s $p$. To onda implicira da vrijedi ili $m \equiv n (mod \, p)$ ili $m \equiv p-n (mod p)$. Dakle, svaki od $\frac{p-1}{2}$ parova ostataka $\{m, p-m\}$ iz skupa $\{1,...,p-1\}$ daje različite kvadratne ostatke module $p$ pa ih zaista ima točno $\frac{p-1}{2}$. Kao rješenje primjera, navedite koliko kvadratnih ostataka ima jedini prosti broj kojeg nismo pokrili ovim teoremom.