section_heading: Kvadratni ostatci po prostom modulu
paragraph_text: U tu svrhu, pretpostavimo da je <math>x^2 \equiv y^2 \pmod p.</math> Tada <math>p|(x - y)(x + y)</math> pa prema Euklidovoj lemi slijedi <math>p|x - y </math> ili <math>p|x + y.</math> No kako su <math>x, y \in \{1, 2, ..., p - 1\}</math> slijedi <math>x = y</math> ili <math> x + y = p</math> pa se kvadratni ostatak postiže točno dva puta.