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. 10k - 1 is also coprime to 10 for any k > 0, so we can find a positive integer h such that 10h = 1 mod m(10k - 1). Hence also 10kh = 1 mod m(10k - 1). But (10kh - 1) = (10k - 1)(10k(h-1) + 10k(h-2) + ... + 10k + 1), so 10k(h-1) + 10k(h-2) + ... + 10k + 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 22t+1. For t = 1, we may take 8. Suppose M has t non-zero digits and is a multiple of 22t+1. Consider the numbers 2.102t + M, 4.102t + M, 6.102t + M, 8.102t + M. All are wobbly with t+1 non-zero digits and divisible by 22t+1. Since 2.102t = 22t+1 mod 22t+3, one of them will be divisible by 22t+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 = 2sM, where M is odd and not divisible by 5. Take a wobbly number of t non-zero digits divisible by at least 2s. Then multiply it by (*) with k = 2t.
© John Scholes
jscholes@kalva.demon.co.uk
18 Sep 2002