Some natural numbers have a nonzero multiple that is a palindrome in base 10. For example, $106 \times 2 = 212$, which is a palindrome, and $29 \times 8 = 232$, which is also a palindrome.
Aside from 0 (which only has 0 as a multiple), are there any natural numbers that are definitively known to not have a multiple that is a palindrome?
I'm curious about this because I teach a theory of computation course and on the final exam asked students to show that the set of all natural numbers with this property is Turing-recognizable. However, I honestly have no idea what numbers are in this set, and was wondering if this was a known open problem or if the solution was known.
Thanks!
Best Answer
Well, any non-zero multiple of $10$ will give trouble! It must end in $0$, and unless we pad the front with $0$'s, we cannot get a palindrome.
If $a$ is relatively prime to $10$, then $a$ divides the extremely palindromic $10^k-1$ for some $k$. This can be proved by using Euler's Theorem, which says that in that case $10^{\varphi(a)} -1$ is divisible by $a$. Here $\varphi$ is the Euler $\varphi$-function.
Remark: If we allow front padding by $0$'s, we can always find a palindromic multiple of $a$. If $a$ is divisible by neither $2$ nor $5$, that is dealt with above. Otherwise, multiply $a$ by $2$'s or $5$'s until we get a number of the form $b\times 10^k$, where $b$ is relatively prime to $10$. Some multiple of $b$ is all $9$'s. So some multiple of $b\times 10^k$ is almost palindromic, except for trailing $0$'s. It can be made palindromic by padding with leading $0$'s.
We saw that if we want a fully palindromic multiple, $a$'s divisible by $10$ are no good. But it seems plausible that unless $a$ is divisible by both $2$ and $5$, it has a palindromic multiple.