Take the 2-minute tour ×
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.

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|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
add comment

3 Answers

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:

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

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.