Questions   
Sort: 
 #2
avatar+26400 
+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

Aug 10, 2017
 #1
avatar+33661 
+4
Aug 10, 2017
 #2
avatar+26400 
+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

Aug 10, 2017
Aug 9, 2017
 #5
avatar+2446 
+3

Another way to solve this problem is to use what the hint suggests-- the triangle inequality theorem.

 

The triangle inequality theorem states that the sum of the lengths of two different sides of a triangle is greater than the third remaining side. Here is a picture that demonstrates this theorem. It might be easier to understand that way:

 

Source: http://s3.amazonaws.com/magoosh-company-site/wp-content/uploads/sites/3/2012/02/23084719/triangle-1.png 

 

Let's apply this to the current problem. Here is a picture to reference as I solve:

 

 

Knowing the triangle inequality theorem, let's just worry about 1 triangle at a time. Let's worry about \(\triangle ABC\). Let's use the theorem to determine the possible lengths that \(\overline{AC}\) can be:
 

\(AB+BC>AC\) \(AB+AC>BC\) \(AC+BC>AB\) Replace the known values into these inequalities and solve.
\(3+6>AC\) \(3+AC>6\) \(AC+6>3\)  
\(9>AC\) \(AC>3\) \(AC>-3\)  
       

 

With so many solutions, sometimes it easier me to sketch a graph of all the solutions and figure out where the solutions overlap. Here is a picture of the number line graph:

 

 

Where is the area of overlap? The area of overlap is from 3 to 9. Therefore, we can express the possible lengths of AC as the following compound inequality: \(3 . We aren't done yet! We now have to consider the other triangle,  \(\triangle ACD\). Again, we will have to consider and use the triangle inequality theorem again:

 

\(AD+DC>AC\) \(DC+AC>AD\) \(AC+AD>DC\) Yet again, plug in the known values.
\(4+4>AC\) \(4+AC>4\) \(AC+4>4\) Solve.
\(8>AC\) \(AC>0\) \(AC>0\)  
       

 

For this one, you could use a number line graph again, but I will just use logic to figure out the set of possible lengths AC can be in this case. In two of our inequalities, it was determined that \(AC>0\). If \(8>AC\), or, as I like to think of it, \(AC<8\), this means that the compound inequality for AC in this case is \(0 . Now, let's look at the restriction we placed on AC before.

 

 

\(3

\(0

 

AC has to comply to both restrictions because it is in both triangles, which means that the final compound inequality is 

\(3 . Therefore, the only possible integers are 4, 5, 6, and 7.

 

Bam! Done!

 #3
avatar+15127 
+1
Aug 9, 2017

1 Online Users