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

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 mod 10, x = k mod 11 and x = k mod 9. But how can I apply the CRT on such a large number?

Thanks! And sorry about the very similar question.

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

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.