Solving CRT system with moduli in AP (Arithmetic Progression)

Question

If they put the rows of 13, there are 8 students left; if they put the rows of 15, there are 3 students left and if they put the rows of 17, there are 9 students left. How many students are there given that the total students are < 5000?

The following congruences are: $$x\equiv 8 \pmod {13} \\ x\equiv 3 \pmod {15} \\ x\equiv 9 \pmod {17}$$

I'm still new to this, how can I apply Chinese Remainder Theorem to these congruences to find the total students?

Answer 1

Let $N$ be the number of students. Let $M = 13\times 15 \times 17 = 3315$

$\qquad\ M_1 = 15 \times 17 = \color{#c00}{255},\,\ \ y_1 = 255^{-1} \equiv \ \ 8^{-1}\equiv \ \ \color{#c00}{5}\ \pmod{13} $

$\qquad\ M_2 = 13 \times 17 = \color{#0a0}{221},\,\ \ y_2 = 221^{-1} \equiv 11^{-1} \equiv \color{#0a0}{11}\pmod{15} $

$\qquad\ M_3 = 13 \times 15 = \color{#90f}{195},\,\ \ y_3 = 195^{-1} \equiv\ \ 8^{-1}\equiv \color{#90f}{15} \pmod{17} $

Thus $\ N \equiv 8 \times \color{#c00}{255 \times 5}\, +\, 3 \times \color{#0a0}{221 \times 11}\, +\, 9 \times \color{#90f}{195 \times 15}\,\equiv\, 723\pmod{3315} $

So the number of students $\, N = 723 + 3315 \times k $

With $\,N < 5000,\ N = 4038\,$ with $\,k = 1$

You can read more here (Vietnamese wiki page on CRT)

Answer 2

It's easy since here since the moduli are in A.P. (Arithmetic Progression) $\,13,15,17\,$ so we can apply a simple inversion-free version of CRT that only needs to invert the A.P. step-size (here $\color{#c00}2$). First we transform our residues $\,8,3,9\,$ to $\rm\color{#0a0}{con}\color{#90f}{gruent}$ ones in A.P (using the Remark below), so

$$\begin{align} &x\equiv 8\equiv\ \ \:\! \color{#90f}{99}\!\!\!\pmod{\!13}\\ &x\equiv 3\equiv\ \ \ \ \:\! 3\!\!\!\pmod{\!15}\\ &x\equiv 9\equiv\! \color{#0a0}{-93}\!\!\!\pmod{\!17}_{\phantom{|_{|_|}}}\end{align}\qquad\qquad$$

therefore $\bmod \color{#c00}{\color{#0af}{13}\!+\!2n}\!:\ x\equiv \color{#90f}{99}\color{#c00}{-2n}(48)\!\equiv 99+\color{#0af}{13}(48)\equiv\,\bbox[5px,border:1px solid #c00]{723}$

Remark $ $ To get residues in A.P. we solve $\,3\!-\!(8\!+\!13j) = (9\!-\!17k)\!-\!3 \!\iff\! 17k\!-\!13j\equiv 11$ $ \!\iff\!\!\bmod 13\!:\, 4k^{\phantom{|^|}}\!\!\!\equiv\! 11\!\equiv\! 24\!\iff\! k\equiv 6\,$ so $\,j = 7,\,$ so $\,8\!+\!13j=\color{#90f}{99},\,$ $9\!-\!17k=\color{#0a0}{-93}$