<s>[INST] What is the smallest multiple of $3^{1000}$, which has only 1’s in the digits?(Like 1, 11, 111 etc) I think the answer is $3^{1000}$ ones,
and I want to prove it with induction. 
$3^0 | 1$ and $1$ is the smallest.
$ 3^1 | 111 $; it’s the smallest too. 
Let’s say it's true for $ 3^k | 111...111 $  ($3^k$  ones).   How can I prove to $3^{k+1} $ ?
 [/INST] Note that
$$
\underbrace{111\cdots11}_{3^{k}} = \underbrace{111\cdots11}_{3^{k-1}}\cdot(1+10^{3^{k-1}} + 10^{2\cdot 3^{k-1}})
$$
and $1+10^{3^{k-1}} + 10^{2\cdot 3^{k-1}}$ is divisible by $3$, so the left-hand side is indeed divisible by $3^{k}$ by induction.
But is it the smallest such number? For simplicity, let $a_n$ for $n\geq 0$ be the sequence defined by
$$
a_n = \underbrace{111\cdots11}_{3^n}
$$
and assume for induction that $a_{k-1}$ is the smallest number consisting only of $1$s that is divisible by $3^{k-1}$ (you have already checked that this is the case for $k = 0$ and $k = 1$, so the base cases are done). Let $x$ be the smallest number consisting only of $1$s that is divisible by $3^k$. We know $x$ exists, as $a_k$ is one such number.
By induction hypothesis, and the first paragraph, we have $a_{k-1}\leq x\leq a_k$. And $x$ can't be $a_{k-1}$ itself, as
$$
a_{k-1} = a_{k-2}(1 + 10^{3^{k-2}} + 10^{2\cdot 3^{k-2}})
$$
and $a_{k-2}$ is not divisible by $3^{k-1}$, and $1 + 10^{3^{k-2}} + 10^{2\cdot 3^{k-2}}$ is divisible by $3$ but not $9$. Thus $a_{k-1}$ is not divisible by $3^k$.
Therefore we have $a_{k-1}<x\leq a_k$. Now consider $$y = \frac{x - a_{k-1}}{10^{3^{k-1}}}$$ It is a strictly positive integer consisting only of $1$s which is divisible by $3^{k-1}$. So we have $a_{k-1}\leq y$. Can we have equality? If that were the case, then we would have
$$
x = a_{k-1}(1+10^{3^k})
$$
which isn't divisible by $3^k$. So we must have $a_{k-1}<y$. So we may repeat the process and consider $$z = \frac{y - a_{k-1}}{10^{3^{k-1}}}$$ Once again $z$ is a strictly positive integer consisting only of $1$s which is divisible by $3^{k-1}$. That means that $a_{k-1}\leq z$. Unnesting this final inequality gives us $a_k\leq x$, and we are done.
</s>