Whats the lowest multiple of $99$ that has digits of only $0, 1$, and $ 2$

elementary-number-theoryintegers

I was doing a programming problem which is

For a positive integer $n$, define $f(n)$ as the least positive multiple of n that, written in base 10, uses only digits $≤ 2$.

Thus $f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.$

When my program reached 99, it was unable to go any further because my program was unable to find a multiple of 99 that fit the following condition. Is it just my programs fault or does 99 not have a multiple where its digits are under 2

Best Answer

The smallest such multiple is 1122222222.

Claim: The number we are looking for has at least ten digits.

Proof: Assume that there is a counterexample with at most nine digits. Then the sum of digits is at most 18, and 18 is only attained by the example 222222222, which is not divisible by 11. So the sum of digits must be 9 in a counterexample. In particular, the sum of digits with alternating signs is between -9 and 9, and it is divisible by 11. So the sum of digits with alternating signs is 0. But this is a contradiction $\pmod 2$: the parity of the sum and the sum with alternating signs should coincide.

So we need 10 digits. The same argument as above shows that the sum of digits cannot be 9. But it is at most 20, so the sum of digits is 18. Again, by the same argument as above, the sum of digits with alternating signs is 0 (between -18 and 18, this time it is even, and divisible by 11).

If there is no digit 1, then there are nine 2's. But then the sum with alternating signs has a different number of 2's with plus and minus sign. So digit 1 is used, and then there must be at least two of them to obtain an even sum. As the sum of digits is 18, there must be two 1's and eight 2's. The smallest number that we can produce from these digits is 1122222222, which is divisible by 99.