Quadratic Residue | noxz.tech

 $x^{2} \equiv (x - n)^{2} (mod n), 0 \leq x \leq n$

In practice, it suffices to restrict the range to $0 < x \leq ⌊ \frac{n}{2} ⌋$ because of the symmetry in $(x - n)^{2} \equiv x^{2} (mod n)$ :

 $1 \mapsto 9 (mod 10)$

 $2 \mapsto 8 (mod 10)$

 $3 \mapsto 7 (mod 10)$

 $4 \mapsto 6 (mod 10)$

 $5 \mapsto 5 (mod 10)$

So for example, $x := 3$ in $(mod 10)$ :

 $3^{2} \equiv (- 7)^{2} (mod 10)$

 $9 \equiv 49 (mod 10)$