Let $x = 2441921$. Factor $x$ into a product of primes.

194 Views Asked by At

Let $x = 2441921$. Factor $x$ into a product of primes.

I found that:
$1519^2 −x=−134560= −2^5 ·5 · 29^2$ and
$1541^2 −x=−67240= −2^3 · 5 · 41^2$.

I am trying to figure out what to do from here. How to find the product of primes with what I have found.

If I find a square closest to x being 1563^2=2442969. What should I do from here?

1

There are 1 best solutions below

2
On

You can write what you found as

$$1519^2\equiv -2^5\cdot5\cdot29^2\mod x$$ and $$1541^2\equiv-2^3\cdot5\cdot41^2\mod x$$

This implies

$$1541^2\cdot2^2\cdot29^2\equiv 1519^2\cdot41^2\mod x$$

which is to say that $x$ divides

$$(1541\cdot58+1519\cdot41)(1541\cdot58-1519\cdot41)=151657\cdot27099$$

which is to say, the factors of $x$ must be among the factors of these two numbers. Can you go from here?

(Note: one can systematically compute $\gcd(x,151657)$ and $\gcd(x,27099)$.)