Do all natural numbers have a nonzero multiple that is a palindrome in base 10?

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.

If $n$ is a multiple of $10$, it cannot have any multiple which is a palidrome. Otherwise, $n$ is divisible by 2 but not 5, OR by 5 but not 2 OR is relatively prime to $10$.

• Any number $n$ which is relatively prime to $10$ has a multiple which can be written only with 1, and a simple proof can be found here:

A natural number multiplied by some integer results in a number with only ones and zeros

• If $2|n$ but $5 \nmid n$. Let $k$ be the power of $2$ in n. Then $n=2^kn_0$ where $n_0$ is relatively prime to $10$. Let $m$ be the "backwards" $n$, that is the digits of $n$ written backwards. For example, if $n=124$ then $m=421$.

Consider the numbers $m, mm,mmm, ..,mmm..m$ obtained by writing $m$ after n$

[for example if $n=124$ then $m=421$ and I am looking at the set

$$\{ 421, 421421, 421421421 ,...\} \,]$$

By the pigeon hole principle, two numbers in our set have the same remainder when divided by $n_0$, thus their difference $mmmm00000.000$ is divisible by $n_0$. In particular, since $n_0$ is relatively prime to 10, $n_0$ divides $mmmm..m$.

Hence the number

$$mmmm..m0000000n..nnnn$$

is a palidrome, and it is a multiple of $n$ whenever $$mmmm..m0000000n..nnnn-nnnn.n=mmm...m0000000.00000$$ contains at least $k$ zeroes at the end.

• If $5|n$ but $2 \nmid n$. Let $k$ be the power of $5$ in n. Then $n=5^kn_0$ where $n_0$ is relatively prime to $10$.

Repeat the argument above.

P.S. The entire argument is based on the following observation: if $m$ is any combination of digits, and $n$ is relatively prime to $10$, then $n$ has a multiple of the form $mmmm...mmm$ [repetition, not multiplication]....

This is basically proven above, but it is proven exactly as in the link provided.

P.P.S. To sum it up, if $n$ is not a multiple of $10$ it has a multiple which is a palidrome. If $n$ is a multiple of $10$, if interested, you can prove the same way that $n$ has a multiple which is of the form palidrome followed by zeroes....