+0

# 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

0
43
2
+74

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
Sort:

#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
+18369
+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

### 4 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details