# Which sets of base 10 digits have the property that, for every $n$, there is a $n$-digit number made up of these digits that is divisible by $5^n$?

Which sets of non-zero base 10 digits have the property that, for every $n$, there is a $n$-digit number made up of these digits that is divisible by $5^n$?

Any set of digits which form a complete residue set modulo 5. In particular, any 5 consecutive digits.

A proof by induction is not too difficult.

• $\{0,5\}$ looks like one such set, because $5 \mid 10 \Rightarrow 5^n \mid 10^n \Rightarrow 5^{n+1} \mid 5\cdot 10^n$ where $10^n$ has $n+1$ digits and so $5\cdot 10^n$ has. – rtybase Jan 14 '18 at 23:03
• Good point. I think I'll make the question harder. – marty cohen Jan 14 '18 at 23:31
• I would bet that you must have $0$, which makes any superset of $\{0,5\}$ be the only answer. As $n$ gets large it gets impossible to avoid $0$, but that is hard to prove. – Ross Millikan Jan 14 '18 at 23:45
• Look at my solution to the original problem. – marty cohen Jan 15 '18 at 2:39
• @marty cohen: I didn't see your edit (so my answer was independent of that). Initially, I had a program which got an answer of no solutions, and when I realized it had a bug, the data led me to the proof I posted below. But now that I see that the result I posted is a result you already had, let me know if you would prefer for me to delete my answer. – quasi Jan 15 '18 at 4:58

Partial result . . .

Claim:

If $S \subseteq \{1,2,3,4,5,6,7,8,9\}$ contains a complete residue system, mod $5$, then for all positive integers $n$, there is an $n$-digit number $x$ such that

• All digits of $x$ are elements of $S$.$\\[4pt]$
• $5^n{\mid}x$.

Proof:

Assume $S \subseteq \{1,2,3,4,5,6,7,8,9\}$ contains a complete residue system, mod $5$.

Necessarily $5 \in S$, hence the claim holds for $n=1$.

Proceed by induction on $n$.

Fix $n \ge 1$, and let $x$ be an $n$-digit number such that all digits of $x$ are elements of $S$, and $5^n{\mid}x$.

Let $y ={\large{\frac{x}{5^n}}}$.

Choose $d \in S$ such that $d(2^n) + y \equiv 0\;(\text{mod}\;5)$.

Let $x'=d(10^n)+x$.

Then $x'$ is an $(n+1)$-digit number, all of whose digits are elements of $S$. \begin{align*} \text{Also,}\;\;x'&=d(10^n)+x\\[4pt] &=(5^n)(d(2^n)+y)\\[4pt] \end{align*} which is a multiple of $5^{n+1}$.

Thus, the induction is complete.

Update:

For $S \subseteq \{1,2,3,4,5,6,7,8,9\}$, call $S$ qualifying if for every positive integer $n$, there is an $n$-digit number $x$ such that

• All digits of $x$ are in $S$.$\\[4pt]$
• $5^n{\mid}x$.

As was shown, if $S \subseteq \{1,2,3,4,5,6,7,8,9\}$, and $S$ contains a complete residue system, mod $5$, then $S$ is qualifying.

For $S \subseteq \{1,2,3,4,5,6,7,8,9\}$, call $S$ a minimal exception if

• $S$ is a qualifying set.$\\[4pt]$
• $S$ does not contain a complete residue system, mod $5$.$\\[4pt]$
• No proper subset of $S$ is qualifying.

Conjecture:

There are exactly $11$ minimal exceptions, as listed below: \begin{align*} &\{1, 2, 3, 5, 6, 7\}\\[4pt] &\{1, 2, 3, 5, 6, 8\}\\[4pt] &\{1, 2, 3, 5, 7, 8\}\\[4pt] &\{1, 2, 5, 6, 7, 8\}\\[4pt] &\{1, 2, 5, 6, 7, 9\}\\[4pt] &\{1, 3, 5, 6, 7, 8\}\\[4pt] &\{2, 3, 4, 5, 7, 9\}\\[4pt] &\{2, 3, 5, 6, 7, 8\}\\[4pt] &\{2, 3, 5, 7, 8, 9\}\\[4pt] &\{2, 4, 5, 6, 7, 9\}\\[4pt] &\{3, 4, 5, 7, 8, 9\}\\[4pt] \end{align*} Remarks: All of the above sets survived testing for $1 \le n \le 10000$.