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

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.

• Welcome to Cryptography. We have $MathJax$ in our site. Please check my modifications. Also, in short, you can say, $x \neq \pm 1 \pmod n$ – kelalaka Aug 17 '19 at 18:45
• Possible duplicate of Factoring large $N$ given oracle to find square roots modulo $N$ – yyyyyyy Aug 17 '19 at 19:25
• @kelalaka You may want to support my feature request: github.com/mathjax/MathJax/issues/2084 – Maarten Bodewes Aug 18 '19 at 16:34
• @MaartenBodewes sure. – kelalaka Aug 18 '19 at 16:36
• From $n = p*q$, with $p \neq q$ and $x^2\equiv1 \pmod n$, $x+1 \not\equiv 0 \pmod n$, $x-1 \not\equiv 0 \pmod n$, its does not follow $\gcd(x+1,n) \in \{p,q\}$. We additionally need that $p$ and $q$ are prime. However, that's not because we must include $x=1$; that is ruled out by $x-1 \not\equiv 0 \pmod n$ – fgrieu Aug 19 '19 at 8:45

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\}$$.

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.