2015 AIME II Problems/Problem 3

Problem

Let be the least positive integer divisible by whose digits sum to . Find .

Solution 1

The three-digit integers divisible by , and their digit sum:

Thus the answer is .

Solution 2 (Faster)

We can do the same thing as solution 1, except note the following fact: is a multiple of and its digits sum to .

Therefore, we can add it onto an existing multiple of that we know of to have , shown in the right-hand column, provided that its units digit is less than and its hundreds digit is less than . Unfortunately, does not fit the criteria, but does, meaning that, instead of continually adding multiples of , we can stop here and simply add to reach our final answer of .

~Tiblis

Solution 3

The digit sum of a base integer is just . In this problem, we know , or for a positive integer .

Also, we know that , or .

Obviously is a solution. This means in general, is a solution for non-negative integer .

Checking the first few possible solutions, we find that is the first solution that has , and we're done.

Solution 3

Since the sum of the digits in the base-10 representation of is , we must have or . We also know that since is divisible by 17, .

To solve this system of linear congruences, we can use the Chinese Remainder Theorem. If we set , we find that and , because . The trick to getting here was to find the number such that , so that when we take things , the goes away. We can do this using the Extended Euclidean Algorithm or by guess and check to find that .

Finally, since , we repeatedly add multiples of until we get a number in which its digits sum to 17, which first happens when .

See also

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.