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

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.

• Solvable by exactly the same method as here in the dupe, i.e. by CCRT it is equivalent to $\,x\equiv 2\pmod{21},\ x\equiv 3\pmod{5}\,$ which is easily solvable by (Easy) CRT. Jan 27 at 5:38

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. Oct 25, 2016 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." Oct 25, 2016 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$$