Congruence of Squares for Factoring After coming across the assertion that given

$$
    x^2 = y^2 \pmod n \\
    x \neq \pm y \pmod n
$$

we can then conclude that n factors into 

$$
    n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y).
$$

in this article, I attempted my own example but it doesn't seem to work.  I think there's a missing hypothesis, but more importantly, I'm interested in understanding why this would work under the correct conditions.



First, the example given was 

$$
\begin{align*}
    &amp;6^2 = 1^2 \pmod {35} \\
    &amp;x+y = 7 \\
    &amp;x-y = 5
\end{align*}
$$

So applying the gcd with $35$ simply retains the values, yielding the correct factorization 

$$35 = 7 \times 5.$$



However, my test example was 

$$
\begin{align*}
    &amp;8^2 = 4^2 \pmod {24} \\
    &amp;x+y = 12 \\
    &amp;x-y = 4
\end{align*}
$$
If we just blindly applied the stated result, we would get

$$24 = 12 \times 4.$$

I would guess the problem is that my selected factors are not coprime.  Does anyone have any intuition for why this method works (when it works) or any hints towards a proof?



After some brief pondering, I've noticed it certainly works if the values $x+y$ and $x-y$ are coprime.  Their product divides $n$ yet they contain no overlapping factors, so by collecting the factors of $x+y$ and $x-y$ which are also factors of $n$, we will end up with precisely all the factors of $n$ and nothing extra.
The  assertion is not correct in general, as you have discovered.

However, here is what is correct:  $\gcd(x+y,n)$ is a factor  of $n$, and $\gcd(x-y,n)$ is a factor  of $n$.  Why?  Well, this is trivial: $\gcd(\text{anything},n)$ is always a  factor of $n$.  Of course, the gcd might be 1, but that's still a divisor of $n$.

We can say even more.   If we let $r=\gcd(x+y,n)$ and $s=\gcd(x-y,n)$, then their product is a multiple of $n$: i.e., $rs$ is a multiple of $n$.  Thus, you can replace $s$ with $s'=n/r$ and now $r,s'$ will have the property you want: both $r$ and $s'$ are divisors of  $n$, and $rs'=n$.  (Why is $rs$ a multiple of $n$? Because if  $x^2  \equiv y^2 \pmod n$, then it follows that $x^2 - y^2 \equiv 0 \pmod n$.  Now $x^2-y^2 = (x-y)(x+y)$, so it follows that $n$ divides $(x-y)(x+y)$, i.e., $n$ divides $rs$.)

This makes this method useful for factoring.  However, beware that there is no guarantee that get a non-trivial factor out of this.  For instance, consider $n=15$.   Then if $x=8$ and $y=7$, we have $x^2 \equiv y^2 \equiv 4 \pmod n$, but $\gcd(x-y,n)=1 $ and $\gcd(x+y,n)=15$, so we obtain that $15 = 1 \times 15$ -- true, but not very useful for factoring $n$.  What we can say is that if $n$  is the product of two large primes, and if you can randomly sample  two $x,y$ such that $x^2 \equiv y^2 \pmod n$, then with probability about $1/2$, $\gcd(x-y,n)$ and $\gcd(x+y,n)$ will give you the full factorization of $n$.

If you want us to comment on an assertion it helps to give a reference for it.  My guess would be that there is additional context you are not  providing, such as the assumption that $n$ is a product of two primes.