Using the Chinese Remainder theorum solve for the total amount of soldiers and e

Question

Using the Chinese Remainder theorum solve for the total amount of soldiers and explain each step.

A Chinese general knows that his troops number somewhat above 1000, but otherwise isn't really sure of the number. He asks them to line up in rows of 11, and finds that the final "remainder" row has 1 soldier. He asks them to line up in rows of 13, and finds that the final "remainder" row has 8 soldiers. He asks them to line up in rows of 17, and finds 2 soldiers in the final "remainder" row. How many soldiers are in his army?

Explanation / Answer

Let, x be number of soldiers

So,

x=1 mod 11

x=8 mod 13

x=2 mod 17

x=17m+2=6m+2 mod 11=1 mod 11, m is any integer

6m+2=1 mod 11

6m=-1 mod 11

2*6m=-2 mod 11

12m=-2 mod 11

m=-2=9 mod 11

m=11k+9

x=17(11k+9)+2=187k+155, k is any integer

x=187k+155=8 mod 13

187k+155=5k-1=8 mod 13

5k=9 mod 13

5*5k=9*5 mod 13

25k=45 mod 13

-k=6 mod 13

k=-6=7 mod 13

k=13p+7

x=187*(13p+7)+155=2431p+1464

Smallest number above 1000 is fpr p=1

x=2431+1464=3895

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.