# Square roots, prime factorization

I´m stuck in my homework and since its homework, I would rather get some hints than full solution. The problem goes:

factorize n = 88416763 in case that you know that the square roots of 51733469 (mod 88416763) are 50224876, 38191887, 22222, 88394541.

Following CodesInChaos request to turn the hint into a full solution, here's a full solution. Let $x$ and $y$ be square roots of $51733469$ modulo $n$. It follows that

$$0\equiv x^2-y^2=(x+y)(x-y)\,(\textrm{mod }n).$$

If we choose $x\not\equiv \pm y\, (\textrm{mod }n)$, then $x-y$ and $x+y$ are not divisible by $n$. On the other hand, $n\mid (x+y)(x-y)$, so $\gcd(x+y,n)\neq 1\neq \gcd(x-y,n)$. Choosing for instance $x = 38191887$ and $y=22222$ gives

$$\gcd(x-y,n) = 8887,\;\; \gcd(x+y,n)=9949.$$

A direct computation shows that $n=88416763 = 8887\times 9949$. It's easy to use the Sieve of Eratosthenes to calculate all primes smaller than $100$ and then check if any of them divide either factor, which will show that $8887$ and $9949$ are both prime.

• so when I know that (x-y)(x+y)=0 mod p and (x-y)(x+y)=0 mod q how can i find q and p? Nov 4 '14 at 13:17
• What happens when $(x+y)(x-y)=0\,\textrm{mod }N$ and you know that $|x+y|,|x-y|<N$? Nov 4 '14 at 13:23
• well than x+y=0 mod p and x-y=0 mod q Nov 4 '14 at 13:34
• so what can you say about greatest common divisors? Nov 4 '14 at 13:40
• oh ofc I just make gcd((x+y),(N-(x+y)) and i get p. Thank you for your time Nov 4 '14 at 13:48