divisibility - Determine all $n$-digit numbers that are divisible by the cyclic permutations of its digits

Given an integer $n \geq 2$, determine all $n$-digit numbers $M_0 = \overline{a_1a_2 \ldots a_n}$ $(a_i \neq 0, i = 1,2,\ldots,n)$ divisible by the numbers $M_1 = \overline{a_2a_3 \ldots a_na_1}$, $M_2 = \overline{a_3a_4\ldots a_na_1a_2},\ldots,M_{n-1} = \overline{a_na_1a_2 \ldots a_{n-1}}$.

We first note that $a_i \leq 4$ for $i > 1$ unless $a_1 = \cdots = a_n$ where $a_1 > 4$. Thus assuming that is not the case, $M_0 \leq \underbrace{84\ldots4}_{n-1 \text{ 4s}}$.

What do I do from here?

Answer

Suppose $M_i = k_iM_0$ for $i = 1, 2, \cdots, n - 1$, and we let $k_0 = 1$. Since $a_i \neq 0$, so $k_i \neq 0$.

Case 1: if $k_i = k_j$ for some $i < j$. Claim: this will be reduced to the same question with $n' = j - i$.

Proof: Since $k_i = k_j$, so $M_i = M_j$. Denote $x = \overline{a_{i + 1} \cdots a_j}$, and $y = \overline{a_{j + 1} \cdots a_{j + n'}}$

$$\overline{xa_{j + 1}a_{j + 2}\cdots} = M_i = M_j = \overline{ya_{j + n' + 1}a_{j + n' + 2}\cdots} \Rightarrow x = y$$

Using the same argument shows that $M_i = \overline{xx \cdots xx}$, i.e. a repeating of the segment $x$. Then now $x$ (possibly a reordering of $x$) is a solution to the same problem for a smaller $n'$.

Case 2: if $k_i \neq k_j, \forall i$. Clearly $k_i < 10$ because of the number of digits. So $k_i \in \{1, \cdots, 9\}$. So $n \leq 9$. Claim: there is no solution.

Proof: We first claim that $a_1 = \max\{a_i\}$. If not, suppose $a_t > a_1$, then

$$M_{t - 1} \leq k_{t - 1}M_{t - 1} = M_0 < (a_1 + 1)10^{n - 1} \leq a_t10^{n - 1} \leq M_{t - 1},$$

a contradiction. Therefore $a_1 = \max\{a_i\}$. Then

$$(\sum_{i = 0}^{n - 1}10^i)na_1 \geq (\sum_{i = 0}^{n - 1}10^i)(\sum_{i = 1}^na_i) = \sum_{i = 0}^{n - 1}M_i = (\sum_{i = 0}^{n - 1}k_i)M_0 \geq (\sum_{i = 0}^{n - 1}k_i)10^{n - 1}a_1 \geq (n + 1)10^{n - 1}a_1.$$

Cancel $a_1$ on both sides of the inequality, we have

$$(\sum_{i = 0}^{n - 1}10^i)n \geq (n + 1)10^{n - 1} \Rightarrow n \geq (\sum_{i = 1}^{n - 1}10^{-i})^{-1} > 9,$$

a contradiction.

In conclusion, with only Case 1 possible, using induction on $n$, we will end up with the only solution $M_0 = \overline{aa\cdots aa}$.