Show that for any n > 1 there is an n digit number with all digits non-zero which is divisible by the sum of its digits.
Solution
Two building blocks are needed. The first is that the number an with 3n digits, all 1, is divisible by 3n. This is an easy induction. It is true for n = 1 because 111 = 3·37. But an+1 = an x 10...010...01 and 10...010...01 has sum of digits 3 and hence is divisible by 3, so an+1 is divisible by one more power of 3 than an.
The second is that if we multiply the number 9...9 made up of k 9s by any number with not more than k digits and last digit non-zero, then the result has digit sum 9k. For suppose we multiply by a1 ... aj with j <= k. Then the product is (10k - 1) a1...aj = a1...aj-1(aj-1)9...9(9-a1)(9-a2)...(9-aj-1)(10-aj), where there are k-j 9s in the middle. The product has k + j digits and digit sum 9k.
So given any n, take k so that 3k ≤ n < 3k+1. Then either 3k ≤ n ≤ 2.3k or 2.3k < n < 3k+1. In the first case, if n = 3k, then we are done (we can take the number with n 1s). So assume j = n - 3k > 0. Take N = 9...9 x 1...12, where the first factor has 3k9s and the second factor has j-1 1s and one 2. We have just established that N has n digits and digit sum 3k+2. But 3k divides the number with 3k 1s and so 3k+2 divides the number with 3k 9s and hence also N (which is a multiple of that number). Note that, to be explicit, N = 1...19...98...8, where we have n - 3k 1s, 2.3k - n, 9s and n - 3k 8s.
In the second case, let j = n - 2.3k. Take N = 9...9 x 2...2, where the first factor has 2.3k 9s and the second factor has j 2s. We have established that N has n digits and digit sum 2.3k+2. Clearly 2 divides 2...2. But 9...9 = 9 x 1...1 x (10m + 1), where the second factor has 3k + 1 1s, and so is divisible by 3k. Hence the product of the first two factors is divisible by 3k+2. Hence N is divisible by 2.3k+2 as required. To be explicit, we have N = 2...219...97...78, where there are (j-1) 2s, (j-1) 7s, one 1, and (2.3k - j) 9s.
Comment. Canada 84/3 was similar (but easier). It asked for infinitely many numbers divisible by the sum of their digits (all non-zero). So the obvious answer was the number made up of 3n 1s.
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2002