Bounds of GCD for Sum and Difference Congruent Squares

Theorem

If $x\not\equiv\pm{y}\pmod{n}$ and $x^2\equiv y^2\pmod{n}$ then $1<\gcd(x-y,n)<n$ and $1<\gcd(x+y,n)<n$.

Proof

Let $x^2\equiv y^2 \pmod{n}$

$\implies n|(x^2-y^2) \implies n|(x+y)(x-y)$

$\implies p|(x+y)(x-y)$ $ \forall$ prime divisors $p$ of $n$

$\implies p|(x-y)$ or $p|(x+y)$

But since $x\not\equiv -y \pmod{n}$, then $n\not{|}(x+y)$,

and $x\not\equiv y \pmod{n}$, then $n\not{|}(x-y)$

$\therefore \gcd(x+y,n)<n$ and $\gcd(x-y,n)<n$

So if $p|(x-y)$ then $1<p\leq\gcd(x-y,n)$, also $\exists q: q|n$ and $q|(x+y)$ and $1<q\leq\gcd(x+y,n)$

Likewise if $p|(x+y)$ then $1<p\leq\gcd(x+y,n)$, also $\exists q: q|n$ and $q|(x-y)$ and $1<q\leq\gcd(x-y,n)$

$\blacksquare$