"$111 \dots$ upto $3^n$ digits" is divisible by $3^n$

Prove that an integer of the form "$111 \dots$ upto $3^n$ digits" is divisible by $3^n$

My attempt

For $n=1,$ $111$ is divisible by 3.

Let $T_n=111...$ upto $3^n$ digits is divisible by $3^n$. Then $T_{n+1}=111...$ upto $3^{n+1}$ digits. I am unable to prove that Then $T_{n+1}$ is divisible by $3^n$.

• Much more generally, if the base 10 digits of $m$ add up to $3^n$, then $m$ is divisible by $3^n$. e.g., the digits of 182736 add up to 27 and $182736 = 27 \times 6768$. Commented Apr 18, 2015 at 19:46
• @RobertSoupe That is only true for n=1 and n=2. e.g. 9972 is not divisible by 27. Commented Apr 20, 2015 at 5:27
• Oops, you're right, @DavidP. Good catch. Commented Apr 20, 2015 at 12:23

$n=1$ case: 111 is divisible by 3.

$n \Rightarrow n+1$ case: To demontrate that $T_{n+1}$ can be divided by $3^{n+1}$ I write $T_{n+1}$ as: $$T_{n+1} = T_n \cdot (10^{2 \cdot 3^n}+10^{3^n}+1)$$ $T_n$ is divisibile by $3^n$ by induction hypotesis, $10^{2 \cdot 3^n}+10^{3^n}+1$ is divisible by 3 because the sum of digits is 3.

So $T_{n+1}$ is divisible by $3^n \cdot 3 = 3^{n+1}$ which is what we wanted.

Why $T_n$ is that one? What we want to do is splitting $T_{n+1}$ to obtain an expression of $T_n$. We can do it by splitting the number in three groups of ones. So $\underbrace{111 \dots 111}_{3^n \text{ digits}} \underbrace{111 \dots 111}_{3^n \text{ digits}} \underbrace{111 \dots 111}_{3^n \text{ digits}} = \underbrace{111 \dots 111}_{3^n \text{ digits}} \underbrace{000 \dots 000}_{3^n \text{ digits}} \underbrace{000 \dots 000}_{3^n \text{ digits}} + \underbrace{111 \dots 111}_{3^n \text{ digits}} \underbrace{000 \dots 000}_{3^n \text{ digits}} + \underbrace{111 \dots 111}_{3^n \text{ digits}}$

Formally it's done by writing the expression $T_{n+1} = T_n \cdot (10^{2 \cdot 3^n}+10^{3^n}+1)$

For example we can observe that $$T_2 = 111\,111\,111 = 111 \cdot 10^6 + 111 \cdot 10^3 + 111 = 111 \cdot (10^6+10^3+1) = \\ =T_1 \cdot (10^6+10^3+1)$$

• Thank you for the answer. Would you kindly elaborate in details in respect of $$T_{n+1} = T_n \cdot (10^{6 n}+10^{3 n}+1)$$ Commented Apr 18, 2015 at 17:39
• Shouldn't that be $T_n(1+10^{3^n}+10^{2\cdot 3^n})$?
– zhw.
Commented Apr 18, 2015 at 17:53
• correct! i'll fix.
– Blex
Commented Apr 18, 2015 at 17:56
• @Blex $$T_2 =...=T_1 \cdot (10^6+10^3+1)$$ is understandable. $$T_{n+1} = T_n \cdot (10^{2 \cdot 3^n}+10^{3^n}+1)$$ is also coming from the same reason but can it (the generalization that $T_{n+1} = T_n \cdot (10^{2 \cdot 3^n}+10^{3^n}+1)$) be little more explainable so that beginners can catch it more easily. Thanks for your reply. Commented Apr 18, 2015 at 18:06
• fixed, i hope it's better now; if it's not enought understandable, i'll write simpler.
– Blex
Commented Apr 18, 2015 at 18:16

step 1. Write the number K = 111... in decimal form as 1100 + 1101 + 1*102 +... = $$\sum_{i=0}^m10^i$$

step 2. Examine K mod $$3^n$$ = $$\sum_{i=0}^m10^i$$ mod $$3^n$$ = $$\frac{1-10^{m+1}}{1-10}$$ mod $$3^n$$ = $$\frac{10^{m+1}-1}{9}$$ mod $$3^n$$ = $$\frac{10^{3^n} -1}{9}$$ mod $$3^n$$. Where the first equality follows from the formula for the sum of a finite geometric series. Clearly, 9|$$10^{3^n} -1$$ is necessary, so compute K' = $$10^{3^n} -1$$ mod (9*$$3^n$$)= $$10^{3^n} -1$$ mod $$3^{n+2}$$. If K' = 0, we're done.

step 3. $$\phi$$($$3^{n+2}$$) = $$3^{n+1}$$-$$3^n$$ = a

Thus, by Euler's formula, $$10^a$$ = 1 mod $$3^{n+2}$$. Therefore, K' + 1 = $$(10^a)^{3^n}$$= 1 mod $$3^{n+2}$$.

So, $$10^{3^n}$$ -1 mod $$3^{n+2}$$ = 0.

The End

We can apply the Lifting the Exponent lemma to $$10^{3^n}-1$$.

First we must check that it satisfies the conditions $$3|(10-1)$$ but $$3 \nmid 10$$ and $$3 \nmid 1$$. This means we have,

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

Because $$v_3$$ is completely additive we can simplify this down to,

$$v_3\left(\frac{10^{3^n}-1^{3^n}}{10-1}\right) = n$$

Which is exactly what we wanted to prove.

• Please don't duplicate prior answers (to FAQs). Commented Apr 19 at 14:27