Counting Soldiers Discreetly

We apply the Chinese remainder theorem here. We have 4 linear congruences, make them as pairs of 2,

$\color{#D61F06}{(1)} \quad \quad x\equiv 4 \pmod{9}$ , $\quad \quad x\equiv 3 \pmod{19}$

$\color{#D61F06}{(2)}\quad \quad x\equiv 0 \pmod{11}$ , $\quad \quad x\equiv 1 \pmod{13}$

Solving the 1st 2, you get $x\equiv 22 \pmod{171}$

This is because by Bezout's theorem

$1\times 19 - 2\times 9 = 1$

hence the common solution will be

$4\times 19\times 1+ (-2)\times 9 \times 3 \pmod{171} = 76-54 = 22 \pmod{171}$

And solving the second pair, because by Bezout's theorem, you get

$6\times 11 - 5\times 13 =1$ , so the common solution will be $6\times 11 \pmod{143} = 66\pmod{143}$

Hence the task is finding common solution of

$\quad \quad x\equiv 22 \pmod{171}$

$\quad \quad x\equiv 66 \pmod{ 143}$

( I will work this one completely to show how bezout's theorem is used)

$171=143 +28$

$143=28\times 5 +3$

Hence we get

$1=28 -9\times 3$

$1=171-143 - 9 (143-28\times 5)$

$1= 171-143 - 9(143-5(171-143))$

$1=171-143+45\times 171 - 54\times 143 = 46\times 171 - 55\times 143$

Thus in the linear congruences system, your answer will be $\pmod{143\times 171}$ and it will be

$22\times 143\times (-55) + 66\times 171\times 46 \equiv 346126 \equiv 3784 \pmod{24453}$

$\color{#D61F06}{\textbf{This means that the solution of out original system is }}$

$\displaystyle x\equiv 3784 \pmod{24453}$

And the second solution of this is $3784+24453 = \boxed{28237}$

This can be done via a direct application of the Chinese Remainder Theorem to the system of equations:

$\color{#D61F06}{(1)} \quad \quad x\equiv4 \pmod{9}$

$\color{#D61F06}{(2)} \quad \quad x\equiv0 \pmod{11}$

$\color{#D61F06}{(3)} \quad \quad x\equiv1 \pmod{13}$

$\color{#D61F06}{(4)} \quad \quad x\equiv3 \pmod{19}$

Now, using the variable conventions in the page, we obtain $N$ , $n_i$ , and $y_i$ :

$N = 9 \times 11 \times 13 \times 19 = \mathbf{24453}$

$n_1 = 9, \quad \quad y_1 = {N \over{n_1}} = \mathbf{2717}$

$n_2 = 11, \quad \quad y_2 = {N \over{n_2}} = \mathbf{2223}$

$n_3 = 13, \quad \quad y_3 = {N \over{n_3}} = \mathbf{1881}$

$n_4 = 19, \quad \quad y_4 = {N \over{n_4}} = \mathbf{1287}$

Next, we find $z_i \equiv y_i^{-1} \pmod{n_i}$ :

$z_1 \equiv 2717^{-1} \equiv (-1)^{-1} \equiv -1 \equiv \mathbf{8} \pmod{9}$

$z_2 \equiv 2223^{-1} \equiv 1^{-1} \equiv \mathbf{1} \pmod{11}$

$z_3 \equiv 1881^{-1} \equiv 9^{-1} \equiv \mathbf{3} \pmod{13}$

$z_4 \equiv 1287^{-1} \equiv 14^{-1} \equiv -4 \equiv \mathbf{15} \pmod{19}$

These inverses were found via the extended Euclidean algorithm.

Next, to obtain the smallest solution, we apply $x \equiv \sum_{i=1}^4{a_iy_iz_i} \pmod N$ :

$x \equiv (4)(2717)(8) + (0)(2223)(1) + (1)(1881)(3) + (3)(1287)(15) \pmod{24453}$

$x \equiv \mathbf{3784} \pmod{24453}$

Finally, the second solution of this is $24453 + 3784 = \boxed{\mathbf{28237}}$

I have solved it in following manner. first the number which satisfies two condition(11-13) is 66. after that i added (11 13=)143 in it until it satisfy third condition (9) that number is 1210 and than i added (143 9)=1287 until it satisfy fourth condition(19) so I find that number 3784 satisfies all this condition to find solution I added(9 13 11*19)=24,453 and I got ans. which is 28,237

I'm not sure if my solution would be valid because I have a need to use an application to be able to solve this. I used MS Excel to solve this problem. Since there is no remainder for multiples of 11, I'm using this as basis. So column 1 consists of multiples of 11, that is Row 1 = 11, Row 2 = 22, and so on.

Column 2 is "=MOD(Ax,9) Column 3 is "=MOD(Ax,13) Column 4 is "=MOD(Ax,19)

Where x is row number. We're finding the following values: Ax (any multiple of 11), 4, 1, 3 in a single row. I used Conditional formatting using colors and find an all colored row. Drag down the formula. You can simply check each rows but to make it easier I added 1 more row with formula "=Bx-Cx-Dx" then I filtered those with answer as "0" which will show up lots of answers but you can easily see a colored row. The 1st value is 3784 but we are looking for the 2nd smallest and that will be seen at row 2567 with a value of 28237.

Note: Actually filtering B, C and D column to find values of 4, 1, 3 is easier that what I did.

I hope this helps even though it is not a pen and paper type of solution.

Cheers.