A wobbly number is a positive integer whose $digits$ in base $10$ are alternatively non-zero and zero the units digit being non-zero. Determine all positive integers which do not divide any wobbly number.
Problem
Source:
Tags: Divisibility Theory
25.05.2007 03:24
We show inductively for every $k$, there is a wobbly number $w_k$ having $2k-1$ digits such that $4^k$ divides it, but $2\cdot 4^k$ doesn't. $k=1$: just take $w_1=4$. For any $k$, we try to set $w_{k+1} = m_k\cdot 100^k+w_k$, $m_k \in \{1,2,...,9\}$. We want that $4^{k+1} \equiv w_{k+1} = m_k\cdot 100^k+w_k = m_k \cdot 4^k \cdot 25^k + 4^k w^\prime_k \mod 2\cdot 4^{k+1} $ (here $w_k=4^k w^\prime_k$ for some odd $w^\prime_k$). But that just means $4 \equiv m_k \cdot 25^k + w^\prime_k \mod 8$, which has a solution $m_k \mod 8$, meaning that we can choose our $m_k$ as required. Now if $s$ is some wobbly number and $n$ some integer coprime to $2,5$, then we find a multiple of $s$ being a wobbly number divisible by $sn$: Let $s$ have $2j-1$ digits and see that $s_k := \sum_{m=0}^{k-1} 100^{j\cdot m} s$ is wobbly again. But $s_k = s \cdot \frac{100^{kj}-1}{100^j-1}$, so we just have to take $k=\varphi((100^j-1)\cdot n)$ to get $100^{kj} \equiv 1 \mod ((100^j-1)\cdot n)$ and thus the result. The first two paragraphs show that for every integer $n$ coprime to $2,5$ we have that $n$, $5n$ ($s=5$ is wobbly) and $2^k n$ have multples being wobbly numbers. No wobbly number can be a multiple of $25$ because all multiples of that number end in $00,25,50,75$, not being allowed. Similar, no wobbly multiple of $10$ exists. As a result, exactly those $n$ have wobbly multiples that are not divisible by $10$ or $25$.