2
$\begingroup$

What is the remainder when the number

$101102103104105...996997998$

is divided by 990?

(The digits of the number are just the digits of all the integers from 101 to 998 inclusive, written side-by-side.)

I think I would have to use chinese remainder theorem and factor 990.

990= $2$$\cdot$$3^2$$\cdot$$5$$\cdot$$11$

Do I just create a system of 4 modular equations with different modulos as the factors listed above?

$\endgroup$
1
  • $\begingroup$ I wouldn't bother with $2$ and $5$, instead doing $10$, and doing that just by writing down the answer. $\endgroup$ – Angina Seng May 16 '17 at 6:23
4
$\begingroup$

First, note that $1000\cong 10\pmod{990}$. Then, $$1000^2\cong 100\pmod{990}$$ so $$1000^3\cong 1000\cong 10\pmod{990}$$ We can show by an easy induction that $1000^k\cong 10\pmod{990}$ if $k$ is odd, and $1000^k\cong 100\pmod{990}$ if $k$ is even (both for $k\geq 1$). Then, the number in question, which we can rewrite as $$\sum_{k=0}^{897} (998-k)1000^k = 998+\sum_{i=0}^{448} (997-2k)1000^{2i+1}+\sum_{j=0}^{447} (996-2k)1000^{2j+2}$$ is congruent to $$998+\sum_{i=0}^{448} 10(997-2k)+\sum_{j=0}^{447} 100(996-2k) \\ = 998+10(448+1)(997-448)+100(447+1)(996-447) \\ = 998+10\cdot 449\cdot 549+100\cdot 448\cdot 549$$ We can calculate the remaining modular division by hand to find that this is congruent to $548\pmod{990}$.

$\endgroup$
3
  • $\begingroup$ Note that dividing the number mod $11$ or mod $99$ is about as complex as dividing it mod $990$, since you are still left with sums that look like the ones above. Therefore, I believe that the Chinese remainder theorem does not make this problem simpler. $\endgroup$ – Michael L. May 16 '17 at 7:26
  • $\begingroup$ Can we use the CRT? If we let this number=x then we get three congruences. $x \equiv k mod 10$, $x \equiv k mod 9$, $x \equiv k mod 11$. We then solve for k $\endgroup$ – shrindle May 17 '17 at 4:23
  • $\begingroup$ Sure, but calculating $k$ divided by $11$ is by itself almost as complicated as calculating it divided by $990$ (in consideration of the fact that we will have a sum similar to the above). I don't see CRT as making this problem simpler. $\endgroup$ – Michael L. May 19 '17 at 13:36

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.