2007 AMC 10B Problem 24

Divisibility by $4$ is decided by the last two digits. Of the endings $44, 49, 94, 99$, only $44$ is a multiple of $4$, so $n$ ends in $44$.

Divisibility by $9$ is decided by the digit sum. Each $9$ contributes $9$, which is already a multiple of $9$, so the digit sum is a multiple of $9$ exactly when $4 \times (\text{number of } 4\text{'s})$ is, that is, when the number of $4$'s is a multiple of $9$. There must be at least one $4$, hence at least nine $4$'s.

Now minimize. The number must have at least one $9$ and at least nine $4$'s, so at least $10$ digits, and a $10$-digit number beats any longer one. Among $10$-digit numbers with nine $4$'s and one $9$, the smallest puts the $9$ as far right as possible; since the last two digits must be $44$, the $9$ goes in the third position from the right:
$$n = 4444444944.$$
This is divisible by $4$ (ends in $44$) and by $9$ (digit sum $9 \cdot 4 + 9 = 45$).

Its last four digits are $4944$.

The answer is $\boxed{\textbf{(C)}\ 4944}$.

Digit-based divisibility rules translate the two conditions into constraints on the ending and on the digit count. To find the smallest number, minimize the number of digits first, then push the larger digit as far right as the constraints allow. Note that many candidates share the answer's ending, so shortcuts based only on the last four digits would be unreliable.

• Testing candidates with fewer than ten digits, or ending the number in 94 or 9 (44 is the only ending of 4's and 9's divisible by 4).
• Forgetting the "at least one of each" requirement and answering $4444$ for the all-$4$'s number $444444444$.