# Show that $\underbrace{1\ldots1}_{81\text{ times}}$ is divisible by $81$ but not by $243$?

Question

How do I show that $$\underbrace{1\ldots1}_{81\text{ times}}$$ is divisible by $$81$$ but not by $$243$$?

My Attempt

Write $$\underbrace{1\ldots1}_{81\text{ times}}=\underbrace{111,111,111}_{9\text{ times}}$$ and note that $$111,111,111=9 \times 12,345,679$$. This also shows that $$9 \mid 111,111,111$$.

Now, the sum of digits of $$\underbrace{12,345,679}_{9\text{ times}}$$ is $$37 \times 9$$ which is clearly divisible by $$9$$, thereby showing that $$9 \mid 12,345,679$$.

This in turn shows that $$81 \mid \underbrace{111,111,111}_{9\text{ times}}$$

Next, note that $$111,111,111=243 \times 457247.37\overline{037}=243 \times \left(457247+\frac{370}{999}\right)$$

As a result, we have $$\underbrace{111,111,111}_{9\text{ times}}=243 \times \left(457247+\frac{370}{999}\right) \times \left(1+10^{9}+\cdots+10^{72}\right)$$

To show that $$243 \nmid \underbrace{111,111,111}_{9\text{ times}}$$ we need only show that $$999 \nmid (1+10^9+\cdots+10^{72})$$.

Indeed, as $$10^3 \equiv 1 \pmod {999}$$, so $$10^9=(10^3)^3 \equiv 1^3 \equiv 1 \pmod {999}$$ and in general $$10^{9a} \equiv 1 \pmod {999}$$ for $$a \in \mathbb{N}$$. Since $$(1+10^9+\cdots+10^{72}) \equiv \underbrace{1+\cdots+1}_{9\text{ times}} =9 \pmod {999}$$ so $$999 \nmid (1+10^9+\cdots+10^{72})$$ and we get the desired result.

Doubt

Is the above solution correct? If it is correct, is there a shorter and more elegant solution?

• Yes, your solution is correct. Also, see whether the approach given here helps you.
– user371838
Sep 14, 2019 at 13:41

The problem is equivalent to show that $$10^{81}-1$$ is divisible by $$3^6$$ but not by $$3^7$$. This follows from the fact that, for $$x=10$$, \begin{align} x^{81}-1&=(x^{27}-1)(1+x^{27}+x^{54})\\ &=(x^{9}-1)(1+x^9+x^{18})(1+x^{27}+x^{54})\\ &=(x^{3}-1)(1+x^3+x^6)(1+x^9+x^{18})(1+x^{27}+x^{54})\\ &=\underbrace{(x-1)}_{=3^2}\underbrace{(1+x+x^2)}_{3k_1}\underbrace{(1+x^3+x^6)}_{3k_2}\underbrace{(1+x^9+x^{18})}_{3k_3}\underbrace{(1+x^{27}+x^{54})}_{3k_4} \end{align} where $$k_1,k_2,k_3,k_3$$ are coprime with $$3$$.

• For the "coprime" step you can instead use the remainder theorem. If $p(x)=q(x)(x-1)+r$ we have that $p(1)=r$ and this gives for the ones you need that the remainder on dividing by $x-1=9$ is $3$ Sep 14, 2019 at 13:56
• Very neat solution indeed. Sep 14, 2019 at 13:57
• @Dragonemperor42 Thanks. As already remarked, your proof is correct! Sep 14, 2019 at 15:02

Let us study $$\nu_3(10^n-1)$$. Since $$10^n-1 = 3^2(10^{n-1}+\ldots+1)$$ and $$10^{n-1}+\ldots+1\equiv n\pmod{3}$$, $$3\nmid n\rightarrow \nu_3(10^n-1)=2.$$ Let us assume $$n=3m$$ now: $$10^{3m}-1 = (10^m-1)(10^{2m}+10^{m}+1)$$ with $$10^{2m}+10^{m}+1\equiv 3\pmod{9}$$, so $$3\mid n \rightarrow \nu_3(10^{n}-1) = 1+ \nu_3(10^{n/3}-1)$$ and by induction $$\boxed{\nu_3(10^n-1) = 2+\nu_3(n)}.$$ If we consider $$n=81$$ we have $$\nu_3(n)=4$$, hence the largest power of $$3$$ dividing $$10^{81}-1$$ is $$3^6$$ and the largest power of $$3$$ dividing the $$81$$th repunit is $$3^4=81$$.

• I am not sure how you did the induction? Sep 14, 2019 at 14:13
• @Dragonemperor42: on the maximum power of $3$ dividing $n$. If this power is $3^k$, in order to compute $\nu_3(10^n-1)$ we apply $k$ times the "rule" $\nu_3(10^n-1)=1+\nu_3(10^{n/3}-1)$, then we finish through the first rule. Sep 14, 2019 at 14:21
• I see. You implicitly use the fact that $n=3^k m$ where $m \nmid 3$, thereby $k$ is the maximum power of $3$ dividing $n$ by construction. Sep 14, 2019 at 14:26

An alternative solution is using binomial theorem. Notice \begin{align} X \stackrel{def}{=}\underbrace{1\ldots 1}_{81} &= \frac{10^{81}-1}{10-1} = \frac{(1+9)^{81} - 1}{9}\\ &= \binom{81}{1} + \binom{81}{2}9 + \binom{81}{3}9^2 + 9^3 (\cdots)\end{align} where $$(\cdots)$$ is some integer we don't care. Since $$243 = 3^5 | 9^3$$, we get \begin{align} X & \equiv 81 + \frac{81\cdot 80}{2} 9 + \frac{81\cdot 80\cdot 79}{6} 9^2 \pmod {3^5}\\ & \equiv 3^4 + 40(3^6) + (40)(79) 3^7 \pmod {3^5}\\ & \equiv 3^4 \pmod {3^5}\end{align} When we divide $$X$$ by $$243$$, the remainder is $$81 = 3^4$$. This implies $$X$$ divides $$81$$ but not $$243$$.