Školjka

%V0 Pretpostavimo da neka dva kvadrata daju isti ostatak modulo $p$. $x^2 \equiv y^2 \pmod p$ $(x-y)(x+y)\equiv 0 \pmod p$ Da bi umozak dva broja bio djeljiv s prostim brojem $p$, barem jedan od njih mora biti djeljiv s $p$. Dakle ili vrijedi $x-y \equiv 0 \pmod p$ $x \equiv y \pmod p$ ili vrijedi $x+y \equiv 0 \pmod p$ $x \equiv -y \pmod p$ Dakle za svaki $x$ postoji tocno jedan broj $y$ koji daje razlicit ostatak pri djeljenju s $p$, ali ciji kvadrat daje isti ostatak. Naravno, moramo pipaziti na jednu iznimku, broj koji je djeljiv s $p$ ima svojstvo da je $x \equiv -x \pmod p$ (to jest $0 \equiv 0 \pmod p$). Dakle, brojevi djeljivi s $p$ nam daju jedan ostatak ($0$), a ostalih ima ukupno $p-1$, i svaki ima svog para s kojim daje isti ostatak. Dakle ukupno imamo $1+\frac {p-1}{2}=\frac{p+1}{2}$ mogucih kvadratnih ostataka.