Solution to MP67
March 2007

The problem:

Prove that there are infinitely many integers such that
            (i) the number is divisible by the sum of its digits, and
            (ii) none of its digits are zero.

This month's problem appeared as problem 3 on the 1984 Canadian Math Olympiad.  Correct solutions came from

Solution.  Since there are easy divisibility rules for powers of 2 and of 5, and for appropriate multiples of 3 and of 9, these rules formed the basis for the submitted solutions.  The most common approach among our correspondents, which was also featured in the official solutions to the 1984 CMO, was to start with any number that satisfied the two given conditions, such as n = 1 or n = 12, and form a number with 3 times as many digits by concatenating three copies of your starting number.  In our examples we get 111 or 121212.  One then observes that the new number is divisible by the sum of its digits, which equals 3 times the sum of the digits of the old number (namely, in our examples, 3 = 3·1 or
9 = 3·(1+2)).  Here is our algorithm in greater detail:

Let  n be any number that is divisible by the sum of its digits, none of which are 0, and
            d be the number of digits (in the decimal representation of n), and
            s be the sum of those d digits.

Then the number n(10^2d + 10^d + 1) is divisible by 3s since (a) 10^2d + 10^d + 1 (which equals 100...100...1) is divisible by 3 (recall that 3 divides a number if and only if it divides the sum of its digits, which here equals 3), and (b) n is divisible by s (by our definition of n).  We observe that n(10^2d + 10^d + 1) is the number consisting of the number n repeated 3 times, so the sum of its digits is 3s.  This process can be repeated ad infinitum. 
            Here is our example starting with n = 12, in which case d = 2 and s = 3.  The next number in the infinite sequence is 12(10⁴ + 10² +1) = 12(10101) = 121212, which is divisible by the sum of its digits, namely 3·3 = 9.  The next number is 121212(10¹² + 10⁶ + 1) = 121212...12 (with nine 12's), which is divisible by 3·9 = 27.  And so on.  (The sequence starting with n = 1 = d = s is easier to check: 1, 111, 111111111, ... ; the kth term of the sequence, starting with k = 0, is composed of 3^k one's.)

Generalization by Matthew Lim.
The argument presented above works for any base b as long as b > 2.  Instead of using 3 copies of the initial number, one uses d copies, where d is any divisor of b –1.  Lim shows that if s is the sum of the digits of the initial number in its base-b representation, then d^k copies of the initial number has a digit sum of s·d^k that divides the number.  He goes on to provide a nice proof that b = 2 is a genuine exception: any base-2 number without any digit 0 is necessarily a string of 1's, namely 2^k – 1.  The sum of the digits of 2^k – 1 is k, but with a bit of number theory one can show that k divides 2^k – 1 for no k > 1.

The sequence of Jean-Luc Luyet.
Only Luyet provided an infinite sequence based on the rule that an integer is divisible by 2 if and only if the number formed by its final n digits is divisible by 2ⁿ.  The basic plan is to use numbers whose right-most n digits form a multiple of the number 2ⁿ, then adjoin enough 1's (or any other numbers) to the left so that the sum of the digits equals 2ⁿ.  The only complication is that we must insure that none of the digits we use is a 0.  Since a power of 2 never ends in 0, we can add multiples of 2ⁿ to get rid of unwanted 0's.  An example will make this clear: For divisibility by 24 = 16, we require the last four digits of our number to be divisible by 16.  So just add 100·16 + 16 = 1616 and we have our final four nonzero digits.  We now want a number whose digit sum equals 16, so we can use 21616 (or 111616).  Another example: for 32 we can add 1000·32 + 100·32 + 32 = 35232 to obtain the right-most five digits, then adjoin 89 to the left to obtain 8935232, which is divisible by the sum of its digits, namely 32.  In general, if the right-most zero is in the position 10^k, use 2ⁿ + 10^k·2ⁿ to get rid of it.  Continue to add appropriate multiples of 2ⁿ — which is always possible because the final digit of 2ⁿ is never 0 — until the right-most n digits forms a number that is a multiple of 2ⁿ, no digit of which is zero.