Let n = p*q,$n = p*q$, with p != q$p \neq q$ and x^2=1 (mod n), x+1 $\neq$ 0 (mod n), x-1 $\neq$ 0 (mod n)$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}$$\gcd(x+1,n) \in \{p,q\}$ follows.
I understand that x^2=(x+1)(x-1)$x^2=(x+1)(x-1)$, so n=p*qis$n=p*q$ is a factor of (x+1)(x-1)$(x+1)(x-1)$, but neither of (x+1)$(x+1)$ nor of (x-1)$(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}$$gcd(x+1,n) \in \{1,p,q\}$ (so the trivial solution 1 is indeed possible). How can we be sure that x+1$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.
