If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is? 
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?
 A: 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$.
A: 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
A: 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$.
A: 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$
