# If $x^2\equiv 1 \pmod{n}$ and $x \not\equiv \pm 1 \pmod{n}$, then either $\gcd(x-1,n)$ or $\gcd(x+1,n)$ is a nontrivial factor of n

I'm reading elementary number theory and trying to understand the following problem: If $x^2\equiv 1 \pmod{n}$, $n=pq$, $p$ and $q$ are odd primes and $x \not\equiv \pm 1 \pmod{n}$, then either $\gcd(x-1,n)$ or $\gcd(x+1,n)$ gives a factorization of n.

EDIT: Andreas Caranti wrote an updated, corrected version of my problem, so I wrote the definition again.

-
Oops, sorry. I'm reading this article and may have misinterpreted the problem. –  Stavros Mekesis May 22 '13 at 11:08
Notice that what you proved is not true! $n$ can divide neither $x+1$ nor $x-1$. Take for example $n=15$, and $x=4$. –  awllower May 22 '13 at 11:08
I might hazard a guess that this is either about Rabin-Miller style primality testing, where a `surprising' square root of $1$ produces a factorization, or about studying RSA? –  Jyrki Lahtonen May 22 '13 at 11:20
@JyrkiLahtonen: Yes, you're right! I'm studying an RSA problem and trying to understand the proof of the Fact 1 on page 205 from this paper. –  Stavros Mekesis May 22 '13 at 11:26

I assume your primes are odd and distinct. Also, your statement is not correct as written, you have to add $x \not\equiv \pm 1 \pmod{n}$. The latter assumption implies that $\gcd(x-1, n), \gcd(x+1, n) < n$.

You have $n \mid x^{2} - 1 = (x-1)(x+1)$. Now if $\gcd(x - 1, n) = 1$, then $n$ divides $x + 1$, a contradiction, as we have taken $x \not\equiv -1 \pmod{n}$. So $\gcd(x - 1, n) > 1$. Similarly, $\gcd(x + 1, n) > 1$.

It follows that $\gcd(x-1,n)$ and $\gcd(x+1, n)$ are nontrivial, proper divisors of $n$, hence $p$ or $q$.

-
Thanks! I'm new to number theory, so I have some questions. Why the latter assumption implies that $\gcd$s are $<n$? And why every nontrivial, proper divisor of n is prime? –  Stavros Mekesis May 22 '13 at 12:22
@Stavros, for your first question, $x \equiv 1 \pmod {n}$ if and only if $n \mid x - 1$ if and only if $\gcd(x-1,n) = n$. (And similarly for $-1$.) For the second one, uniqueness of factorization implies that the (positive) divisors of $n = p q$ are $1, p, q , n$. –  Andreas Caranti May 22 '13 at 14:42

If not, by Euclid's Lemma, $\ (n,x\pm1)=1\,\Rightarrow\, (n,(x\!-\!1)(x\!+\!1)) = 1,\,$ contra $\, n\mid x^2-1$.

Or, more directly, $\ (x\!-\!1)(x\!+\!1) = pqk,\,$ so, by unique factorization, the prime $\,p\,$ is a factor of one of $\, x\!-\!1,\ x\!+\!1,\,$ so $\,q\,$ is a factor of the other one (else both primes divide the same factor, so $\, n = pq\,$ divides $\,x\!-\!1\ \ {\rm or}\ \ x\!+\!1,\,$ contra hypothesis).

-

If $n=p\cdot q$ divides $x^2-1=(x+1)(x-1)$

If odd prime $r$ divides $x-1$ and $x+1,$ it will divide $(x+1)-(x-1)=2$ which is impossible $\implies r$ can divide exactly one of $x-1,x+1$

Now let us check the possibilities

Case $1:$ $p$ divides $x-1$ and $q$ divides $x-1\implies (x-1)$ is divisible by lcm$(p,q)=pq=n\implies x\equiv1\pmod n$ which is not acceptable according to the given condition.

Similarly, Case $2:$ $p$ divides $x+1$ and $q$ divides $x+1$ is discarded

Case $3:$ $p$ divides $x-1$ and $q$ divides $x+1$

Then $x-1=p\cdot a,x+1=q\cdot b$ where $a,b$ are some integers

i.e., $q\cdot b-p\cdot a=2$ , we can always find such $a,b$ using Bézout's Lemma as $(p,q)=1$

If $q$ divides $a,$ the LHS will be divisible by $q$

$\implies 2$ must be divisible by $q$ which is impossible $\implies (q,a)=1$

Now, gcd$(x-1,n)=$gcd$(p\cdot a,p\cdot q)=p\cdot$gcd $(a,q)=q$ as gcd$(a,q)=1$

Case $4$ $p$ divides $x+1$ and $q$ divides $x-1$ can be handled similarly.

-