Identical Digits Property?

Number Theory Level 1

True or false :

Let $Q$ be a positive integer with all $3^n$ identical digits, that is $Q = \underbrace{aaaaaaa\ldots a}_{3^n \text{ digits}}$ . Then, $3^n$ divides $Q$ for positive integers $n$ .

True False

2 solutions

Alejandro Castillo
May 30, 2016

Given that $Q=\underbrace { aaa...a }_{ { 3 }^{ n } }$ we can write that $Q=a\times { 10 }^{ { 3 }^{ n } }+a\times { 10 }^{ { 3 }^{ n }-1 }+...+a\times { 10 }^{ 0 }=a\sum _{ J=1 }^{ { 3 }^{ n } }{ { 10 }^{ J } } =a\left[ \frac { { 10 }^{ { 3 }^{ n } }-1 }{ 10-1 } \right] =a\left[ \frac { \overbrace { 999...9 }^{ { 3 }^{ n } } }{ 9 } \right] =a\left[ \overbrace { 111...1 }^{ { 3 }^{ n } } \right]$ . The criterion of divisibility of 3 says that the: "if sum of the digits of a number is 3 or multiply of 3, this number is divisible by 3". Then, for induction we can proof that the number $\overbrace { 111...1 }^{ { 3 }^{ n } }$ is ever divisible by $3^{n}$ Therefore $3^n$ divides to $Q$ for all $n$ integer positive

Moderator note:

As pointed out in the comments, this solution hasn't provided the induction prove that " $\overbrace { 111...1 }^{ { 3 }^{ n } }$ is divisible by $3^n$ , which is the crux of the problem.

This gap is easily filled by observing that $\overbrace { 111...1 }^{ { 3 }^{ n } } = \overbrace { 111...1 }^{ { 3 }^{ n -1 } } \times 1 0 \ldots 0 1 0 \ldots 1$ where the first term is a multiple of $3^{n-1}$ and the second term is a multiple of 3.

In fact, we can show that $3^n$ is the highest power of 3 that divides $\overbrace { 111...1 }^{ { 3 }^{ n } }$ form the above observation.

Do note that even though the statement "if sum of the digits of a number is 3 or multiple of 3, this number is divisible by 3" is true, it doesn't follow by induction that "if sum of the digits of a number is $3^n$ or a multiple of $3^n$ , this number is divisible by $3^n$ ". This is true only for $n=1,2$ . A simple counterexample for $n=3$ is $9981$ and for $n\geq 3$ , we can construct the counterexample $2727\ldots2745$ where $27$ is repeated as many times so that the sum of digits is $3^n$ . This number is not divisible by $27=3^3$ and hence not divisible by $3^n~\forall~n\geq 3$ .

However, the statement $3^n\mid \underbrace{111\ldots 11}_{3^n\textrm{ times}}$ is true $\forall~n\geq 1$ and can be proved by induction. Here 's a nice inductive proof of this statement.

Prasun Biswas - 5 years ago

Sam Bealing
Jun 13, 2016

$Q=\left (\dfrac{a}{9} \right) \left (10^{(3^n)}-1 \right) \\ 3^n \vert Q \implies 3^n \vert \left (\dfrac{a}{9} \right) \left (10^{(3^n)}-1 \right) \implies 3^{n+2} \vert a \left (10^{(3^n)}-1 \right)$

So the problem is equivalent to proving $3^{n+2} \vert \left (10^{(3^n)}-1 \right)$ . This can be done by induction.

It is easy to test the statement is true for $n=1$ . Assume the statement is true for $n=k$ so $3^{k+2} \vert \left (10^{(3^k)}-1 \right)$ :

$10^{(3^{k+1})}-1=10^{3(3^k)}-1=\left (10^{(3^k)} \right )^3-1=\left (10^{(3^k)}-1 \right) \left (\left (10^{(3^k)} \right )^2+10^{(3^k)}+1 \right) \\ \left (\left (10^{(3^k)} \right )^2+10^{(3^k)}+1 \right) \equiv \left (\left (1^{(3^k)} \right )^2+1^{(3^k)}+1 \right) \equiv 1+1+1 \equiv 0 \pmod{3}$

Combining this and the inductive hypothesis gives:

$3 \left (3^{k+2} \right) \vert 10^{(3^{k+1})}-1 \implies 3^{(k+1)+2} \vert 10^{(3^{k+1})}-1$

So it is proved by induction that $3^{n+2} \vert \left (10^{(3^n)}-1 \right)$ for all positive $n$ making the statement:

$\color{#20A900}{\boxed{\boxed{\text{True}}}}$

Moderator note:

Great approach, using the hints in the question statement to guide the solution.

Identical Digits Property?

2 solutions

Moderator note:

Moderator note:

0 pending reports