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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Knowing that $n= 3598057$ is a product of two different prime numbers and that 20779 is a square root of $1$ mod $n$, find prime factorization of $n$.

What I have done so far:

$n = p \cdot q$

$x^2 \equiv 1\pmod{n}$

$x^2 -1 \equiv 0\pmod{n}$

$(x-1)(x+1) \equiv 0\pmod{n}$

$x-1 = 20779 \lor x + 1=20779$

I have also noticed that:

$(x-1)(x+1) \equiv 0\pmod{p \cdot q}$

$(x-1)(x+1) \equiv 0\pmod{p} \land (x-1)(x+1) \equiv 0\pmod{q}$

But I have no idea what to do next. Any hints?

share|cite|improve this question
Tiny hint:you know that $(x-1)(x+1)\equiv 0\pmod p$; when can a product of two factors be equal to $0$ modulo a prime? – Steven Stadnicki May 17 '13 at 0:02
Your step $$(x-1)(x+1)\equiv 0\pmod{n}\implies x-1=20779\text{ or }x+1=20779$$ is incorrect; there can be more than two square roots of $1$ when the modulus $n$ is not prime (as we know it is not in this setting). – Zev Chonoles May 17 '13 at 0:03
up vote 2 down vote accepted

From $(x-1)(x+1)\equiv 0 \pmod n$ you cannot conclude that $x-1 = 20779 \lor x + 1=20779$ when $n$ is not prime. You can conclude that $x-1 \equiv 0 \pmod p$ and $x+1 \equiv 0 \pmod q$ (or the other way-we could swap $p,q$) when you know that $n$ has only two prime factors unless $pq$ divides one of $x+1, x-1$. So factor $20778$ and $20780$ looking for factors that will multiply to make $3598057$. The other factors are small enough to find by hand.

share|cite|improve this answer
+1 ok, thanks a lot for help! – JosephConrad May 17 '13 at 0:43
Don't try to factor $20778$ or $20780$. Find the gcds instead; if $p | n$, $p | 20778$ or $p | 20780$. So, $p | (20778, n)$ or $p | (20780, n)$. Use Euclid's algorithm to find the gcds. – Eric Jablow May 17 '13 at 1:02
@Eric: a better approach. That will work with large multiples – Ross Millikan May 17 '13 at 1:22

From the condition (x-1)(x+1)=0 mod n

you can conclude (a) n divides (x-1), or (b) n divides (x+1), or (c) some factor of n divides (x-1) and some other factor of n divides (x+1)

Since (a) and (b) are ruled out (x is not plus or minus 1) we get two factors as f1 = gcd(x-1,n) f2 = gcd(x+1,n)

If n is not known to be a product of two primes, then one will try to factor f1 and f2 or prove their primality.

share|cite|improve this answer

Your Answer


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.