中国剩余定理1(Chinese remainder theorem)

There is a group of soldiers.

  • If we arrange them into groups of four, there is one left.
  • If we arrange them into groups of five, there are two left.
  • If we arrange them into groups of seven, there are four left.

How many soldiers are there in total at least?


The answer is 137.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

X X
Sep 24, 2018

If we add three more soldiers, it will become: "there's nothing left in a group of 4,5,7"

So, 4 × 5 × 7 = 140 4\times5\times7=140 satisfies the above. Subtract by 3 and get the answer=137

Chew-Seong Cheong
Sep 24, 2018

Relevant wiki: Chinese Remainder Theorem

Let the least number of soldiers be n n . Then

n 1 (mod 4) n 4 a + 1 where a is an integer. 4 a + 1 2 (mod 5) 4 a 1 (mod 5) a 4 n 4 × 5 b + 4 a + 1 = 20 b + 17 where b is an integer. 20 b + 17 4 (mod 7) 6 b + 3 4 (mod 7) 6 b 1 (mod 7) b 6 (mod 7) n 20 ( 6 ) + 17 = 137 \begin{aligned} n & \equiv 1 \text{ (mod 4)} \\ \implies n & \equiv 4a + 1 & \small \color{#3D99F6} \text{where }a \text{ is an integer.} \\ 4a + 1 & \equiv 2 \text{ (mod 5)} \\ 4a & \equiv 1 \text{ (mod 5)} \\ a & \equiv 4 \\ \implies n & \equiv 4\times 5 b + 4a+1 = 20b+17 & \small \color{#3D99F6} \text{where }b \text{ is an integer.} \\ 20b + 17 & \equiv 4 \text{ (mod 7)} \\ 6b + 3 & \equiv 4 \text{ (mod 7)} \\ 6b & \equiv 1 \text{ (mod 7)} \\ b & \equiv 6 \text{ (mod 7)} \\ \implies n & \equiv 20(6)+17 = \boxed{137} \end{aligned}

Thank for the Chinese remainder theorem sir

Shuvodip Das - 2 years, 3 months ago

You are welcome

Chew-Seong Cheong - 2 years, 3 months ago

1 pending report

Vote up reports you agree with

×

Problem Loading...

Note Loading...

Set Loading...