# Find the least value of x which when divided by 3 leaves remainder 1, …

A number when divided by 3 gives a remainder of 1; when divided by 4, gives a remainder of 2; when divided by 5, gives a remainder of 3; and when divided by 6, gives a remainder of 4. Find the smallest such number.

How to solve this question in 1 min?

Any help would be appreciated. :)

$x + 2$ must be divisible by $3, 4, 5$, and $6$. Hence $x + 2 = n \cdot \text{lcm}(3,4,5,6) = n \cdot 60$, for any integer $n$. So $x = 60n - 2$ for any integer $n$. Assuming the problem asks for the "smallest positive" such number, the answer is $58$.

So we need $\displaystyle x=3a+1=4b+2=5c+3=6d+4$

which can also the written as $\displaystyle x=3(a+1)-2=4(b+1)-2=5(c+1)-2=6(d+1)-2$

So, we need to find $x$ such the remainder $=-2$ for the divisors $3,4,5,6$

Now, the smallest number which is divisible by $3,4,5,6$ is lcm$(3,4,5,6)=60$

So, $60m-2$ (where $m$ is an integer) will leave $-2$ as remainder

Find proper $m$ for the minimum positive value of $x$

Hint $\$ Apply the ubiquitous constant case optimization of CRT

$$\ x\equiv m_i\!-\!2\!\!\!\pmod{m_i}\iff x\!+\!2\equiv 0\!\!\pmod {m_i}\iff m_i\mid x\!+\!2\iff {\rm lcm}\{m_i\}\!\mid x\!+\!2$$

Find the smallest $x \in \mathbb{N}_0$ such that: \begin{align} x &\equiv 1 \mod 3\\ x &\equiv 2 \mod 4\\ x &\equiv 3 \mod 5\\ x &\equiv 4 \mod 6 \end{align}

## Solution

Again, you can solve this quite fast with programming.

### The simple solution

Because the numbers are so small that you can use very inefficient solutions (but very fast in terms of programming time):

x = 0
while True:
if x % 3 == 1 and x % 4 == 2 and x % 5 == 3 and x % 6 == 4:
print(x)
break
x += 1


### A faster solution

Every single of the six constraints has to be true. The sixth constraint is only true for every sixth number, so we can "jump" in steps of six:

x = 4
while True:
if x % 3 == 1 and x % 4 == 2 and x % 5 == 3:
print(x)
break
x += 6


The answer is 58.