Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$ is a nontrivial factor of $n$.

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

share|improve this question
    
Oops, sorry. I'm reading this article and may have misinterpreted the problem. –  Stavros May 22 '13 at 11:08
1  
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 May 22 '13 at 11:26

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
    
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 May 22 '13 at 12:22
1  
@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).

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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