after helping a friend solve a homework, I asked myself the following question:

$H\subseteq\{1,2,\ldots,9\}$, $T(H)=\{n\in\mathbb{N}:$ all the digits in the decimal representation in $n$ belong to $H\}$.

What is the minimum possible number of elements in $H$, if we know that every $10 \not |n$ has a multiple in $T(H)$?

So far I have proved that $5$ elements are enough (nice exercise btw.)

Any ideas on the answer?

(I tried to look at the multiples of $5^7$, but so far did not manage to find a suitable multiple)

For relatively prime numbers (to $10$), $H=\{1\}$ is enough by Euler-Fermat.

$4\not |22$, $8\not| 444$, $4\not 66$ and $16\not| 8888$ proves that $1$ digit is not enough for $n=2^km$, where $gcd(10,m)=1$, and $\{1,2\}$ is enough.

And for $n=625$, the last $3$ digits are always different, so only the $3$ sets: $\{1,2,5\}, \{6,2,5\},\{8,7,5\}$ could be possible. I tested some cases, for $n=5^7$, none of these sets gave a suitable multiple up to $k=10^6$

It would be enough to prove find the necessary number for the powers of $5$, as there is a simple construction from that point on, making use of $(10,m)=1\Rightarrow m\left|\frac{10^{\varphi(9m)-1}}{9}\right.$

  • $\begingroup$ "For relatively prime numbers," you mean, of course, relatively prime to $10$. $\endgroup$ – Thomas Andrews May 13 '15 at 4:22

Your Answer

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

Browse other questions tagged or ask your own question.