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.