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...