Why is there at least a $50$% chance that greatest common divisor $(n,x-y)$ is a factor of $n$ not equal to $0$, $1$, or $n$? Given integers $x$, $y$, and $n$ such that $x^2\equiv y^2 ($mod$ n)$, there is at least a $50$% chance that greatest common divisor $(n,x-y)$ is a factor of $n$ not equal to $1$, $0$, or $n$.  Why is it at least $50$%?
I think it is because if $x\not\equiv±y($mod$ n)$, then gcd$(n,x-y)$ is a factor of $n$ not equal to $1$, $0$, or $n$, but if $x\equiv±y($mod$ n)$, then gcd$(n,x-y)$ must equal $n$, $1$ or $0$. 
My Guess:
Let’s say we find an $x$ and $y$ such that $x^2 ≡ y^2($mod$ n)$.
Then $(x – y)(x + y) = 0 ($mod$ n)$
First, if either $x$ or $y$ is $0$, then gcd$(n, x - y) = 0$ 
If $x ≡ y($mod$ $n)$, then gcd$(n, x - y) = 0$ or $n$.
If $x ≡ -y($mod$ $n)$, then gcd$(n, x - y) = 1$ or $n$
If $x ≡ y(mod$ $n)$, then gcd$(n, x + y) = 1$ or $n$
If $x ≡ -y(mod$ $n)$, then gcd$(n, x + y) = 0$ or $n$
But if $x$ is not congruent to $± y($mod $n)$, then gcd$(n, x + y)$ does not equal $0$, $1$, or $n$. 
So when $x^2 ≡ y^2(mod$ $n)$, there is at least a $50$% chance that gcd$(n, x + y)$ is a non-trivial factor of $n$ (a factor not equal $0$, $1$, or $n$).
Is this correct?
 A: The given statement is correct for numbers $n$ with at least two distinct odd prime factors. (to be more precise, if there is no primitive root modulo $n$ , but the case of $n$ odd and $n$ has two distinct prime factors is the most important in practice)
Suppose, $n$ is divisible by the odd distinct primes $p$ and $q$ and $x^2\equiv y^2\ ($mod $n$).
If $gcd(x,y)\ne1$, then there exists a prime $r$ such that  $r|x$ and $r|y$.
In such a case case, $r$ also divides $x-y$ and therefore $x^2-y^2$. Hence $r|gcd(n,x-y)$.
If $x\equiv y\ ($mod $n\ )$, then $gcd(x-y,n)=$$n$. Because $n > 2r$,
this occurs with probability at most $\frac{1}{2}$.
If $gcd(x,y)=1$, then we have that $gcd(n,y)=1$. If it didn't, there would be a prime $r$ dividing $n$ and $y$, so we would have that $x^2\equiv 0\ ($mod $r)$, implying $x\equiv 0\ ($mod $r )$, which is a contradiction to $gcd(x,y)=1$.
Hence, $x^2\equiv y^2\ (\ mod\ n)$ can be transformed into $z^2\equiv 1\ (\ mod\ n)$.  
The solution of the system $p\equiv 1\ (\ mod\ n)$ $q\equiv -1\ (\ mod\ n)$ and the solution of the system $p\equiv-1\ (\ mod\ n)$ $q\equiv 1\ (\ mod\ n)$ are two non-trivial solutions. So, the case $gcd(x,y)=1$ gives a chance of at least $\frac{1}{2}$ to find a factor because the equation $z^2\equiv 1\ (\ mod\ n)$ has at least $4$ solutions, two of which are trivial.
