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

Question

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. :)

Answer 1

$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$.

Answer 2

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$

Answer 3

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$$

Answer 4

Task

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

Answer

The answer is 58.

Answer 5

Notice that this number is: -2(mod 3) -2(mod 4) -2(mod 5) -2(mod 6) Thus, we need to calculate the LCM of 3,4,5,6 and subtract 2. The LCM is 60. Thus, the answer is 58.