Is it divisible by $3^n$?

Question

I need to prove that a number made up exactly $3^n$ $1$s and nothing else is a multiple of $3^n$.

Well I think it is true that any number is a multiple of $3^n$ if the sum of its digits is. But I would have to give a formal proof to that statement before I use it. It is rather simple to prove this idea for $n=1$, but for any $n$...

Do you think that would be the best approach, or can you think of a better one?

Answer 1

You can use induction for a formal proof of the statement.

Claim: $$3^n \mid \underbrace{111\ldots111}_{3^n\textrm{ times }}$$

Base case: For $n=1$, this is true since $111=3\times 37$ is divisible by $3$

Inductive Hypothesis: Suppose that, for $n=k$, we have $3^k\mid \underbrace{111\ldots 111}_{3^k \textrm{ times}}$, so we can write $\underbrace{111\ldots 111}_{3^k\textrm{ times}}=3^k\times p$ for some integer $p$.

Inductive step:

$$\underbrace{111\ldots 111}_{3^{k+1}\textrm{ times}}=\sum_{i=0}^2 10^{i\cdot 3^k}\cdot \underbrace{111\ldots 111}_{3^k\textrm{ times}}=3^kp\sum_{i=0}^2 10^{i\cdot 3^k}$$

Note that every power of $10$ leaves a remainder of $1$ when divided by $3$, so sum of any three powers of $10$ will be divisible by $3$ since the remainders of the addends add up to $3$, hence $\sum\limits_{i=0}^2 10^{i\cdot 3^k}$ is divisible by $3$ (say it's equal to $3q$ for some integer $q$). Then, we have,

$$\underbrace{111\ldots 111}_{3^{k+1}\textrm{ times}}=3^kp\times 3q=3^{k+1}pq$$

... which is divisible by $3^{k+1}$.

Hence, the statement is true for all $n\geq 1$ by induction.

---

Answer 2

Well I think it is true that any number is a multiple of $3^n$ if the sum of its digits is.

This is false in general, if $n>2$. For instance, for $n=3$: $$9981=9\times 1109$$ and $1109$ is prime (certainly not a multiple of $3$).

Back to the problem:

The way I see it:

\begin{align}\underbrace{111\cdots1}_{3^n\text{ times}}&=111\cdot(\underbrace{[00]1\ 001\ 001\cdots001}_{3^{n-1}\text{ times}})\\&=111\cdot1001001\cdot(\underbrace{[000000]1\ 0000001\ 0000001\cdots0000001}_{3^{n-2}\text{ times}})\\&=111\cdot1001001\cdot100000010000001\cdot(\cdots)\end{align}

At each step I'm taking out a divisor with exactly three "$1$"-s, which is therefore an exact multiple of $3$.