Maths Olympiad Prep

Library / /18 of 35

Number theory Difficulty 5.5 AIME, harder Prove it Slovenia

For which positive integers nn does there exist a multiple of 13, 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 1313. Let us try and find a multiple of 1313 such that the sum of its digits will be equal to 22. This number must have two digits equal to 11 and the remaining digits must be 00. We check the first few positive integers with this property. The numbers 1111, 101101 and 110110 are not divisible by 1313, but 10011001 is.

Similarly, let us try and find a positive integer mm with the sum of the digits equal to 33. Let m=10a+10b+10cm = 10^a + 10^b + 10^c where abca \ge b \ge c. The remainder of 10210^2 when divided by 1313 is 99. The remainder of 10310^3 when divided by 1313 is 1212. For 10410^4 we get 33, for 10510^5 we get 44 and for 10610^6 we get 11. The sum of the remainders given by 10210^2, 10410^4 and 10610^6 is 1313, so 1313 divides 101010101010.

Any number of the form 1001100110011001\,1001\ldots1001 with kk repetitions of 10011001 is a multiple of 10011001, so it is also a multiple of 1313. The sum of its digits is equal to 2k2k. Any number of the form 10101010011001101010\,1001\ldots1001 where 101010101010 is followed by kk repetitions of 10011001 is also a multiple of 1313 and has the sum of the digits equal to 3+2k3 + 2k.

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.