Sun Tzu Suan Ching/Examples/Example 2

From ProofWiki
Jump to navigation Jump to search

Example of Problem from Sun Tzu Suan Ching

There are certain things whose number is unknown.
Repeatedly divided by $3$, the remainder is $2$;
by $5$ the remainder is $3$,
and by $7$ the remainder is $2$.
What will be the number?


Solution

The number of objects could be any one of the numbers:

$23 + 105 n$

where $n \in \N$ is an arbitrary natural number.


Proof

The numbers in this sequence all leave a remainder of $2$ when divided by $3$:

$2, 5, 8, 11, 14, 17, 20, 23, 26, \ldots$

Of these, the numbers in this sequence all leave a remainder of $3$ when divided by $5$:

$8, 23, 38, \ldots$

Of these, the numbers in this sequence all leave a remainder of $2$ when divided by $7$:

$23, 128, 233, \ldots$

The difference between consecutive terms is $105 = 3 \times 5 \times 7$, according to the Chinese Remainder Theorem.

$\blacksquare$


Sources