The problem: Find the smallest positive integer $x$ such that

$x$ divided by $4$ has remainder $1$

$x$ divided by $5$ has reminder $2$

$x$ divided by $6$ has remainder $3$

Now, my first idea was to add to each divisor its the remainder and multiply the quantities obtained.


But $315$ does not satisfy all the conditions above, and I don't know how to get the smallest integer that satisfies the conditions. Any help?

  • $\begingroup$ Are you familiar with the congruence relations on the integers? $\endgroup$ – Luca Bressan Sep 9 '16 at 17:29
  • $\begingroup$ Yes but im not fan of them $\endgroup$ – Peterix Sep 9 '16 at 17:30
  • $\begingroup$ $315$ is neither the smallest number that works, nor is it even one such number. $315$ leaves a remainder of $0$ when divided by $5$ ... $\endgroup$ – Zubin Mukerjee Sep 9 '16 at 17:33

If $x \equiv 1\pmod{4}$, then $$x \equiv 1,5,9,13,17\pmod{20}$$ Of these, only $17$ is also $2 \pmod{5}$. Therefore $$x \equiv 17 \pmod{20}$$

Next, the LCM of $20$ and $6$ is $60$.

If $x \equiv 17 \pmod{20}$, then $$x \equiv 17, 37, 57 \pmod{60}$$

Of these, only $57$ is $3\pmod{6}$. This means

$$x \equiv 57\pmod{60}$$

This means $\boxed{57}$ is the smallest $x$ that satisfies your conditions.

  • $\begingroup$ Note that this method also finds all $x$ that satisfy your conditions. Simply add any multiple of $60$ to $57$ to get other values of $x$ that will work. $\endgroup$ – Zubin Mukerjee Sep 9 '16 at 17:33

You may have solved problems of the kind: Find x such that it leaves a remainder 3 when divided by 4, 5 or 6.

In the above scenario you first find out a number which divisible by each of 4, 5 and 6 (lcm or it's multiple) and then you add the remainder 3 to that number. You can find infinitely many such numbers as there are infinite number of multiples of $lcm(4,5,6)$.

Here notice that $4-1 = 3$, $5-2 = 3$ and $6-3 = 3$. So basically we are solving the exactly same problem here, we have just changed the remainder from $3$ to $-3$.

As $lcm(4,5,6) = 60$, such numbers are of form $60n - 3$, for any integer $n$.


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.