6
$\begingroup$

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$?

This is an extension of Prove that for any integer $n>0$, there exists a number consisting of 1's and 2's only, which is divisible by $2^n$.

Here is my answer:

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.

$\endgroup$
  • 3
    $\begingroup$ $\{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. $\endgroup$ – rtybase Jan 14 '18 at 23:03
  • $\begingroup$ Good point. I think I'll make the question harder. $\endgroup$ – marty cohen Jan 14 '18 at 23:31
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 14 '18 at 23:45
  • 1
    $\begingroup$ Look at my solution to the original problem. $\endgroup$ – marty cohen Jan 15 '18 at 2:39
  • 1
    $\begingroup$ @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. $\endgroup$ – quasi Jan 15 '18 at 4:58
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.