Maths Olympiad Prep

Library / /395 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Example 16 Han Xin Counts the Soldiers: There is a troop of soldiers. If they form a column of five, there is one person left over at the end. If they form a column of six, there are five people left over at the end. If they form a column of seven, there are four people left over at the end. If they form a column of eleven, there are ten people left over at the end. Find the number of soldiers.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let xx be the number of soldiers we are looking for. According to the problem,

In Theorem 1, take m1=5,m2=6,m3=7,m4=11,b1=1m_{1}=5, m_{2}=6, m_{3}=7, m_{4}=11, b_{1}=1, b2=5,b3=4,b4=10b_{2}=5, b_{3}=4, b_{4}=10. Then we have
M=5×6×7×11=2310M1=23105=462M2=23106=385M3=23107=330M4=231011=210\begin{array}{l} M=5 \times 6 \times 7 \times 11=2310 \\ M_{1}=\frac{2310}{5}=462 \\ M_{2}=\frac{2310}{6}=385 \\ M_{3}=\frac{2310}{7}=330 \\ M_{4}=\frac{2310}{11}=210 \end{array}

Let M1M_{1}^{\prime} be a positive integer that satisfies M1M11(mod5)M_{1}^{\prime} M_{1} \equiv 1(\bmod 5), then 11 \equiv M1M1462M12M1(mod5)M_{1}^{\prime} M_{1} \equiv 462 M_{1}^{\prime} \equiv 2 M_{1}^{\prime}(\bmod 5), so we get M1=3M_{1}^{\prime}=3. Let M2M_{2}^{\prime} be a positive integer that satisfies M2M21(mod6)M_{2}^{\prime} M_{2} \equiv 1(\bmod 6), then 1M2M21 \equiv M_{2}^{\prime} M_{2} \equiv 385M2M2(mod6)385 M_{2}^{\prime} \equiv M_{2}^{\prime}(\bmod 6), so we get M2=1M_{2}^{\prime}=1. Let M3M_{3}^{\prime} be a positive integer that satisfies M3M31(mod7)M_{3}^{\prime} M_{3} \equiv 1(\bmod 7), then 1M3M3330M31 \equiv M_{3}^{\prime} M_{3} \equiv 330 M_{3}^{\prime} \equiv M3(mod7)M_{3}^{\prime}(\bmod 7), so we get M3=1M_{3}^{\prime}=1. Let M4M_{4}^{\prime} be a positive integer that satisfies M4M41(mod11)M_{4}^{\prime} M_{4} \equiv 1 \quad(\bmod 11), then 1M4M4210M4M4(mod1 \equiv M_{4}^{\prime} M_{4} \equiv 210 M_{4}^{\prime} \equiv M_{4}^{\prime} (\bmod 11). Therefore, by (46) we get
x3×462+5×385+4×330+10×21067312111(mod2310)\begin{aligned} x & \equiv 3 \times 462+5 \times 385+4 \times 330+10 \times 210 \\ & \equiv 6731 \equiv 2111(\bmod 2310) \end{aligned}

Thus, we have
x=2111+2310k,k=0,1,2,x=2111+2310 k, \quad k=0,1,2, \cdots
x1(mod5),x5(mod6),x4(mod7),x10(mod11).\begin{array}{l} x \equiv 1(\bmod 5), x \equiv 5(\bmod 6), \\ x \equiv 4 \quad(\bmod 7), \quad x \equiv 10 \quad(\bmod 11). \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.