Natural number that has a remainder of $1, 2, 3, 4$ respectively after dividing...

Question

A number when divided by 2 leaves a remainder of 1. When it is divided by 3 leaves a remainder 2. When it is divided by 4 it leaves a remainder of 3. And when it is divided by 5 it leaves remainder of 4. What should be the number ?

Note : I already formulated some formula but I think it might not work:

x = 2a + 1
x = 3b + 2
x = 4c + 3
x = 5d + 4

Answer 1

This is a classic problem in number theory solved by the Chinese remainder theorem. You can look up this algorithm many places, but indeed the (smallest) solution (as posted by @metamorphy) is $59$.

Answer 2

Note that if $x \equiv 3 \pmod{4}$ you get 'for free' that $x \equiv 1 \pmod{2}$. So these two conditions toghether are equivalent to the first one. Thus, you're looking at

$$ \cases{ x \equiv 3 \pmod{4} \\ x \equiv 2 \pmod{3} \\ x \equiv 4 \pmod{5} }$$

By the chinese remainder theorem, this system of equations has a unique solution modulo $4\cdot3\cdot5 = 60$. The only numbers in $\{1,\dots,60\}$ that are congruent to $4$ modulo $5$ are

$$ 0, 4,9,14,19,24,29,34,39,44,49,54,59. $$

Now, our number is odd by the first observation, so we can reduce the former to check only these

$$ 9,19,29,39,49,59 $$

and finally, only $59$ here is $2$ modulo $3$. Thus, the solutions have the form

$$ 60k + 59 $$

or since $59 \equiv -1 \pmod{60}$,

$$ 60k -1 \quad (k \in \mathbb{Z}) $$

Answer 3

Continuing your thought: $$\begin{cases}x=2a+1\\x=3b+2\\x=4c+3\\x=5d+4\end{cases} \Rightarrow \begin{cases}x=2a+1\\2a+1=3b+2\\2a+1=4c+3\\2a+1=5d+4 \end{cases}\Rightarrow \begin{cases}x=2a+1\\a=\frac12(3b+1)\\3b+2=4c+3\\3b+2=5d+4 \end{cases}\Rightarrow \\ \begin{cases}x=2a+1\\a=\frac12(3b+1)\\b=\frac13(4c+1)\\ 4c+3=5d+4 \end{cases}\Rightarrow \begin{cases}x=2a+1\\a=\frac12(3b+1)\\b=\frac13(4c+1)\\ c=\frac14(5d+1) \end{cases}$$ Now you must solve the last Diophantine equation (or by trial and error) and find backwards: $$d=11,c=14,b=19,d=29,x=59.$$ Alternatively, using modular arithmetic: $$\begin{cases} x\equiv 1\pmod{2}\\ x\equiv 2\pmod{3}\\ x\equiv 3\pmod{4}\\ x\equiv 4\pmod{5}\end{cases} \Rightarrow \begin{cases} x=2a+1\\ 2a+1=2\pmod{3}\\ 2a+1=3\pmod{4}\\ 2a+1=4\pmod{5} \end{cases}\Rightarrow \begin{cases} x=2a+1\\ a\equiv 2\pmod{3}\\ a\equiv 1\pmod{2}\\ a\equiv 4\pmod{5} \end{cases}\Rightarrow \\ \begin{cases} x=2a+1\\ a=3b+2\\ 3b+2\equiv1\pmod{2}\\ 3b+2\equiv 4\pmod{5} \end{cases}\Rightarrow \begin{cases} x=2a+1\\ a=3b+2\\ b\equiv-1\pmod{2}\\ b\equiv 4\pmod{5} \end{cases}\Rightarrow \begin{cases} x=2a+1\\ a=3b+2\\ b=2c-1\\ 2c-1\equiv 4\pmod{5} \end{cases}\Rightarrow \\ \begin{cases} x=2a+1\\ a=3b+2\\ b=2c-1\\ c\equiv 0\pmod{5} \end{cases} \Rightarrow \begin{cases} \color{red}{x}=2(30n-1)+1=\color{red}{60n-1}\\ a=3(10n-1)+2=30n-1\\ b=2(5n)-1=10n-1\\ c=5n, n\in \mathbb Z \end{cases}$$

Answer 4

If we increase $a,b,c,d$ by one from your system of equations, observe that these equations now tell us that $x=2a-1=3b-1=4c-1=5d-1$ with the new values. Thus $x+1=3b=4c=5d$, so $60|(x+1)$; thus $x=60n-1$ for any integer $n$.