3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Soupe Apr 18 '15 at 19:46
  • $\begingroup$ @RobertSoupe That is only true for n=1 and n=2. e.g. 9972 is not divisible by 27. $\endgroup$ – David P Apr 20 '15 at 5:27
  • $\begingroup$ Oops, you're right, @DavidP. Good catch. $\endgroup$ – Robert Soupe Apr 20 '15 at 12:23
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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) $$ $\endgroup$ – user1942348 Apr 18 '15 at 17:39
  • 1
    $\begingroup$ Shouldn't that be $T_n(1+10^{3^n}+10^{2\cdot 3^n})$? $\endgroup$ – zhw. Apr 18 '15 at 17:53
  • $\begingroup$ correct! i'll fix. $\endgroup$ – Blex Apr 18 '15 at 17:56
  • $\begingroup$ @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. $\endgroup$ – user1942348 Apr 18 '15 at 18:06
  • $\begingroup$ fixed, i hope it's better now; if it's not enought understandable, i'll write simpler. $\endgroup$ – Blex Apr 18 '15 at 18:16
2
$\begingroup$

step 1. Write the number K = 111... in decimal form as 1*100 + 1*101 + 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} -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} -1$ is necessary, so compute K' = $10^{3^n+1} -1$ mod (9*$3^n$)= $10^{3^n+1} -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}$ -1 mod $3^{n+2}$ = 0.

The End

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.