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

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?

-
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

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.

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

-