Using Chinese Remainder Theorem to find the remainder when divided by 990.

Question

I'm still revising for my final (this class is absolutely killing me) and I need some help on the following problem:

What is the remainder when the number $101102103104105...996997998$ is divided by $990$?

The question says that CRT must be used. I actually found an alternative answer to this question on this site (link: Remainder when dividing by 990: Chinese Remainder Theorem) and understand the policy on duplicates, but I wish to know how we can use CRT on such a large number.

If we were to set $x = 101102103104105...996997998$, then based on the factors of $990$, we would get $x = k\pmod{10}$, $x = k\pmod{11}$ and $x = k \pmod9$. But how can I apply the CRT on such a large number?

Thanks! And sorry about the very similar question.

Answer 1

The number $x$ is indeed large but we can simplify its computation $\!\bmod 9\ \&\ 11\,$ using $\,10^{\large 3}\equiv \pm1\,$ and this makes the arithmetic so simple that it can all be done purely mentally, i.e.

$\!\!\bmod 11\!:\ 10^{\large 3}\equiv -1\,\Rightarrow\, x\equiv (998\!-\!997) + (996\!-\!995)+\cdots + (102\!-\!101)\equiv \overbrace{449\cdot 1\equiv 9}^{\large \equiv\ 4\ -\ 4\ +\ 9}$

$\!\!\bmod 9\!:\ \ \ 10^{\large 3}\equiv 1\,\Rightarrow x\equiv \begin{align} &\ \ \ \ \ 998+997+\cdots+\color{#0a0}{550}\\ &+101+102+\cdots+\color{#0a0}{549}\end{align}\equiv 449(\color{#0a0}{1099})\equiv (4\!+\!4\!+\!9)(1\!+\!9\!+\!9)\equiv 8$

$\!\!\bmod 10\!:\ \ x\equiv 8\,$ too, thus by CCRT $\ x\equiv 8\pmod{\!90}.\ $ By above $\,x\equiv 9\pmod{\!11},\,$ so by CRT

$\!\!\bmod\color{#c00}{ 11}\!:\,\ 9\equiv x\equiv 8+90\,\color{#c00}k\equiv 8+2k\iff 2k\equiv 1\equiv 12\iff \color{#c00}{k\equiv 6}$

so we deduce:$\ \ x = 8 + 90(\color{#c00}{6\!+\!11}n) = 548+ 990n$

Answer 2

Do you know the divisibility rules for $9,10,11$? Apply each of them to get the remainder modulo those. For example, as the number ends in $8$ it is equivalent to $8 \bmod 10$. What is the sum of all the digits? That gives the remainder $\bmod 9$. Then find a number less than $990$ that has the right three remainders.