Maths Olympiad Prep

Library / /20 of 35

Number theory Difficulty 5.6 AIME, harder Prove it Slovenia

For which positive integers nn does there exist a multiple of 77, such that the sum of its digits is equal to nn?

Solution

Any number with the sum of the digits equal to 11 is a power of 1010, so it cannot be a multiple of 77. Let us try and find a multiple of 77 such that the sum of its digits will be equal to 22. This number must have two digits equal to 11. We check the first few positive integers with this property. The numbers 1111, 101101 and 110110 are not divisible by 77, but 10011001 is.

The positive integer 10011001100110011001\ldots1001, made by kk repetitions of the number 10011001, has the sum of the digits equal to 2k2k and is obviously a multiple of 10011001. Hence, it is also a multiple of 77. We conclude that for all even positive integers nn there exists an integer mm, which is a multiple of 77 with the sum of its digits equal to nn.

It is easy to find a multiple of 77 with the sum of the digits equal to 33. The number 2121 has these properties. Any number of the form 211001100110012110011001\ldots1001, which consists of 2121 followed by kk repetitions of 10011001, has the sum of the digits equal to 3+2k3 + 2k and is a multiple of 77. So, for all odd positive integers n>1n > 1 there exists an integer mm, which is a multiple of 77, such that the sum of the digits of mm is equal to nn.

We have shown that all positive integers nn except 11 have the required property.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.