Which ordered pair is a solution to the system of equations?

Solve the following simultaneous linear congruences.

Anastaziya [24]

a. The moduli are coprime, so you can apply the Chinese remainder theorem directly. Let

$x=4\cdot5+3\cdot5+3\cdot4$

Taken mod 3, the last two terms vanish, and $20\equiv2\pmod3$ so we need to multiply by the inverse of 2 modulo 3 to end up with a remainder of 1. Since $2\cdot2\equiv4\equiv1\pmod3$ , we multiply the first term by 2.

$x=4\cdot5\cdot2+3\cdot5+3\cdot4$

Taken mod 4, the first and last terms vanish, and $15\equiv3\pmod4$ . Multiply by the inverse of 3 modulo 4 (which is 3 because $3\cdot3\equiv9\equiv1\pmod4$ ), then by 2 to ensure the proper remainder is left.

$x=4\cdot5\cdot2+3\cdot5\cdot3\cdot2+3\cdot4$

Taken mod 5, the first two terms vanish, and $12\equiv2\pmod5$ . Multiply by the inverse of 2 modulo 5 (3, since $3\cdot2\equiv6\equiv1\pmod5$ ) and again by 3.

$x=4\cdot5\cdot2+3\cdot5\cdot3\cdot2+3\cdot4\cdot3\cdot3$

$\implies x=238$

By the CRT, we have

$x\equiv238\pmod{3\cdot4\cdot5}\implies x\equiv-2\pmod{60}\implies\boxed{x\equiv58\pmod{60}}$

i.e. any number $58+60n$ (where $n$ is an integer) satisifes the system.

b. The moduli are not coprime, so we need to check for possible contradictions. If $x\equiv a\pmod m$ and $x\equiv b\pmod n$ , then we need to have $a\equiv b\pmod{\mathrm{gcd}(m,n)}$ . This basically amounts to checking that if $x\equiv a\pmod m$ , then we should also have $x\equiv a\pmod{\text{any divisor of }m}$ .