Find the largest divisor of $1001001001$ that does not exceed $10000$.

Question

Find the largest divisor of $1001001001$ that does not exceed $10000$.

Answer 1

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