Find the largest divisor of $1001001001$ that does not exceed $10000$.
-
2$\begingroup$ Write $1001001001$ as $1001 \times (10^6+1)$ $\endgroup$ – Kirthi Raman Mar 25 '12 at 2:07
First we observe that
$$1001001001 = 1001 \times 10^6 + 1001 = 1001(10^6+1)$$
The factors of $1001$ are $7, 11,$ and $13$.
In order to find factors of $(10^6+1)$, we look at the factorization of $(x^6+1)$
$$(x^6+1) = ((x^2)^3+1) = (x^2+1)(x^4-x^2+1) \tag{A}$$
Applying $(A)$ to find factors of $(10^6+1) = 101 \times 9901$
Finally we can write $1001001001$ as
$$1001001001 = 7 . 11 .13 . 101 . 9901$$
Besides $9901$, we find that $77,91,143,707,1001,1111,1313,7777$ and $9191$ are the only divisors of $1001001001$ that are less than $10000$, therefore the largest divisor of $1001001001$ that does not exceed $10000$ is $9901$.