2010 AIME I Problem 2

Attempt Problem 2 of the 2010 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2010 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

2.

Find the remainder when 9⋅99⋅999⋅⋯⋅99…9⏟999 nines9 \cdot 99 \cdot 999 \cdot \cdots \cdot \underbrace{99\ldots9}_{\text{999 nines}} is divided by 1000.1000.

Answer: 109
Concepts:modular arithmeticpattern recognition
Difficulty rating: 1950
Small Hint:

Every factor from the third one on ends in at least three 99s, so it is ≡−1(mod1000)\equiv -1 \pmod{1000}

Big Hint:

Count how many factors are ≡−1(mod1000)\equiv -1 \pmod{1000} and check whether that count is odd or even; only 9⋅999 \cdot 99 remains to compute

Solution:

Work modulo 1000.1000. Every factor from the third one on ends in at least three 99s, so each is ≡−1(mod1000).\equiv -1 \pmod{1000}. There are 999999 factors in all, hence 997997 of them are ≡−1.\equiv -1.

The product is therefore ≡9⋅99⋅(−1)997≡−891≡109(mod1000), \begin{aligned} &\equiv 9 \cdot 99 \cdot (-1)^{997} \\ &\equiv -891 \equiv 109 \pmod{1000}, \end{aligned} so the remainder is 109.109.

Problem 1#1
Full Exam

Problem 2 in Other Years