# How does one prove that the number $111\ldots 1$ (formed by $3^{n}$ digits all equal to $1$) is divisible by $3^{n}?$

I am self-studying Discrete Mathematics (in Portuguese), and there is one exercise I was not able to solve.

Show that the number $111\ldots 1$ (formed by $3^{n}$ digits are equal to $1$) is divisible by $3^{n}.$

All I was able to do was to show the base case, but I do not know how to use the inductive step.

-
What is the value of $n$? – Martin Argerami Mar 23 '12 at 17:52
$n$ is natural! Meu colega! – checkmath Mar 23 '12 at 17:55
@RossMillikan: You are right! Sorry, I am ADHD. I mean it! – spohreis Mar 23 '12 at 18:15
@spohreis: No worries. – Ross Millikan Mar 23 '12 at 18:18

I’m sure that you meant to say that the number was formed by $3^n$ digits equal to $1$, not $3^3$ digits.

Let $m_n$ be the number whose decimal representation is a string of $3^n$ $1$’s. To be explicit, $m_n=\frac19(10^{3^n}-1)$. Suppose that $3^n$ divides $m_n$ for some $n$, say $m_n=3^nk$. Then \begin{align*} m_{n+1}&=10^{3^n}\left(10^{3^n}m_n+m_n\right)+m_n\tag{1}\\ &=\left(10^{2\cdot3^n}+10^{3^n}+1\right)m_n\\ &=\left(10^{2\cdot3^n}+10^{3^n}+1\right)3^nk\;, \end{align*}

and we need only show that $3$ divides $10^{2\cdot3^n}+10^{3^n}+1$. But $10\equiv 1\pmod 3$, so every power of $10$ is congruent to $1$ mod $3$, and therefore $10^{2\cdot3^n}+10^{3^n}+1$ is indeed a multiple of $3$.

If the step $(1)$ is a little puzzling at first, look at an example:

$$m_2=111111111=111000000+111000+111=1000(1000m_1+m_1)+m_1\;.$$

-

I think you meant

For $n\geq 1$ Show that the number $111 \cdots 1$ (formed by $3^n$ 1's) is divisible by $3^n$.

Base case is clear.Denote let $A_m:= \underbrace{111 \cdots 1}_{3^m}$. Suppose the result is true for integers $n=k$, then $$A_{k+1}= \frac{10^{3^{k+1}}-1}{9}=\frac{(10^{3^k})^3-1}{9}=\frac{10^{3^k}-1}{9}(10^{2\cdot3^n}+10^{3^n}+1)=A_k\times S$$

where $S=10^{2\cdot3^n}+10^{3^n}+1$, since $S$ is a multiple of $3$ the conclusion follows.

-

Hint $\$ By below, $\rm\:\ 3^k\: |\: f_n\ \Rightarrow\ 3^{k+1}\: |\: f_{n+1}.\:$ Yours is the special case $\rm\:c = 3.$ $$\rm\displaystyle\ f_n = \frac{(3c\!+\!1)^{3^n}\!-1}{3c}\ \ \Rightarrow\ \ f_{n+1} = \frac{(3c\:\!f_n\! +\! 1)^3-1}{3c}\: =\: \frac{9c\:f_n\:\!m}{3c}\: =\: 3\:f_n m$$

-