x2≡(x−n)2(modn),0≤x≤n In practice, it suffices to restrict the range to 0<x≤⌊2n⌋ because of the symmetry in (x−n)2≡x2(modn): 1↦9(mod10) 2↦8(mod10) 3↦7(mod10) 4↦6(mod10) 5↦5(mod10) So for example, x:=3 in (mod10): 32≡(−7)2(mod10) 9≡49(mod10) Read more: [https://math.stackexchange.com/questions/1195366/all-the-solvable-congruences-x2-equiv-a-pmod-n-have-the-same-number-of-solu] [https://en.wikipedia.org/wiki/Quadratic_residue] [https://mathworld.wolfram.com/QuadraticResidue.html]