# 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 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < 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 < x_1 < x_2 < \frac{N}{2} < x_3 < x_4 < N$?

• This can easily be proven by the fact that with a square root $a$, there is also a square root $-a$. And if you look at this pair, one will be between 0 and $N/2$ and the other one between $N/2$ and $N$. – tylo Jul 1 '14 at 10:50
• @tylo This is basically what my answer says... – Thomas Jul 1 '14 at 10:55

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 < n/2 \iff n-r > 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$.

• But, how we know for sure in each pair exactly one root will be greater than n/2. I;m sorry since i couldnt understand your point. For me, 'In each pair exactly one root will be greater than n/2' is still a plain statement. Dont u think so? – habillqabill Jul 1 '14 at 10:24
• @habillqabill Suppose $n$ is odd. Let $r$ be any integer between $1$ and $n$. Now suppose $r$ is less than $n/2$, then we are done. If $r$ is in fact greater than $n/2$, then $n - r < n/2$ and we are done. Basically, no matter $r$, either $r$ or $n - r$ will be less than $n/2$ (since both will fall on opposite sides of $n/2$). It's a symmetry argument. – Thomas Jul 1 '14 at 10:25
• oh yeah, that correct. n should be an odd number. By the way, i'll try to turn your argument into a mathematical statement. I see it all over the places, particularly when involving Rabin primitive, without any explanation. – habillqabill Jul 1 '14 at 10:30
• @habillqabill If this answers your question, would you consider accepting it by clicking on the check mark on the left? – Thomas Jul 3 '14 at 15:12
• ok done. tq guys. – habillqabill Jul 11 '14 at 8:00

This is not correct for all primes $p,q;\;$ even if $p\ne q:\;$ take e.g. $p=2$, $q=5$. Here you have two quadratic residues in $(\mathbb{Z}/n\mathbb{Z})^\times$ namely $1$ and $9\equiv -1,\;$ but both have only two square roots: $$1^2 \equiv 9^2 \equiv 1 \pmod {10}, \quad \text{and}\quad 3^2 \equiv 7^2 \equiv 9 \pmod {10}$$

• Your example is a particular case involving the prime 2 (even number). However, in practical we used large primes, then the theorem will always correct since all other primes are odd numbers. – habillqabill Jul 1 '14 at 10:20
• @habillqabill: No, at least you must additionally assume $p\ne q.$ – gammatester Jul 1 '14 at 10:26
• However, if u familiar with Rabin's encryption or modular square root problem, then it is mathematically proven that there are exactly four integers x_i such that y=x^2(mod pq) – habillqabill Jul 1 '14 at 10:36
• Rabin assumes distinct primes and $p\equiv q \equiv 3 \pmod 4$. For the general problem with two odd primes there is another counter example. Take look at $p=q=3:\;$ $$1^2 \equiv 8^2 \equiv 1 \pmod {9}, \quad 2^2 \equiv 7^2 \equiv 4 \pmod {9}, \quad 4^2 \equiv 7^2 \equiv 5 \pmod {9}$$ @tylo: Here $\varphi(9)=6$ is no multiple of 4. – gammatester Jul 1 '14 at 10:50
• It was not me throwing in Rabin. – gammatester Jul 1 '14 at 11:03