I was working on the classic number theory problem "for any integer $n$, it has a multiple whose base $10$ representation consists of only $1$s and $0$s" (for anyone who stumbles on this post looking to solve this, consider the pigeonhole principle). The book I am working on then asks to prove that the same holds for the digits $0$ and $k$, but for no other pair of digits. This isn't so bad, as there are ready counterexamples for all pairs (consider some numbers that require certain digits to be in their multiples).
However, outside of these obvious counterexamples, I was wondering if the statement were true. For example, a counterexample to the pairs $(2,5)$, $(4,5)$, $(6,5)$, and $(8,5)$ is $n = 10$, though any multiple of $10$ will do. However, the statement appears to be true for most integers that are not divisible by $10$. The only other counterexamples I have found so far are odd multiples of $125$ (noting that even multiples are also multiples of $10$). That these are the only counterexamples seems to be a reasonable conjecture based on some code I've written (I've checked up to $n = 10000$), but I'm not sure why this is true. Based on those results, I have some example conjectures:
- For any integer $n$ that is not a multiple of $10$ or a multiple of $125$ have a multiple that can be written in base $10$ with only the digits $2$ and $5$.
- For any integer $n$ that is not a multiple of $10$ or a multiple of $25$ have a multiple that can be written in base $10$ with only the digits $4$ and $5$ (this statement also applies for $6$ and $5$ and $8$ and $5$).
There are other statements we could make for other pairs but I'll leave them for now.
I do have some progress on these statements. For example, both statements are true for $n$ that are coprime to $10$ as there is a number consisting of only $1$s that is a multiple of $n$, and so by multiplication there is a number consisting of only whatever digit we want that is a multiple of $n$. However, this doesn't answer why it is true for most numbers that do have a common factor with 10. Does anyone have a general answer to such problems?
Best Answer
This conjecture is true.
Proof :
For $n=5^ab$ where $0\le a\le 2$ and $\gcd(b,10)=1$, since $\gcd(99b,100)=1$, we see, by Euler's theorem, that there is a positive integer $k$ such that $100^k\equiv 1\pmod{99b}$. So, we get $$b\mid\underbrace{1010\cdots 10101}_{2k-1}=1+10^2+10^4+\cdots +10^{2k-2}=\dfrac{100^{k}-1}{99}$$ Now, let us consider $$25\times \underbrace{1010\cdots 10101}_{2k-1}=\underbrace{2525\cdots 2525}_{2k}$$ This is a multiple of $n=5^ab$.
For $n=2^a$, let us show by induction on $a$ that for every $a$, there is $N_a$ satisfying $2^a\mid N_a$ and $N_a=\overline{c_1c_2\cdots c_{\color{red}a}}$ with $c_i=2$ or $5$. We have $N_1=2$. Then, let us consider $10^aL+N_a=2^a(5^aL+m)$ where $L=2$ or $5$ with $N_a=2^am$. If $m$ is odd, then we can choose $L=5$. If $m$ is even, then we can choose $L=2$. Then, $10^aL+N_a$ is a multiple of $2^{a+1}$. (We have $N_2=52,N_3=552,N_4=5552,N_5=55552,N_6=255552,\cdots$.)
For $n=2^ab$ where $\gcd(b,10)=1$, since $\gcd((10^a-1)b, 10^a)=1$, we see, by Euler's theorem, that there is a positive integer $k$ such that $(10^a)^k\equiv 1\pmod{(10^a-1)b}$. So, we get $$b\mid \overbrace{1\underbrace{00\cdots 001}_{a}\underbrace{00\cdots 001}_{a}\cdots \underbrace{00\cdots 001}_{a}}^{(k-1)a+1}=1+10^a+10^{2a}+\cdots +10^{(k-1)a}=\dfrac{(10^a)^{k}-1}{10^a-1}$$ Now, let us consider $$N_a\times\overbrace{1\underbrace{00\cdots 001}_{a}\underbrace{00\cdots 001}_{a}\cdots \underbrace{00\cdots 001}_{a}}^{(k-1)a+1}=\overbrace{c_1c_2\cdots c_{a}c_1c_2\cdots c_{a}\cdots c_1c_2\cdots c_{a}}^{ka}$$ This is a multiple of $n=2^ab$.$\ \blacksquare$
We can prove that this conjecture is also true in the same way as above.