Question

Using the Chinese Remainder Theorem, solve the congruence
x 15 (mod 42)
x 5 (mod 19)

Answer 1

19 and 42 are coprime, so we can use the CRT right away. Start with

`x=19+42`

Taken mod 42, we're left with a remainder of 19. Notice that

`19\cdot3\equiv57\equiv15\pmod{42}`

so we need to multiply the first term by 3 to get the remainder we want.

`x=19\cdot3+42`

Next, taken mod 19, we're left with a remainder of 4. Notice that

`42\cdot6\equiv252\equiv5\pmod{19}`

so we need to multiply the second term by 6.

Then by the CRT, we have

`x\equiv19\cdot3+42\cdot6\equiv309\pmod{42\cdot19}\implies x\equiv309\pmod{798}`

so that any solution of the form
`x=798n+309` is a solution to this system.