A *wobbly* number is a positive integer whose digits are alternately zero and non-zero with the last digit non-zero (for example, 201). Find all positive integers which do not divide any wobbly numbers.

**Solution**

Answer: multiples of 25 and multiples of 10.

A multiple of 10 ends in 0, so can never be wobbly. A multiple of 25 ends in 25, 75, 50 or 00, so cannot be wobbly. So these numbers certainly satisfy the condition. We have to prove that no other numbers satisfy it.

If m is not divisible by 2 or 5, then it is coprime to 10. 10^{k} - 1 is also coprime to 10 for any k > 0, so we can find a positive integer h such that 10^{h} = 1 mod m(10^{k} - 1). Hence also 10^{kh} = 1 mod m(10^{k} - 1). But (10^{kh} - 1) = (10^{k} - 1)(10^{k(h-1)} + 10^{k(h-2)} + ... + 10^{k} + 1), so 10^{k(h-1)} + 10^{k(h-2)} + ... + 10^{k} + 1 is a multiple of m (*).

We show by induction that we can find a wobbly number with t non-zero digits which is a multiple of 2^{2t+1}. For t = 1, we may take 8. Suppose M has t non-zero digits and is a multiple of 2^{2t+1}. Consider the numbers 2.10^{2t} + M, 4.10^{2t} + M, 6.10^{2t} + M, 8.10^{2t} + M. All are wobbly with t+1 non-zero digits and divisible by 2^{2t+1}. Since 2.10^{2t} = 2^{2t+1} mod 2^{2t+3}, one of them will be divisible by 2^{2t+3}. So we can obtain wobbly numbers which are divisible by arbitrarily large powers of 2.

Now any number which is not a multiple of 10 or 25 is either (1) odd and not divisible by 5, or (2) odd and divisible by 5, but not 25, or (3) even and not divisible by 5. For (1) we may take (*) with k = 2. For (2) take (*) with k = 2 for m/5 and multiply it by 5. For (3), suppose m = 2^{s}M, where M is odd and not divisible by 5. Take a wobbly number of t non-zero digits divisible by at least 2^{s}. Then multiply it by (*) with k = 2t.

© John Scholes

jscholes@kalva.demon.co.uk

18 Sep 2002