[proofplan]
The argument is a two-line observation packaged carefully. From $x^2 \equiv y^2 \pmod N$ we extract $N \mid (x-y)(x+y)$. The gcd $d := \gcd(N, x+y)$ lies in $\{1, 2, \ldots, N\}$ and divides $N$ by definition. We rule out the two degenerate endpoints: $d = N$ would force $N \mid (x+y)$, i.e. $x \equiv -y \pmod N$, violating the second hypothesis; $d = 1$ would force $N$ to divide the other factor $x - y$ (using coprimality to transfer all prime factors of $N$ from $x+y$ to $x-y$), i.e. $x \equiv y \pmod N$, again violating the hypothesis. The symmetric argument works for $\gcd(N, x - y)$ by swapping $y$ with $-y$.
[/proofplan]
[step:Derive the factorisation $N \mid (x-y)(x+y)$ from the congruence of squares]
By hypothesis, $x^2 \equiv y^2 \pmod{N}$, so $N \mid (x^2 - y^2)$. Factoring in $\mathbb{Z}$,
\begin{align*}
x^2 - y^2 &= (x - y)(x + y).
\end{align*}
Hence
\begin{align*}
N &\mid (x - y)(x + y).
\end{align*}
[/step]
[step:Analyse $d := \gcd(N, x+y)$ and rule out the endpoints]
Set $d := \gcd(N, x + y)$. By definition of the gcd, $d \mid N$, so $d \in \{1, 2, \ldots, N\}$. We show $d \neq N$ and $d \neq 1$.
*Ruling out $d = N$.* Suppose, for contradiction, $d = N$. Then $\gcd(N, x + y) = N$, which means $N \mid (x + y)$, i.e.
\begin{align*}
x &\equiv -y \pmod{N}.
\end{align*}
This contradicts the hypothesis $x \not\equiv -y \pmod{N}$.
*Ruling out $d = 1$.* Suppose, for contradiction, $\gcd(N, x + y) = 1$. Since $N \mid (x - y)(x + y)$ (Step 1) and $\gcd(N, x + y) = 1$, [Euclid's Lemma](/theorems/???) applies: if $N$ divides a product and is coprime to one factor, it divides the other. Hence
\begin{align*}
N &\mid (x - y),
\end{align*}
i.e. $x \equiv y \pmod{N}$, contradicting the hypothesis $x \not\equiv y \pmod{N}$.
Therefore $1 < d < N$, and $d$ is a proper divisor of $N$.
[guided]
The strategy is to trap the value of $d = \gcd(N, x+y)$ between the two forbidden endpoints $d = N$ and $d = 1$. The gcd always satisfies $d \mid N$, so $d$ is automatically a divisor of $N$; what we need is that $d$ is a *proper* divisor, i.e. $d \in \{2, 3, \ldots, N - 1\}$.
*Why rule out $d = N$?* If $d = \gcd(N, x+y) = N$, then every divisor of $N$ divides $x + y$; in particular $N$ itself divides $x + y$, so $x + y \equiv 0 \pmod N$, i.e. $x \equiv -y \pmod N$. This is precisely the second half of the forbidden condition $x \equiv \pm y \pmod N$. So the hypothesis $x \not\equiv -y \pmod N$ blocks $d = N$.
*Why rule out $d = 1$?* This is the subtler case. If $\gcd(N, x+y) = 1$, then $N$ and $x + y$ share no prime factors. But we know $N \mid (x-y)(x+y)$. [Euclid's Lemma](/theorems/???) — which requires exactly coprimality of $N$ with one factor — then tells us that the "missing" divisibility must be absorbed by the other factor: $N \mid (x - y)$. That gives $x \equiv y \pmod N$, violating the first half of $x \not\equiv \pm y \pmod N$.
So both endpoints are impossible, and $1 < d < N$. This $d$ is a proper divisor of $N$, which is the useful factor in factoring algorithms.
Why is this algorithmically useful? Because if $N$ were prime, every gcd $\gcd(N, m)$ with $0 < m < N$ would equal $1$, and we could never produce a proper factor. The existence of $x \not\equiv \pm y$ with $x^2 \equiv y^2 \pmod N$ is a *certificate of compositeness* of $N$, and $\gcd(N, x \pm y)$ is the witness factor.
[/guided]
[/step]
[step:Repeat the argument for $\gcd(N, x - y)$ by symmetry]
Set $d' := \gcd(N, x - y)$. The argument is identical in structure to Step 2, with the roles of $+y$ and $-y$ swapped.
*Ruling out $d' = N$.* If $d' = N$, then $N \mid (x - y)$, i.e. $x \equiv y \pmod{N}$, contradicting the hypothesis $x \not\equiv y \pmod{N}$.
*Ruling out $d' = 1$.* If $\gcd(N, x - y) = 1$, then by [Euclid's Lemma](/theorems/???) applied to $N \mid (x-y)(x+y)$ with $\gcd(N, x - y) = 1$, we conclude $N \mid (x + y)$, i.e. $x \equiv -y \pmod{N}$, contradicting the hypothesis $x \not\equiv -y \pmod{N}$.
Therefore $1 < d' < N$, and $d'$ is also a proper divisor of $N$.
[/step]
[step:Conclude]
Both $\gcd(N, x + y)$ and $\gcd(N, x - y)$ are proper divisors of $N$, as claimed. This completes the proof.
[/step]
