Bounds of GCD for Sum and Difference Congruent Squares

Theorem

Let $x, y, n$ be integers.

Let:

$x \not \equiv \pm y \pmod n$

and:

$x^2 \equiv y^2 \pmod n$

where $a \equiv b \pmod n$ denotes that $a$ is congruent to $b$ modulo $n$.

Then:

$1 < \gcd \set {x - y, n} < n$

and:

$1 < \gcd \set {x + y, n} < n$

where $\gcd \set {a, b}$ is the GCD of $a$ and $b$.

Proof

\(\ds x^2\)

\(\equiv\)

\(\ds y^2\)

\(\ds \pmod n\)

\(\ds \leadsto \ \ \)

\(\ds n\)

\(\divides\)

\(\ds \paren {x^2 - y^2}\)

\(\ds \leadsto \ \ \)

\(\ds n\)

\(\divides\)

\(\ds \paren {x + y} \paren {x - y}\)

\(\ds \leadsto \ \ \)

\(\ds p\)

\(\divides\)

\(\ds \paren {x + y} \paren {x - y}\)

for all prime divisors $p$ of $n$

\(\ds \leadsto \ \ \)

\(\ds p\)

\(\divides\)

\(\ds \paren {x - y}\)

\(\, \ds \lor \, \)

\(\ds p\)

\(\divides\)

\(\ds \paren {x + y}\)

But since $x \not \equiv -y \pmod n$, then:

$n \nmid \paren {x + y}$

and since $x \not \equiv y \pmod n$, then:

$n \nmid \paren {x - y}$

Therefore:

$\gcd \set {x - y, n} < n$

and:

$\gcd \set {x + y, n} < n$

So if $p \divides \paren {x - y}$ then:

$1 < \gcd \set {x - y, n} < n$

and also there exists $q$ such that:

$q \divides n$

$q \divides \paren {x + y}$

$1 < q \le \gcd \set {x + y, n}$

Likewise if $p \divides \paren {x + y}$ then:

$1 < \gcd \set {x + y, n} < n$

and also there exists $q$ such that:

$q \divides n$

$q \divides \paren {x - y}$

$1 < q \le \gcd \set {x - y, n}$

$\blacksquare$