What is the smallest multiple of $3^{1000}$, which has only 1’s in the digits?(Like 1, 11, 111 etc)

Question

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

Answer 1

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

Answer 2

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

Answer 3

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$

Answer 4

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.

Answer 5

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