A Chinese emperor orders a regiment of soldiers in his palace to divide into groups of $4$. They do so successfully. He then orders them to divide into groups of $3$, upon which $2$ of them are left without a group. He then orders them to divide into groups of $11$, upon which $5$ are left without a group. If the emperor estimates there are about two hundred soldiers in the regiment, what is the most likely number of soldiers in the regiment?

RektTheNoob
Aug 9, 2017

#1**0 **

n mod 4 = 0, n mod 3 = 2, n mod 11 = 5, solve for n

The LCM of 2, 11 = 33, and modulus 4 = 0 remainder, and by simple iteration we have:

n = 4 (33 D + 26), where D =0, 1, 2, 3.....etc.

n=104, **236**, 368......etc.

Since the Emperor estimates the regiment to have about 200 soldiers, then 236 soldiers is the most likely number.

Guest Aug 9, 2017

#2**+1 **

**A Chinese emperor orders a regiment of soldiers in his palace to divide into groups of 4. They do so successfully. He then orders them to divide into groups of 3, upon which 2 of them are left without a group. He then orders them to divide into groups of 11, upon which 5 are left without a group. If the emperor estimates there are about two hundred soldiers in the regiment, what is the most likely number of soldiers in the regiment?**

\(\begin{array}{|rcll|} \hline n &\equiv& {\color{red}0} \pmod {{\color{green}4}} \\ n &\equiv& {\color{red}2} \pmod {{\color{green}3}} \\ n &\equiv& {\color{red}5} \pmod {{\color{green}11}} \\\\ m &=& {\color{green}4}\cdot {\color{green}3} \cdot {\color{green}11} \\ &=& 132 \\ \hline \end{array} \)

\(\text{Because } 3\cdot 11 \text{ and } 4 \text{ are relatively prim } ( gcd(33,4) = 1! ) \\ \text{and because } 4\cdot 11 \text{ and } 3 \text{ are relatively prim } ( gcd(44,3) = 1! ) \\ \text{and because } 4\cdot 3 \text{ and } 11 \text{ are relatively prim } ( gcd(12,11) = 1! ) \\ \text{we can continue}\)

\(\small{ \begin{array}{|rcll|} \hline n &=& {\color{red}0} \cdot {\color{green}3\cdot 11} \cdot \Big( \frac{1}{\color{green}3\cdot 11}\pmod {{\color{green}4}} \Big) \\ & +& {\color{red}2} \cdot {\color{green}4\cdot 11} \cdot \Big( \frac{1}{\color{green}4\cdot 11}\pmod {{\color{green}3}} \Big) \\ & +& {\color{red}5} \cdot {\color{green}4\cdot 3} \cdot \Big( \frac{1}{\color{green}4\cdot 3}\pmod {{\color{green}11}} \Big) \\ & +& {\color{green}4}\cdot {\color{green}3} \cdot {\color{green}11} \cdot k \quad & | \quad k\in Z\\\\ n &=& {\color{red}2} \cdot {\color{green}44} \cdot \Big( \frac{1}{\color{green}44}\pmod {{\color{green}3}} \Big) +{\color{red}5} \cdot {\color{green}12} \cdot \Big( \frac{1}{\color{green}12}\pmod {{\color{green}11}} \Big) +132 \cdot k \quad & | \quad k\in Z\\ \hline \end{array} } \)

\(\begin{array}{rcll} && \frac{1}{\color{green}44}\pmod {{\color{green}3}} \quad &| \quad \text { modular inverse } 44\cdot \frac{1}{44} \equiv 1 \pmod {3} \\ &=& {\color{green}44}^{\varphi({\color{green}3})-1} \pmod {{\color{green}3}} \quad & | \quad \text{ Euler's totient function } \varphi(n) \quad \varphi(p) = p-1 \\ &=& 44^{2-1} \pmod {3} \\ &=& 44 \pmod {3} \\ &=& 2 \\\\ && \frac{1}{\color{green}12}\pmod {{\color{green}11}} \quad &| \quad \text { modular inverse } 12\cdot \frac{1}{12} \equiv 1 \pmod {11} \\ &=& {\color{green}12}^{\varphi({\color{green}11})-1} \pmod {{\color{green}11}} \quad & | \quad \text{ Euler's totient function } \varphi(n)\quad \varphi(p) = p-1 \\ &=& 12^{10-1} \pmod {11} \\ &=& 12^{9} \pmod {11} \quad & | \quad 12 \equiv 1 \pmod {11 } \\ &=& 1^{9} \pmod {11} \\ &=& 1 \\ \end{array}\)

\(\small{ \begin{array}{|rcll|} \hline n &=& {\color{red}2} \cdot {\color{green}44} \cdot \Big( 2 \Big) +{\color{red}5} \cdot {\color{green}12} \cdot \Big( 1 \Big) +132 \cdot k \\ &=& 176 +60 +132 \cdot k \\ &=& 236 +132 \cdot k \quad & | \quad 236 \equiv 104 \pmod {132} \\ \mathbf{n} & \mathbf{=} & \mathbf{104 +132 \cdot k } \quad & | \quad \mathbf{ k\in Z } \\ \hline \end{array} } \)

\(\begin{array}{|lrcll|} \hline k=0: & n & = & 104 \\ k=1: & n & = & 104+132 \\ & &\mathbf{=}& \mathbf{236} \\ k=2: & n & = & 104+132\cdot 2 \\ & & = & 368 \\ \ldots \\ \hline \end{array} \)

The most likely number of soldiers in the regiment is **236**

heureka
Aug 10, 2017