# Proving a number with $3^n$ equal digits is divisible by $3^n$

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.

-
do you mean all of its digits are equal or only $3^n$ of them? – dREaM 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

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

-
Could you please explain what do you mean by "Repeating $(1)$ $n$ times ..."? – VelvetThunder 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

-

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

-

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

-