Exactly two of the four roots must be greater than N/2 Theorem: Let $y$ be a quadratic residue in $\mathbb{Z}_N$* where $N=pq$.

There are exactly four integers $x_1, x_2, x_3, x_4$ where $0 &lt; x_1 &lt; x_2 &lt; \frac{N}{2} &lt; x_3 &lt; x_4 &lt; N$ such that $y = x_i^2 \pmod{N}$ for $i=1,2,3,4$.

The above theorem simply states that exactly two of the four roots must be greater than $\frac{N}{2}$. 

Most papers will say that this result is well known, without providing any detailed proof. How can we prove that $0 &lt; x_1 &lt; x_2 &lt; \frac{N}{2} &lt; x_3 &lt; x_4 &lt; N$?
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$.

By simple arithmetic, one can see that $r &lt; n/2 \iff n-r &gt; n/2$.  Thus, assuming that $n$ is odd (which rules out the possibility that $r = n/2$), it follows that exactly one of each conjugate pair of roots is grater than $n/2$.