Let's say I have an integer $n$ and two integers $y$ and $x$ such that
$x\not\equiv\pm y ($mod$n)$ but $x^2 \equiv y^2($mod $n)$
This would of course imply that $(x-y)(x+y) \equiv 0 ($mod $n)$.
Why, then, are the greatest common divisors $(x-y, n)$ and $(x+y,n)$ not equal to $1$ or $n$ ?
I have to explain to some people this, which is the essence of the Quadratic Sieve Method, and I'm certain the Chinese Remainder Theorem will be useful in explaining it here, but I need someone to help me explain why that statement is true.
To show $gcd(x-y,n)\neq n$, we assume the opposite first for the sake of contradiction, then $n|x-y$ contradicting $x\not\equiv y\pmod{n}$.
To show $gcd(x+y,n)\neq n$, we assume the opposite first then $n|x+y$ contradicting $x\not\equiv -y\pmod{n}$.
To show $gcd(x-y,n)\neq1$, we assume the opposite, then since $x^2-y^2$ is a multiple of $n$ and $x-y,n$ are coprime, $n|x+y$ contradicting $x\not\equiv -y\pmod{n}$.
To show $gcd(x+y,n)\neq1$, we assume the opposite, then since $x^2-y^2$ is a multiple of $n$ and $x+y,n$ are coprime, $n|x-y$ contradicting $x\not\equiv y\pmod{n}$.