Why does square root $\pmod n$ find $p$ and $q$ (as $n = p \cdot q$)?

Question

Let $n = p*q$, with $p \neq q$ and $x^2=1 \pmod n$, $x+1 \neq 0 \pmod n, x-1 \neq 0 \pmod n$ (So x is a non-trivial square root mod n.)

I don't see how $\gcd(x+1,n) \in \{p,q\}$ follows.

I understand that $x^2=(x+1)(x-1)$, so $n=p*q$ is a factor of $(x+1)(x-1)$, but neither of $(x+1)$ nor of $(x-1)$ (as a x is a non-trivial solution). Every proof I've seen so far stops at this point, leaving me confused. In my opinion, it holds that $gcd(x+1,n) \in \{1,p,q\}$ (so the trivial solution 1 is indeed possible). How can we be sure that $x+1$ and n have common factors other than 1? I'm sure I am missing something very obvious, but I just can't make it out.

Answer 1

If $x^2\equiv1\mod{n}$, it means that $(x+1)(x-1)\equiv0\mod n$. In other words, $(x+1)(x-1)=k\cdot n=k\cdot p\cdot q$ for some $k\in\mathbb{N}$. And there you go: if $x\neq\pm 1\mod n$, neither $x+1$ nor $x-1$ equals $p\cdot q$ and must contain either of the primes in their factorization (plus perhaps some factor of $k$). Hence, $\gcd(x+1,n)\in\{p,q\}$.

Answer 2

You have

$x^2 \equiv 1 \pmod n$ and $x \neq \pm 1 \pmod n$

now we can write $x^2 -1 = 0 + n\cdot k$ for some $k \in \mathbb{Z}$.

that is $(x-1)(x+1) = n \cdot k$.

• So if you take $\gcd(x+1, n)$ and $\gcd(x-1,n)$ then one of them must be larger than 1. Otherwise we have to $(x-1)(x+1) = k$ which fails since the equality.

• Also, if we now that $n = p \cdot q$ we can look at $(x-1)(x+1) = n \cdot k$ as; $$(x-1)(x+1) = p \cdot q \cdot k$$ which means that $p$ and $q$ must divide either $(x-1)$ or $(x+1)$ and this will make the GCD differs from 1.