Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Write $1001001001$ as $1001 \times (10^6+1)$ –  Kirthi Raman Mar 25 '12 at 2:07
add comment

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.