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.

  • $\begingroup$ 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$ $\endgroup$
    – kelalaka
    Aug 17, 2019 at 18:45
  • 3
    $\begingroup$ Possible duplicate of Factoring large $N$ given oracle to find square roots modulo $N$ $\endgroup$
    – yyyyyyy
    Aug 17, 2019 at 19:25
  • 1
    $\begingroup$ @kelalaka You may want to support my feature request: github.com/mathjax/MathJax/issues/2084 $\endgroup$
    – Maarten Bodewes
    Aug 18, 2019 at 16:34
  • $\begingroup$ @MaartenBodewes sure. $\endgroup$
    – kelalaka
    Aug 18, 2019 at 16:36
  • $\begingroup$ 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$ $\endgroup$
    – fgrieu
    Aug 19, 2019 at 8:45

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.