WordGPT

Sun Tzu's puzzle: remainders 2, 3, 2

Exercise · Level 3 (Medium)

A number leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. What is the smallest such number?

x≡2 (3),x≡3 (5),x≡2 (7)x\equiv2\ (3),\quad x\equiv3\ (5),\quad x\equiv2\ (7)

wordgptpro.com

Solution

  1. From x≡3(mod5)x\equiv3\pmod5: x=3,8,13,18,23,…x=3,8,13,18,23,\dots. From x≡2(mod7)x\equiv2\pmod7 among these: 23 is the first (23=3⋅7+223=3\cdot7+2), and then the numbers repeat every 5⋅7=355\cdot7=35: 23,58,93,…23,58,93,\dots.

  2. Now x≡2(mod3)x\equiv2\pmod3 among those: 23=3⋅7+223=3\cdot7+2 works at once.

    23=7⋅3+2,23=4⋅5+3,23=3⋅7+2\begin{aligned}23&=7\cdot3+2,\quad 23\\&=4\cdot5+3,\quad 23\\&=3\cdot7+2\end{aligned}
    (1)
  3. The three moduli are coprime, so by the Chinese remainder theorem the solutions repeat every 3⋅5⋅7=1053\cdot5\cdot7=105:

    x≡23(mod105)x\equiv23\pmod{105}
    (2)
Answerx=23 (mod 105)x=23\ (\text{mod }105)

wordgptpro.com

Need a hint?

Combine two conditions at a time: list numbers satisfying the largest modulus and test the others.

The smallest number is 23, and all solutions are 23 + 105k. (This puzzle appears in Sun Tzu's mathematical manual from the 3rd–5th century.)

How to work it out

  1. From x≡3(mod5)x\equiv3\pmod5: x=3,8,13,18,23,…x=3,8,13,18,23,\dots. From x≡2(mod7)x\equiv2\pmod7 among these: 23 is the first (23=3⋅7+223=3\cdot7+2), and then the numbers repeat every 5⋅7=355\cdot7=35: 23,58,93,…23,58,93,\dots.

  2. Now x≡2(mod3)x\equiv2\pmod3 among those: 23=3⋅7+223=3\cdot7+2 works at once.

    23=7⋅3+2,23=4⋅5+3,23=3⋅7+2\begin{aligned}23&=7\cdot3+2,\quad 23\\&=4\cdot5+3,\quad 23\\&=3\cdot7+2\end{aligned}
    (1)
  3. The three moduli are coprime, so by the Chinese remainder theorem the solutions repeat every 3⋅5⋅7=1053\cdot5\cdot7=105:

    x≡23(mod105)x\equiv23\pmod{105}
    (2)
LaTeX source of the formulas on this page
\[ x=23\ (\text{mod }105) \]
\[ 23=7\cdot3+2,\quad 23=4\cdot5+3,\quad 23=3\cdot7+2 \]
\[ x\equiv23\pmod{105} \]

Questions

What is the answer to: Sun Tzu's puzzle: remainders 2, 3, 2?

The smallest number is 23, and all solutions are 23 + 105k. (This puzzle appears in Sun Tzu's mathematical manual from the 3rd–5th century.)

What is the key idea?

Solve one congruence at a time, keeping the common step size as the product of the moduli.

Is there a hint?

Combine two conditions at a time: list numbers satisfying the largest modulus and test the others.

Related problems

More number theory problems

    Sun Tzu's puzzle: remainders 2, 3, 2: answer and solution | WordGPT