Respuesta :

We want an integer [tex]x[/tex] such that

[tex]x\equiv\begin{cases}2&\pmod3\\0&\pmod4\\2&\pmod5\end{cases}[/tex]

Note that the moduli are all relatively prime, so we can use the Chinese remainder theorem right away. As a first step, let's suppose

[tex]x=4\cdot5\cdot2+3\cdot5\cdot0+3\cdot4\cdot2[/tex]

Taken modulo 3, the last two terms immediately vanish, and [tex]4\cdot5\cdot2=40\equiv1\pmod3[/tex]. We want a remainder of 2, so we just multiply this term by 2.

[tex]x=4\cdot5\cdot2^2+3\cdot5\cdot0+3\cdot4\cdot2[/tex]

Next, taken modulo 4, all terms vanish, so we're good here.
Then, taken modulo 5, the first two terms vanish and we're left with [tex]3\cdot4\cdot2\equiv24\equiv4\pmod5[/tex]. We want a remainder of 2. To rectify this, we can first multiply this term by the inverse of 4 modulo 5, then multiply again by 2. This guarantees that


[tex]3\cdot(4\cdot4^{-1})\cdot2^2\equiv2\pmod5[/tex]

The inverse of 4 modulo 5 is 4, since [tex]4^2\equiv16\equiv1\pmod5[/tex], so we end up with

[tex]x=4\cdot5\cdot2^2+3\cdot5\cdot0+3\cdot4^2\cdot2^2=272[/tex]

You can confirm for yourself that 272 satisfies the desired conditions. The CRT says that any integer of the form


[tex]272\pmod{3\cdot4\cdot5}\equiv32\pmod60[/tex]

will work, i.e. [tex]32+60n[/tex] where [tex]n\in\mathbb Z[/tex], and in particular 32 is the smallest positive solution.
Q&A Education