If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is?

Question

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is?

$729=9^3$

For any number to be divisible by $9$, the sum of the digits have to be divisible by $9$. The given number is divisible by $9$.

Then I tried dividing the given number by $9$. The quotient was like $123456789012\cdots$

So the quotients sum is $(45\times 8)+1=361$

Is this the way to proceed? Is there a shorter way?

Answer 1

We are looking for

$ x = 10^{80} + 10^{79} + \dots + 10^2 + 10 + 1 \mod{9^3}$

$ 10^k = (9 + 1)^k = \sum\limits_{i=0}^{k}{k \choose i}9^i $ (Binomial theorem)

Considering the second equality $\mod{9^3} $, we only need first three summands of the sum. So $ 10^k \equiv 1 + k\cdot 9 + \frac{k\cdot(k-1)}{2}\cdot 9^2\mod{9^3}$. So what we're looking for is

$$ x\mod{9^3} \equiv\sum\limits_{k=0}^{80}1 + 9k + 81\frac{k\cdot(k-1)}{2} \mod{9^3} = \sum\limits_{k = 0}^{80}1 - \frac{63}{2}k + \frac{81}{2}k^2$$

Using formulas $ \sum_{k=0}^n k = \frac{n(n+1)}{2}, \sum\limits_{k=0}^n k^2 = \frac{n(n+1)(2n+1)}{6} $ we get that

$$ x \mod{9^3} = 81 + \frac{-63}{2}\cdot80\cdot81\cdot\frac{1}{2} + \frac{81}{2}\cdot80\cdot81\cdot161\cdot\frac{1}{6} \mod{9^3}$$

$$ x \mod{9^3} = 81 + 81((-63)\cdot20 + 20\cdot27\cdot161) \mod{9^3}$$

Notice the term in brackets is divisible by $ 9 $, hence the answer is $ 81 $.

I'm not sure that's the best way to approach this. Please correct me if any of the calculations were wrong

Answer 2

According to Wolfy, or by repeated use of $x^3-1 =(x-1)(x^2+x+1) $, $\frac{x^{81}-1}{x-1} = (x^2+x+1) (x^6+x^3+1) (x^{18}+x^9+1) (x^{54}+x^{27}+1) $.

Since $x^{3n} \equiv 1 \bmod (x^3-1)$, $x^{6n}+x^{3n}+1 \equiv 3 \bmod (x^3-1) $.

Therefore the right 3 factors are all $\equiv 3 \bmod (x^3-1) $.

Therefore the whole product $\equiv 27(x^2+x+1) \bmod (x^3-1) $.

Since

$\begin{array}\\ x^2+x+1 &=((x-1)+1)^2+(x-1)+2\\ &=(x-1)^2+2(x-1)+1+(x-1)+2\\ &=(x-1)^2+3(x-1)+3\\ \end{array} $

we have

$\begin{array}\\ 27(x^2+x+1) &=27((x-1)^2+3(x-1)+3)\\ &=27(x-1)^2+81(x-1)+81\\ &\equiv 81 \bmod 729 \qquad\text{setting }x=10 \text{ since }27\cdot 9^2, 81\cdot 9 \equiv 0 \bmod 729\\ \end{array} $

Therefore the answer is $81$.

Answer 3

We want to compute $\frac{10^{81}-1}{9} \mod 9^3$. We can't divide by 9 but we can compute $10^{81}-1 \mod 9^4$ and then divide the result by 9. We can compute this with a simple calculator: $$ 10^{81}-1 = (10^9)^9-1 = 5185^9-1 = 5185 (5185^2)^4-1 = \cdots = 729 $$ The result is thus $729/9 = 81$.

Answer 4

Put $$a=10^9=729\cdot1371742+82\equiv 1+9^2\ (mod\space 9^3)$$ $$N=111111111=729\cdot 152415+576\equiv 576 \ (mod\space 9^3)$$ Let $M$ be the number so $$M=N(a^8+a^7+a^6+a^5+a^4+a^3+a^2+a+1)$$ Furthermore $$a\equiv 1+9^2\ (mod\space 9^3)$$ $$a^2\equiv 1+2\cdot9^2\ (mod\space 9^3)$$ $$a^3\equiv 1+3\cdot9^2\ (mod\space 9^3)$$ $$......$$ $$a^8\equiv 1+8\cdot9^2\ (mod\space 9^3)$$ It follows $$M\equiv N(9+9^2\cdot 9\cdot 4)\equiv 576\cdot 9\equiv \color{red} {81}\ (mod\space 9^3)$$ because $576\cdot 9=5184=7\cdot 729+81$