1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OP asks for a one minute solution (perhaps for an exam) and you give him this programming session!! $\endgroup$ – tatan Jun 11 '16 at 17:17
  • $\begingroup$ I wrote that in much less than a minute $\endgroup$ – Martin Thoma Jun 12 '16 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.