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.

Prove a number with $3^n$ equal digits is divisible by $3^n$.

My thoughts about the problem are: a number with $3^n$ equal digits $d$ is equal to $d\frac {10^{3^n} - 1} {9}$. We use Lifting The Exponent lemma, or plain induction.

share|improve this question
4  
do you mean all of its digits are equal or only $3^n$ of them? –  Jorge Fernández Jul 20 '12 at 0:40
    
@ChuckFernández: Since it is mentioned that "a number with $3^n$ equal digits $d$ is equal to $d\frac{10^{3^n}-1}{9}$", I assume all of its digits are equal. –  robjohn Jul 20 '12 at 8:03

4 Answers 4

up vote 3 down vote accepted

This follows from the fact that $x^3-1=(x-1)(x^2+x+1)$ and that $10\equiv1\pmod{3}$. That is, $$ 10^{3^n}-1=\left(10^{3^{n-1}}-1\right)\left(10^{2\cdot3^{n-1}}+10^{3^{n-1}}+1\right)\tag{1} $$ and $$ \begin{align} \left(10^{2\cdot3^{n-1}}+10^{3^{n-1}}+1\right) &\equiv1+1+1\\ &\equiv0\pmod{3}\tag{2} \end{align} $$ so that $$ \left.3\,\middle|\,\left(10^{2\cdot3^{n-1}}+10^{3^{n-1}}+1\right)\right.\tag{3} $$ We start out with $$ \left.3^2\,\middle|\,\left(10^{3^0}-1\right)\right.\tag{4} $$

Next, combining $(1)$ and $(3)$ yields that $$ \left.3^{n+1}\,\middle|\,\left(10^{3^{n-1}}-1\right)\right.\Rightarrow\left.3^{n+2}\,\middle|\,\left(10^{3^n}-1\right)\right.\tag{5} $$

Therefore, induction on $n$, using $(4)$ and $(5)$, says $$ \left.3^n\,\middle|\,\frac{10^{3^n}-1}{9}\right.\tag{6} $$

share|improve this answer
    
Could you please explain what do you mean by "Repeating $(1)$ $n$ times ..."? –  Quixotic Jul 20 '12 at 0:55
    
@Quixotic: I have expanded the explanation. Hopefully, this is clearer. –  robjohn Jul 20 '12 at 1:12
    
would the downvoter care to comment? –  robjohn Jul 20 '12 at 7:20
    
@Rob You may find of interest the telescopic view of the above in my answer. –  Bill Dubuque Jul 23 '12 at 4:52

Lifting Exponents Lemma says that if $p$ is prime, $\nu_p(a-b)=r>0$, $\nu_p(m)=s$, and $p \not | a,b$, then $\nu_p(a^m-b^m)=r+s$.

Using this, it is direct from what you have. The hint I can give you is to write $1=1^{3^n}$.

Cheers,

Rofler

share|improve this answer

$10^{3^n}-1$

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

=$-1+ 1+(3^nC_1)(3^2)+(3^nC_2)(3^2)+\cdot\cdot\cdot+(3^2)^{3^n}$

which will be divisible by $3^{n+2}$ if n+4≥n+2 , (n-1+6)≥n+2, $\cdot\cdot\cdot\ , 2.3^n≥n+2$ which is true for n≥0.

So, $\frac{10^{3^n}-1}{9}$ will be divisible by $3^n$ for n≥0.

share|improve this answer

Note $\rm\,\ 3\,f_n\:|\:f_{n+1}\Rightarrow\: 3^n\:|\:f_n/f_0\ $ by induction (or, clearer, by multiplicative telescopy).

Thus $\rm\ f_n = 10^{3^n}\!-1\:\Rightarrow\: 3\,f_n\:|\:f_{n+1}\! = (f_n\!+\!1)^3\!-\!1 = f_n\,(f_n^2 + 3\,f_n+3)\ $ by $\rm\:3\:|\:f_n^2 + 3\,f_n+3,\:$ by $\rm\:3\:|\:f_n$

Hence $\rm\displaystyle\ 3^n\:|\:f_n/f_0\ =\ \frac{10^{3^n}-1}{9}\ =\ 111\cdots 111\,\ (3^n digits)$

share|improve this answer

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.