I'm trying to understand something written in my textbook. Suppose $n=pq$ is the product of two primes and we know the four solutions $x \equiv \pm a, \pm b$ of $x^2 \equiv y \ $(mod $\ n)$. Then $a \equiv b \ $ (mod $p$) and $a \equiv -b \ $(mod $q$), or $a \equiv b \ $(mod $q$) and $a \equiv -b \ $(mod $p$).
Can someone explain why this is true?
On
Just an example.
The square roots of $-3 \equiv 4 \pmod 7$ are $\pm 2 \pmod 7.$
The square roots of $-3 \equiv 36 \pmod{13}$ are $\pm 6 \pmod{13}$
By the Chinese Remainder Theorem, one of the pairs comes from $19,$ because $$ 19 = 3 \cdot 7 - 2 = 13 + 6.$$ That pair, $\pm 19 \pmod {91}$ are $$ 19, 72 \pmod{91} $$ So we are naming $a = 19.$
The other pair comes from $33,$ because $$ 33 = 5 \cdot 7 - 2 = 3 \cdot 13 - 6.$$ That pair, $\pm 33 \pmod {91}$ are $$ 33, 58 \pmod{91} $$ So we are naming $b = 33.$
Then $p=7, \; \; $ $q = 13.$
Let's see, $33-19 = 14$ is a multiple of $7,$ so $a \equiv b \pmod 7.$
Finally, $33+19 = 52$ is a multiple of $13$ so $a+b \equiv 0 \pmod {13} \; , \; \; $ also written $a \equiv -b \pmod {13}.$
$a^2\equiv b^2\pmod n\iff n|a^2-b^2=(a+b)(a-b)\implies p,q|(a+b)(a-b)$
$\implies p|a+b$ or $a-b$ and $q|a+b$ or $a-b$
$\implies a\equiv -b\pmod p$ or $a\equiv b\pmod p$ and $a\equiv-b\pmod q$ or $a\equiv b\pmod q$.
But if $a\equiv b\pmod p$ and $a\equiv b\pmod q$ then $a\equiv b\mod n$, so $a$ and $b$ are not distinct.
Likewise if $a\equiv -b\pmod p $ and $a\equiv -b\pmod q$ then $a\equiv-b\pmod n$,
so again $\pm a$ and $\pm b$ are not distinct.
Therefore, the possibilities are $a\equiv b\pmod p$ and $a\equiv -b\pmod q$
or $a\equiv -b\pmod p$ and $a\equiv b\pmod q$.