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} $ ?
 A: 
Let’s say ... $ 3^k | 111...111 $  ($3^k$  ones).  How can I prove [it for] $3^{k+1} $?

Note that $$\dfrac{10^{3^{k+1}}-1}9=\dfrac{10^{3^{k}}-1}9\times(10^{2\times3^k}+10^{3^k}+1).$$
On the right side, the first factor is divisible by $3^k$ and the second by $3$.
A: 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.
A: If $10^m=1+3^kr$ where $3\nmid r$
$(10^m)^n=(1+3^kr)^n$
$\equiv1+n3^kr\pmod{3^{k+1}}$ for $2k\ge k+1$
We need $3\mid n$ for $10^{mn}-1$ to be divisible by $3^{k+1}$
So if ord$_{3^k}10=m,$
ord$_{3^{k+1}}3=3m$
Now ord$_{3^2}10=1$
So, by induction 
ord$_{3^{m+2}}10=3^m$
Now in our case $m+2=1000+2$
A: If $m$ is coprime to $3$ then the g.c.d. of $10^m-1$ and $10^3-1$ is $10-1=9$. In particular, $9$ but not $27$ is  a factor of $10^m-1$.
If $n=3^km$ where  $m$ is coprime to $3$ then $$\frac {10^{3^km}-1}{10^{3^{k-1}m}-1}=1+10^{3^{k-1}m}+10^{3^{k-1}(2m)}\equiv3\pmod9$$
Repeating this process we obtain 
$10^{3^km}-1=\frac {10^{3^km}-1}{10^{3^{k-1}m}-1}\frac {10^{3^{k-1}m}-1}{10^{3^{k-2}m}-1}..\frac {10^{3m}-1}{10^{m}-1}(10^{m}-1)$
$$\equiv3^{k+2}\pmod {3^{k+3}}$$
Hence the least $n$ such that  $10^n-1$ is a multiple of $3^{1002}$ is obtained when $k=1000$ and $m=1$ i.e. $n=3^{1000}$.
A: A partial answer: as I note in my comment: by noting that 
$$
\overbrace{11 \cdots 1}^{n} = \frac{10^{n} - 1}{9},
$$
we can reframe your problem as that of finding the smallest $n$ such that $10^n$ is equal to $1$ modulo $3^{1002}$. We note that that $\varphi(3^{1002}) = 2 \cdot 3^{1001}$, where $\varphi$ denotes Euler's totient function.  Thus, we can guarantee that $n = 2 \cdot 3^{1001}$ will give us a string of $1$s that is divisible by $3^{1000}$, and that any smaller value of $n$ that works must divide $2 \cdot 3^{1001}$.
That being said, I see no easy way to check whether $n = 3^{1000}$ will work. Brute force computation confirms (W|A link) that it does, so that the string of $3^{1000}$ $1$'s is indeed divisible by $3^{1000}$.  This calculation (W|A link) confirms that the largest proper factor $n = 3^{999}$ does not work, which means that $3^{1000}$ is indeed the smallest possible value of $n$.
