0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.