Find the remainder when $528528528...$up to $528$ digits is divided by $27$?
Here's what I have done: The number can be written as $528\cdot 10^{525}+528\cdot 10^{522}+...+528$ which has $176$ terms and each term is $\equiv15 \mod 27$ thus the number should be $176*15 \mod 27$ hence $21$ should be the remainder. But book says it is $6$. I don't understand the flaw in my logic. Please correct me.
-
$\begingroup$ you have $21+6=27$ perhaps you are off by a sign? $\endgroup$ – gt6989b Oct 16 '17 at 15:26
-
3$\begingroup$ I think that your answer is correct. $\endgroup$ – alexp9 Oct 16 '17 at 15:29
-
$\begingroup$ Brute force in python gives 21. $\endgroup$ – Gribouillis Oct 16 '17 at 15:31
-
1$\begingroup$ Are you sure the book says $6$ and not $-6$? After all, $21\equiv -6 \pmod{27},$ so then both answers would agree. $\endgroup$ – David K Oct 16 '17 at 15:36
-
1$\begingroup$ @fleablood Also a good point about negative remainders. It looks like there's probably an error in the book. (Unless the transcription of the problem is very confused, it's only $176$ "copies" of the group of digits $528,$ which makes $528$ digits altogether since each group has three digits. Also, we don't need $10^k$ to be congruent to $1$; we only need $10^{3k}\equiv 1 \pmod{27},$ which is true.) $\endgroup$ – David K Oct 16 '17 at 17:00
Here is a python3 session
>>> s = '528' * 176
>>> len(s)
528
>>> int(s) % 27
21
-
$\begingroup$ Is it possible to multiply a string by a number? My god...python is awesome. $\endgroup$ – Integral Oct 16 '17 at 15:35
-
2$\begingroup$ @Integral yes strings, lists and tuples can be repeated by multiplying them by a number. $\endgroup$ – Gribouillis Oct 16 '17 at 15:36
You can see that $6$ cannot be correct by casting out $9$'s: Since $5+2+8=5+5+5$, we have
$$528528\ldots528\equiv5+5+5+\cdots+5+5+5=5\cdot528\equiv5(5+2+8)\equiv5\cdot6\equiv3\mod 9$$
so the remainder mod $27$ must be either $3$, $12$, or $21$. Your approach gave the correct answer, $21$.
-
$\begingroup$ Anyway it is also $-6$ so there is a typo in the book or Anuran has not have seen the minus sign. $\endgroup$ – Piquito Oct 16 '17 at 15:54
-
$\begingroup$ @Piquito, I agree, a negative sign would fix things (as David K noted in comments). But remainders are usually understood to be nonnegative, so I'm inclined to think it's a typo. $\endgroup$ – Barry Cipra Oct 16 '17 at 15:57
Since $3\mid111$, we know that $27\mid999$, Therefore, $$ 1000\equiv1\pmod{27} $$ Thus, $$ \begin{align} \sum_{k=0}^{175}528\cdot1000^k &\equiv528\cdot176\pmod{27}\\ &\equiv3\cdot176^2\pmod{27}\\ &\equiv3\cdot14^2\pmod{27}\\ &\equiv3\cdot7\pmod{27}\\ &\equiv21\pmod{27} \end{align} $$
You are incorrect in assuming $10^{k} \equiv 1 \mod 27$. As $10^k \not \equiv 1$ we do not have $528*10^k \equiv 15 \mod 27$.
What you need instead is $528528... = 528(1001001001......)$
And $1001001..... =\sum_{k=0}^{175} 10^{3k}$
$10^3 \equiv 1 \mod 27$... Oh... we do have that and you were not wronng after all.... so $\sum 10^{3k}\equiv 176 \equiv 14 \mod 27$.
So $528528....... \equiv 15*14 \equiv 21 \mod 27$.
And... the book is wrong.
Had it been 527 iterations of 528 the answer would be $6$.
Note that $27 \times 37 = 999$.
To find the remainder you get when you divide $528528\cdots 528$ by $999$, you can "cast out" $999$s.
$\underbrace{528 + 528 + \cdots 528}_{\text{$176$ times} } \to 176 \times 528 \to 92928 \to 92+928 \to 1020 \to 21$
So the remainder is $21$.
Note. If the remainder was bigger than 26, you would have had to divide it by 27 to get the correct remainder.