# In Shor's algorithm, why do we have ${\rm gcd}(x\pm 1, N) > 1$?

I'm struggling to understand the last part of Shor's algorithm, to be exact the point when we found $$x-1$$, $$x+1$$ with $$x-1 ≠ 0\mod N$$, $$x+1 ≠ 0 \mod N$$ and $$(x+1)(x-1) = 0 \mod N$$.

Then, $$gcd(x-1, N) > 1$$ and $$gcd(x+1, N) > 1$$ should hold true. Why is this the case? Is this so trivial to see? Especially the$$\mod N$$ confuses me here.

The assumptions $$x\pm1\neq0\bmod N$$ mean that neither of them is a multiple of (or equal to) $$N$$. That is, you cannot write $$x+1=kN$$ for some $$k\in\mathbb{Z}$$, and same for $$x-1$$.
At the same time, $$(x+1)(x-1)=0\bmod N$$ means that $$(x+1)(x-1)=kN$$ for some $$k\in\mathbb{Z}$$. This means all factors of $$N$$ are contained in this product. But by the previous assumption, they are not contained in $$x+1$$ or $$x-1$$ individually. So the only possibility is that some of the factors of $$N$$ are in $$x+1$$, and some of them are in $$x-1$$. This is equivalent to saying that the GCD between $$x\pm1$$ and $$N$$ is not one.
As an example, consider a simple case with $$N=pq$$ with $$p,q$$ coprimes. Then if $$(x+1)(x-1)=kpq$$ but $$x\pm1\neq0\bmod pq$$, then $$x+1$$ must contain $$p$$, and $$x-1$$ must contain $$q$$ (or vice versa). And that would mean $$\operatorname{gcd}(x+1,N)=p>1$$ and $$\operatorname{gcd}(x+1,N)=q>1$$.