5
$\begingroup$

Find the smallest natural number that leaves residues $5,4,3,$ and $2$ when divided respectively by the numbers $6,5,4,$ and $3$.

I tried $$x\equiv5\pmod6\\x\equiv4\pmod5\\x\equiv3\pmod4\\x\equiv2\pmod3$$What $x$ value?

$\endgroup$
13
$\begingroup$

HINT: Notice that your congruences are equivalent to the following ones:

$$\left\{\begin{align*} x\equiv-1\pmod6\\ x\equiv-1\pmod5\\ x\equiv-1\pmod4\\ x\equiv-1\pmod3 \end{align*}\right.$$

In other words, $x+1$ is divisible by $6,5,4$, and $3$. What’s the smallest positive integer with that property?

$\endgroup$
2
$\begingroup$

Given

$x=6a+5=6(a+1)-1$

$x=5b+4=5(b+1)-1$

$x=4c+3=4(c+1)-1$

$x=3d+2=3(d+1)-1$

therefore x will be of the form $(\text{L.C.M(3,4,5,6)}k-1)$ or,

$x=60k-1$ for some $k$.

Can you guess that $k$?

ANSWER:$k=1$, or $x=59$

$\endgroup$
2
$\begingroup$

The number which leaves (5, 4, 3, 2) mod (6, 5, 4, 3) is one less than the one that leaves a residue of (0, 0, 0, 0), mod (6, 5, 4, 3). So one finds $n=\operatorname{lcm}(6,5,4,3)-1$ to get 59, which is the desired answer.

$\endgroup$
0
$\begingroup$

The problem can be solved by Chinese Remainder Theorem (CRT) or by taking lcm of divisors. Here divisors are 3, 4, 5 and 6; and the 1 must be subtracted? can you guess why we are subtracting 1? Or you can ask me if you need any clarifications.

$\endgroup$

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.