Skip to main content
2 of 3
deleted 3 characters in body
Thomas
  • 7.5k
  • 1
  • 31
  • 44

Each root $r$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ has a ``conjugate'' root $-r \equiv n - r$ since trivially $(-r)^2 \equiv r^2 \pmod{n}$.

If there are exactly four roots (each prime factor generally brings in two roots, well, one root and its conjugate, and they generate the roots modulo $n$ via by CRT - see gammatester's answer below for more details) we have exactly two pairs of conjugate roots. In each pair exactly one root will be greater than $n/2$.

Thomas
  • 7.5k
  • 1
  • 31
  • 44