2006 iTest Problems/Problem 28

Problem

The largest prime factor of $999999999999$ is greater than $2006$. Determine the remainder obtained when this prime factor is divided by $2006$.

Solution

Note that $999999999999 = 10^{12} - 1$. This expression can be factored with difference of squares and sum/difference of cubes. \begin{align*} 10^{12} - 1 &= (10^6 + 1)(10^6 - 1) \\ &= (10^2 + 1)(10^4 - 10^2 + 1)(10^3 - 1)(10^3 + 1) \end{align*} Note that since $10^3 - 1, 10^3 + 1, 10^2 + 1$ are all less than $2006$, none of them are the wanted factors. The only option left is $10^4 - 10^2 + 1 = 9901$. By doing a prime check (or noting that if $9901$ has factors larger than 5, then the largest prime factor of the original number can not be greater than $2006$), we confirm that $9901$ is the largest prime factor of $999999999999$. The remainder when $9901$ is divided by $2006$ is $\boxed{1877}$.

See Also

2006 iTest (Problems, Answer Key)
Preceded by:
Problem 27
Followed by:
Problem 29
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10