# Prove that a number that consists of $3^n$ ones is divisible by $3^n$

I can't even make sense of this question. Isn't this just like asking, "Prove that 3 is divisible by 3." Isn't any number divisible by itself? Is this all there is to this question—it seems like there must be more to it.

• If $n = 1$, then the number that consists of $3^n$ ones is $111 = 3 \times 37$. – user153918 Feb 26 '15 at 16:49
• "Consists of" is unclear. They intend "whose decimal representation consists of". – André Nicolas Feb 26 '15 at 16:51
• The problem is to show that $3^n \mid {10^{3^n}-1 \over 9}$. – copper.hat Feb 26 '15 at 16:53
• It's congruence arithmetic. – MadScientist Feb 26 '15 at 17:06

We can use induction. I prefer to show that the number that "consists of" $3^n$ $9$'s is divisible by $9\cdot 3^n$.

The number whose decimal representation consists of $3^n$ consecutive $9$'s is $10^{3^n}-1$.

For the induction step, note that $10^{3^{k+1}}-1=x^3-1$ where $x=10^{3^k}$. This factors as $(x-1)(x^2+x+1)$. By the induction assumption, $x-1$ is divisible by $9\cdot 3^k$. Also, $3$ divides $x^2+x+1$, so $9\cdot 3^{k+1}$ divides $x^3-1$.

Remark: Or else we could show that the number whose decimal representation consists of $3^{k+1}$ consecutive $1$'s is the number with $3^k$ consecutive $1$'s, times a number of the shape $1000\cdots 01000\cdots 01$. The second number is divisible by $3$ by the usual divisibility test.

What is meant is show that $111$ (so onehundred eleven) is divisible by $3^1$, and $111111111$ (the number with $3^2= 9$ times the digit $1$) is divisible by $3^2 = 9$ and so on.

The number is written using $3^n$ times the digit $1$.

Not, as you assume, $1+1+1$ and so on. This would indeed be obvious.

• I see, thanks for the correct interpretation. – Sargon Feb 26 '15 at 16:53

Generalization :

If modulo order ord$_{p^k}a=d\implies a^d\equiv1\pmod{p^k},a^d=1+p^k\cdot c$ for some integer $c$ and $p$ is any integer

$\implies a^{pd}=(a^d)^p=(1+p^k\cdot c)^p\equiv1\pmod{p^{k+1}}$

Here $a=10,p=3,k=2,d=1$

So by mathematical induction, $10^n\equiv1\pmod{3^{n+1}}$ for integer $n\ge1$