4
$\begingroup$

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.

  • 0
    @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.2012-07-20

4 Answers 4

3

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

  • 0
    @Rob You may find of interest the telescopic view of the above in my answer.2012-07-23
1

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

0

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

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