A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively

A number when successively divided by $9$, $11$ and $13$ leaves remainders $8$, $9$ and $8$ respectively.

The answer is $881$, but how? Any clue about how this is solved?


Note $\ $ A newer duplicate question with cited source makes it clear that this is not a CRT problem (as was inferred in the above comments) but, more simply, a question on iterated division with remainder. The answer below is for the CRT interpretation.

Hint $\ $ Note that $\rm\ x\equiv 8\:\ (mod\ 9),\ x\equiv 8\:\ (mod\ 13)$ $\iff$ $\rm x\equiv 8\:\ (mod\ 9\cdot 13),\:$ follows from CCRT = special constant case $\rm\,a\! =\! b\,$ of Easy CRT (below), reducing the $3$ equations to these $2$:

$$\begin{array}{ll}\rm x\ \equiv\ 9\ \ (mod\ \ 11)\\ \rm x\ \equiv\ 8\ \ (mod\ 9\cdot\! 13)\end{array}$$

Applying Easy CRT (below) with $\rm\ a=9,\ b = 8,\ n=\:9\cdot 13,\ m=11,\ $ noting that

$$\rm mod\:\ m\!=\!11\!:\ \ \frac{a-b}{n}\ =\ \frac{9-8}{9\cdot 13}\ \equiv\ \frac{1}{-2\cdot 2}\ \equiv\ \frac{12}{-4}\ \equiv\ {-3}\ \equiv\ \color{#C00}8 $$

we quickly obtain the unique solution: $\rm\ \ x\, \equiv\, 8 + 9\cdot 13\cdot [\color{#C00}8]\,\equiv\, 944 \ \ (mod\,\ 11\cdot9\cdot 13)$

Theorem (Easy CRT) $\rm\ \ $ If $\rm\ m,n\:$ are coprime integers then $\rm\ \color{#0a0}{n^{-1}}\ $ exists $\rm\ (mod\ m)\ \ $ and

$\rm\displaystyle\quad\quad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\rm\ a\ \ (mod\ m) \\ \rm x&\equiv&\rm\ b\ \ (mod\ n)\end{eqnarray} \ \iff\ \ x\ \equiv\ b + n\ \bigg[\frac{a-b}{\color{#0a0}n}\ mod\ m\:\bigg]\ \ (mod\ mn)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ n\!:\,\ x\equiv b + n\ [\cdots]\equiv b\:,\ $ and $\rm\ mod\ m\!:\,\ x\equiv b + (a-b)\ n/n\: \equiv\: a\:.$

$\rm\ (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\ mn)\ $ since if $\rm\ x',x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \ $ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = mn\:.\ \ $ QED

Note $\ $ The constant case optimization of CRT = Chinese Remainder Theorem frequently proves handy in practice, e.g. see also this answer, where it shortens a few-page proof to a few lines.


Program your computer to divide the numbers 1, 2, 3, etc., by 9, 11, and 13, and to report to you when it finds the remainders are, respectively, 8, 9, and 8. This approach will teach you more about computer programming than about Number Theory, so it may not be what you want - but it is absolutely for certain a way to solve the problem.


Work backwards. The easiest number that leaves a remainder of $8$ when dividing by $13$ is $8$ itself. Then $8 \cdot 11 + 9 = 97$ will leave a quotient of $8$ and a remainder of $9$ for the division by $11$. Then $9 \cdot 97+8=881$ is what you are looking for.