Proving 111...111 is divisible by $3^n$

Question

Problem: Show that the number $11...11$ with $3^n$ digits is divisible by $3^n$.

My Attempt I tried solving this problem on base 3. It is easy to see that

$$3^n = 100....00$$ (upto $n$ 0's)

And $$ 11...11 = a_0 + 3a_1 + 3^2a_2 + .... 3^ma_m $$ if the the claim is correct then that would would imply that $11..11$ in base 3 would end with $3^n$ zeroes then that would mean that, $$ a_1=a_2=a_3...=a_k=0$$where k= $3^n$ I tried proving this but wasn't able to, subsequesntly I also tried to prove that a number is divisible by $3^n$ if it's sum is a multiple of $3^n$. Any insight on solving this?

(PS I do know this already has been posted on MSE but I wanted to see if I could prove this using my method)

Answer 1

Here is one possible way of doing it using some high school math competition technique: $$ 111....111 \quad \text{(with $3^n\ 1s)$} = \sum_{i=0}^{3^n-1} 10^i = \frac{1}{9} (10^{3^n} -1 ). $$

We count number of factor 3 in the numerator by lifting the exponent: https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma

$$ \nu_3(10^{3^n} -1) = \nu_3(10-1) + \nu_3(3^n) = n+2 $$

Canceling out the 9 in the denominator which contains two 3's, we get $$ \nu_3(111....111) = n $$

Answer 2

If $a$ is divisible by $3^k$ for fixed $k \ge 0$ and

$$ s \equiv 1 \pmod{3} \;\land\; t \equiv 1 \pmod{3} \;\land\; u \equiv 1 \pmod{3}$$

then by algebra

$$ 3^{k+1} \mid sa + ta + ua$$

Observe that $10^n \equiv 1 \pmod{3}$ for $n \ge 0$.

Using the above we'll make some non-abstract statements that the OP can formalize into a rigorous proof using induction:

$\; 3^1$ divides $111$
$\; 3^2$ divides $10^6 \cdot 111 + 10^3 \cdot 111 + 111$
$\; 3^2$ divides $111111111$