Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

I would appreciate your help.

share|cite|improve this question
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
up vote 4 down vote accepted

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:


share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.