Probability Factorization Algorithm I want to prove the following: 
Let $n = pq$, with $p, q$ distinct odd primes. Let $x,y$ be random integers with $\gcd(xy, n) = 1$ and $x^2 \equiv y^2 \mod n$. Prove that there is a 50-50 chance that $\gcd(n, x-y)$ is a nontrivial factor of n. 
I know: $n|(x^2-y^2) \iff n|(x-y)(x+y) \iff nk = (x-y)(x+y)$ for some $k\in \mathbb{Z}$.
Now I want to enumerate over some cases (possibilities from this equation):


*

*$(x-y) = n$

*$(x-y) = 1$

*$k$ divides $(x-y)$

*$k$ does not divide $(x-y)$


I know I am missing something. I am just not quite sure where to go from here...
 A: Hint: We have $x^2\equiv y^2\pmod{n}$ iff $x^2\equiv y^2\pmod{p}$ and $x^2\equiv y^2\pmod{q}$.
For given $y$, the congruence $x^2\equiv y^2\pmod{p}$ has two solutions, namely $x\equiv y\pmod{p}$ and $x\equiv -y\pmod{p}$. Similarly, for fixed $y$ the congruence $x^2\equiv y^2\pmod{q}$ has two solutions. 
So by the Chinese Remainder Theorem, for fixed $y$ the congruence $x^2\equiv y^2\pmod{n}$ has $4$ solutions. 
Show that the two uninteresting ones, where the signs match, do not produce a non-trivial factor, but the other two do. 
Added detail: Suppose for example that $x\equiv y\pmod{p}$ and $x\equiv -y\pmod{q}$. Then $p$ divides $x-y$, and $q$ divides $x+y$.  But $q$ does not divide $x-y$. For if $q$ divided $x-y$, then $q$ would divide $(x-y)+(x+y)$, that is, $2x$. This is impossible, since $\gcd(xy,n)=1$ and $q$ is odd.  
Since $p$ divides $x-y$, but $q$ doesn't, $\gcd(x-y,n)\ne 1$, and $\gcd(x-y,n)\ne n$. It follows that $\gcd(x-y,n)=p$.
Essentially the same argument shows that if $x\equiv -y\pmod{p}$ and $x\equiv y\pmod{q}$, then $\gcd(x-y,n)=q$. 
