noxz.tech

Quadratic Residue

1 min read

x2≡(x−n)2(modn),0≤x≤n x^2 \equiv (x - n)^2 \pmod{n}, 0 \le x \le n

In practice, it suffices to restrict the range to 0<x≤⌊n2⌋0 \lt x \le \left\lfloor {n \over 2} \right\rfloor because of the symmetry in (x−n)2≡x2(modn)(x - n)^2 \equiv x^2 \pmod{n}:

1↦9(mod10) 1 \mapsto 9 \pmod{10}

2↦8(mod10) 2 \mapsto 8 \pmod{10}

3↦7(mod10) 3 \mapsto 7 \pmod{10}

4↦6(mod10) 4 \mapsto 6 \pmod{10}

5↦5(mod10) 5 \mapsto 5 \pmod{10}

So for example, x:=3x:=3 in (mod10)\pmod{10}:

32≡(−7)2(mod10) 3^2 \equiv (-7)^2 \pmod{10}

9≡49(mod10) 9 \equiv 49 \pmod{10}

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