# What is the number that, when divided by $3$, $5$, $7$, leaves remainders of $2$, $3$, $2$, respectively?

What is the number?

The LCM of the divisors is 105. I think this has something to do with the Chinese remainer theorem, but I am not sure how to apply this knowledge.

Yes, this is the first known incidence of the Chinese Remainder Theorem (CRT).

From Wikipedia:

The earliest known statement of the CRT, as a problem with specific numbers, appears in the 3rd-century book Sunzi's Mathematical Classic (孫子算經) by the Chinese mathematician Sun Tzu:[2] “ There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?"

The solution given by the CRT algorithm is indeed $x\equiv 23 \bmod 105=3\cdot 5\cdot 7$, as shown there. So there are $23+k\cdot 105$ things, for $k\in \mathbb{N}$.

• Is he the same that the autor of The Book of War or someone homonym?. Thank you. – Piquito Oct 25 '16 at 15:07
• No, this is not the case. From Wikipedia: "The specific identity of its author Sunzi (lit. "Master Sun") is still unknown but he lived much later than eponymous Sun Tzu, author of The Art of War." – Dietrich Burde Oct 25 '16 at 15:14

Chinese theorem can be used, but for this problem can be avoided: call the number $n$. Then $n-2$ is a multiple of $21$. Since $n-3$ is a multiple of $5$, $n$ ends with $3$ or $8$ and $n-2$ ends with $1$ or $6$. The smallest value for $n-2$ is $21$.

We can solve in a simple way without the Chinese Remainder Theorem.

Let $n = 3x + 2 = 5y + 3 = 7z + 2$.

Then, $5y + 3 \equiv 3x + 2 \equiv (\mod 3) \implies y \equiv 1(\mod 3)y$

Hence let $y = 3k + 1$ which gives $n = 5y + 3 = 15k + 8$.

Again $n = 15k + 8 \equiv 7z + 2 (\mod 7) \implies k \equiv 1 (\mod 7)$

Hence let $k = 7m + 1$. This gives $n = 15k + 8 = 105m + 23$

Thus in general the number $n$ is of the form $n = 105m + 23$. The smallest such number is when $m = 0$, we get $n = 23$.

Let $N$ be the number so we have$$N=3n_1+2=7n_2+2\Rightarrow n_1=7k\Rightarrow N=21k+2$$ Besides $$21k+2=5n_3+3\iff 21k-5n_3=1\qquad (*)$$ Since $(k,n_3)=(1,4)$ is a solution of $(*)$ the general solution is $$\begin{cases}k=5t+1\\n_3=21t+4\end{cases}$$ It follows $$N=21(5t+1)+2=23+105t\text{ where } t\in\Bbb Z$$