I have come up with a solution to the following question:
A number written in base 10 is a string of 3^2013 digit 3s. No other
digit appears. Find the highest power of 3 which divides this number.
However after looking up the answer it appears I have made a mistake somewhere that I cannot spot.
Here is my solution,
Let the number = $3+3*10 + 3*10^2+…+3*10^{2012}$. The 3 can then be factored out to get a geometric sum which then sums to $\frac{10^{2013}-1}{3}$.
The numerator can be expanded to give $(10-1)(10^{2012}-10^{2011}-…-10+1)$ hence the number simplifies to $3(10^{2012}-10^{2011}-…-10+1)$
Ignoring the 3 on the front for now and considering the expression (mod 3) it gives, $10^{2012}-10^{1011}-…-10+1 \cong 1 – 1 – 1-…-1+1 = 2 – 2011 = -2009$
2009 is not divisible by 3 and so this does not reduce to 0 (mod 3) hence the highest power of 3 that divides the expression is 3.
This is clearly incorrect as its easy to show the number is at least divisible by 9 using divisibility rules, however I'm not sure why. Thanks for any help.
Best Answer
The reason for being incorrect is already in comments, if you use the right expression $\dfrac{10^{3^{2013}}-1}3$ for your number you'll find it is divisible by $9$. In fact it is divisible by a higher power of $3$.
Let the number made of a string of $3^k$ threes be $S_k$. Then we can show the stronger claim that $S_k \equiv 3^{k+1} \mod {3^{k+2}}$, which is enough to conclude that the power you seek is $3^{2014}$.
The base case for an induction argument is easy with $k=0$ or $k=1$. For the induction step, note $S_{k+1} = S_k \cdot \left(10^{3^{k+1}}+10^{3^k}+1 \right)$
By the induction hypothesis, we have $S_k = a\cdot 3^{k+2}+3^{k+1}$, for some $a \in \mathbb N$. Further, obviously $10^{3^{k+1}}+10^{3^k}+1 \equiv 3 \pmod 9 $, hence $10^{3^{k+1}}+10^{3^k}+1 = 9b+3$ for some $b\in \mathbb N$.
Therefore we have the induction step $$S_{k+1} = S_k \cdot \left(10^{3^{k+1}}+10^{3^k}+1 \right) = \left(a\cdot 3^{k+2}+3^{k+1}\right)\cdot(9b+3) \equiv 3^{k+2} \pmod {3^{k+3}}$$