8
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Look at the quotient again. I think it's more like $12345679012\dots$ (note the missing $8$). $\endgroup$ Jan 14 '16 at 0:56
10
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Looks ok to me. I get the same answer by a completely different method. $\endgroup$ Jan 14 '16 at 2:05
6
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.