heureka

avatar
Nombre de usuarioheureka
Puntuación26367
Membership
Stats
Preguntas 17
Respuestas 5678

 #2
avatar+26367 
+3

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

 

laugh

10 ago 2017
 #2
avatar+26367 
+1

If a,b,c are integers from the set of positive integers less than 7 such that

\(\begin{align*} abc&\equiv 1\pmod 7,\\ 5c&\equiv 2\pmod 7,\\ 6b&\equiv 3+b\pmod 7, \end{align*}\)

then what is the remainder when a+b+c is divided by 7 ?

 

\(\begin{array}{rcll} \mathbf{Formula}: \\\\ 6b & \equiv & 3+b \pmod 7 \quad & | \quad -b \\ 6b-b & \equiv & 3+b-b \pmod 7 \\ 5b & \equiv & 3 \pmod 7 \\ \begin{array}{|rcll|} \hline \mathbf{5b} &\mathbf{\equiv}& \mathbf{3 \pmod 7} \\ \hline \end{array} & (1) \\\\ \begin{array}{|rcll|} \hline \mathbf{5c} &\mathbf{\equiv}& \mathbf{2 \pmod 7} \\ \hline \end{array} & (2) \\\\ \begin{array}{|rcll|} \hline \mathbf{abc} &\mathbf{\equiv}& \mathbf{1 \pmod 7} \\ \hline \end{array} & (3) \\\\ \begin{array}{|rcll|} \hline \mathbf{a+b+c} &\mathbf{\equiv}& \mathbf{x \pmod 7} \\ \hline \end{array} & (4) \\\\ (1)+(2): \qquad 5b+5c & \equiv & 3+2 \pmod 7\\ 5(b+c) & \equiv & 5 \pmod 7 \quad & | \quad :5 \\ \frac{5(b+c)}{5} & \equiv & \frac{5}{5} \pmod 7 \\ b+c & \equiv & 1 \pmod 7 \\ \begin{array}{|rcll|} \hline \mathbf{b+c} &\mathbf{\equiv}& \mathbf{1 \pmod 7} \\ \hline \end{array} & (5) \\\\ (5) \text{ in }(4): \qquad a+b+c & \equiv & x \pmod 7 \\ a+ (b+c) & \equiv & x \pmod 7 \\ a+ (1) & \equiv & x \pmod 7 \\ a+ 1 & \equiv & x \pmod 7 \\ \begin{array}{|rcll|} \hline \mathbf{a+ 1 } &\mathbf{\equiv}& \mathbf{x \pmod 7} \\ \hline \end{array} & (6) \\\\ (1) \times (2): \qquad 5b\times 5c & \equiv & 3\times 2 \pmod 7 \\ 25bc & \equiv & 6 \pmod 7 \quad & | \quad 6 \equiv -1 \pmod 7 \\ 25bc & \equiv & -1 \pmod 7 \\ \begin{array}{|rcll|} \hline \mathbf{25bc} &\mathbf{\equiv}& \mathbf{-1 \pmod 7} \\ \hline \end{array} & (7) \\\\ \mathbf{a=\ ? } \\ (3) \div (7): \qquad \frac{abc}{25bc} & \equiv & \frac{1}{-1} \pmod 7 \\ \frac{a}{25} & \equiv & -1 \pmod 7 \quad & | \quad \times 25 \\ \frac{25a}{25} & \equiv & (-1)\cdot 25 \pmod 7 \\ a & \equiv & -25 \pmod 7 \\ a & \equiv & -25 + 4\times 7 \pmod 7 \\ a & \equiv & -25 + 28 \pmod 7 \\ a & \equiv & 3 \pmod 7 \\ a-3 &=& n\cdot 7 \\ a &=& 3+ n\cdot 7 \qquad n \in \mathbb{Z} \\ \begin{array}{|rcll|} \hline \mathbf{a} &\mathbf{=}& \mathbf{ 3+ n\cdot 7 \qquad n \in \mathbb{Z} } \\ \hline \end{array} & (8) \\\\ \mathbf{x=\ ? } \\ (6): \qquad a+1 & \equiv & x \pmod 7 \quad & | \quad a = 3+ n\cdot 7 \\ 3+ n\cdot 7 + 1 & \equiv & x \pmod 7 \\ 4+ n\cdot 7 & \equiv & x \pmod 7 \quad & | \quad n\cdot 7 \pmod 7 = 0 \\ 4 & \equiv & x \pmod 7 \\ 4 \pmod 7 &=& x \\ 4 &=& x \\ \begin{array}{|rcll|} \hline \mathbf{x} &\mathbf{=}& \mathbf{ 4 } \\ \hline \end{array} \\ \end{array}\)

 

The remainder when \(a+b+c\) is divided by \(7\) is \(\mathbf{4}\)

 

laugh

10 ago 2017