3
$\begingroup$

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

  • 2
    Write $1001001001$ as $1001 \times (10^6+1)$2012-03-25

1 Answers 1

9

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