Sun Tzu's puzzle: remainders 2, 3, 2
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
From : . From among these: 23 is the first (), and then the numbers repeat every : .
Now among those: works at once.
(1)The three moduli are coprime, so by the Chinese remainder theorem the solutions repeat every :
(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.