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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this communityWhat 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}$.
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$$