Find the largest divisor of $1001001001$ that does not exceed $10000$.
Find the largest divisor of $1001001001$ that does not exceed $10000$.
3
$\begingroup$
elementary-number-theory
-
2Write $1001001001$ as $1001 \times (10^6+1)$ – 2012-03-25
1 Answers
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$.