Maths Olympiad Prep

Library / /9 of 61

Number theory Difficulty 6.0 AIME, harder Prove it Canada

Problem:

An integer is digitally divisible if
(a) none of its digits is zero;
(b) it is divisible by the sum of its digits (e.g., 322322 is digitally divisible).
Show that there are infinitely many digitally divisible integers.

Solution

Solution:

Let us construct infinitely many digitally divisible integers.

Consider the integer 1111111\ldots 1 consisting of kk digits, all of which are 11 (for any k1k \geq 1). None of its digits is zero, so condition (a) is satisfied.

The sum of its digits is kk (since there are kk digits, each 11). The number itself is N=1111k times=10k19N = \underbrace{111\ldots 1}_{k\text{ times}} = \frac{10^k - 1}{9}.

We claim that NN is divisible by kk for infinitely many kk.

But even if kk does not always divide NN, we can construct other numbers. For example, consider the number N=1000k1 times1000k1 times11N = 1\underbrace{00\ldots 0}_{k-1\text{ times}}1\underbrace{00\ldots 0}_{k-1\text{ times}}1\ldots 1 (with nn blocks of 11 separated by k1k-1 zeros), i.e., N=10(n1)k+10(n2)k++100N = 10^{(n-1)k} + 10^{(n-2)k} + \cdots + 10^0. The sum of its digits is nn (since there are nn ones and the rest are zeros). But this number contains zeros, so it does not satisfy condition (a).

Instead, consider the following construction:

Let dd be any positive integer not divisible by 1010 (so that its digits are all nonzero). Let N=d×10m+d×102m++d×10kmN = d \times 10^m + d \times 10^{2m} + \cdots + d \times 10^{km}, where mm is chosen so that dd has mm digits and none of the digits of dd is zero. Then NN will have only the digits of dd repeated, so none of its digits is zero.

Alternatively, consider the following:

Let nn be any positive integer. Consider the number N=1111n1 timesN = 1\underbrace{11\ldots 1}_{n-1\text{ times}} (i.e., nn digits, all 11). The sum of its digits is nn. N=10n19N = \frac{10^n - 1}{9}. For n=9n = 9, N=111111111N = 111111111, sum of digits is 99, and 111111111111111111 is divisible by 99.

In general, for n=9kn = 9k, N=11119k timesN = \underbrace{111\ldots 1}_{9k\text{ times}} is divisible by 99, and the sum of its digits is 9k9k, so NN is divisible by the sum of its digits. Thus, for every k1k \geq 1, N=11119k timesN = \underbrace{111\ldots 1}_{9k\text{ times}} is digitally divisible.

Therefore, there are infinitely many digitally divisible integers.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.