Prove that if $(u,v)$ is chosen randomly from $S$, there is at least a $50\%$ chance that $u\ne\pm v \bmod N$ I need serious help with this problem. 
Suppose $N$ is an odd composite number and $S=\{(x,y) \in \mathbb Z^2 : x^2 \equiv y^2 \mod N\}$


*

*Prove that if $(u,v)$ is chosen randomly from $S$, there is at least a $50\%$ chance that $u \not \equiv \pm v \bmod N$


Attempt:
since $(x,y)$ satisfy $x^2 \equiv y^2 \mod N$
then $x^2 - y^2 \equiv 0 \mod N$
so, 
$(x-y)(x+y)=0 \mod n$
and we know that n is a composite number, so there are prime factor p and q such that n=pq
so
$(x-y)(x+y)=0 \bmod pq$
and by Chinese Remainder Theorem we deduce
$(x-y)(x+y)=0 \bmod p$   
and 
$(x-y)(x+y)=0 \bmod q$
so
$(x-y)(x+y)=kpq$
$(x-y)(x+y)/(pq)=k$
for some constant $k$
that's pretty much all i got, I'm not sure how to finish the proof. any help would be greatly appreciated.
 A: Let $n=15$, and fix $y$. We find the probability that if $0\le x\lt 15$, and $x^2\equiv y^2\pmod{15}$, then $x\equiv \pm y\pmod{15}$.
It is not hard to verify that if $y$ is relatively prime to $15$, then there are precisely $4$ values of $x$ such that $x^2\equiv y^2\pmod{15}$. Thus for such $y$ the probability is exactly $50\%$.
If $y^2\equiv 0\pmod{15}$, then $x\equiv y \pmod{15}$. For such $y$, the probability that $x\not\equiv \pm y\pmod{15}$ is $0$. 
We cannot have $y^2\equiv 3\pmod{15}$, or $y^2\equiv 5$, or $y^2\equiv 12$.
Now look at $y^2\equiv 6\pmod{15}$. The only $x$ such that $x^2\equiv y^2\pmod{15}$ are $x\equiv \pm 6$. Thus if $y^2\equiv 6\pmod{15}$, the probability that $x\not\equiv \pm y\pmod{15}$ is $0$.
We can deal similarly with $y^2\equiv 9\pmod{15}$ and $y^2\equiv 10\pmod{15}$.  
Thus the assertion we were asked to prove is not true. 
Remark: If we specify in addition that $x$ and $y$ are relatively prime to $n$, then it is indeed true that the probability that $x\not\equiv \pm y\pmod{n}$ is $\ge \frac{1}{2}$, unless $n$ is a prime power. This can be done by a Chinese Remainder Theorem argument.
If $n$ is not a prime power, let $n=ab$ where $a$ and $b$ are relatively prime. Fix $y$. Then the congruence $x^2\equiv y^2\pmod{a}$ has at least two solutions, $x\equiv y$ and $x\equiv -y$. 
The same is true modulo $b$.
By the CRT, we can find $x$ such that $x\equiv y\pmod{a}$ and $x\equiv -y\pmod{b}$. This $x$ is not congruent to $y$ or $-y$ modulo $ab$. Neither is $-x$.  
A: It is not true.  Let $n=9$.  The squares $\pmod 9$ are $0,1,4,7$  There are thee numbers that square to $0$, so nine ordered pairs from them.  Three of those have $u=v$ and two have $u=-v$  There are two numbers that square to each of $1,4,7$, so four ordered pairs for each of the three.  All of them have $u=\pm v$, so the chance that $u \neq \pm v \pmod 9$ is only $\frac 4{21}$
I believe it will be true if $n$ has at least three distinct prime factors.  For example, let $n=105=3\cdot 5 \cdot 7$.  There is one square, $0$, with only one square root.  It contributes one ordered pair.  There are six squares, $15,21,30,60,70,84$ with two square roots.  Each contributes four ordered pairs and $u=\pm v$ in all of them.  There are ten squares, $9,25,36,39,49,51,81,85,99,100$ with four square roots.  Each contributes sixteen ordered pairs and $u= \pm v$ in half of them.  There are six squares, $1,4,16,46,64,79$ with eight square roots.  Each contributes sixty-four ordered pairs and $u= \pm v$ in only sixteen of them.  So out of $569$ ordered pairs, we have $u = \pm v$ in $1+24+80+96=201$
