Respuesta :

If you're supposed to solve the congruences one at a time:

1: [tex]2x\equiv5\pmod7[/tex]

First find the inverse of 5 modulo 7. Note that [tex]5\cdot3\equiv15\equiv1\pmod7[/tex], so [tex]5^{-1}\equiv3\pmod7[/tex].

[tex]3\cdot2x\equiv6x\equiv1\pmod7[/tex]

Then find the inverse of 6 modulo 7. Note that [tex]6\cdot6\equiv36\equiv1\pmod7[/tex], so 6 is its own inverse, and we have

[tex]6\cdot6x\equiv x\equiv6\pmod7[/tex]

so the first congruence has solution [tex]x=6+7n[/tex] where [tex]n\in\mathbb Z[/tex].

2: [tex]4x\equiv2\pmod5[/tex]

We have [tex]3\cdot2\equiv6\equiv1\pmod5[/tex], so [tex]2^{-1}\equiv3\pmod5[/tex]. Then

[tex]3\cdot4x\equiv12x\equiv2x\equiv1\pmod5[/tex]

and

[tex]3\cdot2x\equiv x\equiv3\pmod5[/tex]

so the solution is [tex]x=3+5n[/tex] for [tex]n\in\mathbb Z[/tex].

3: [tex]3x\equiv9\pmod{11}[/tex]

[tex]9\cdot5\equiv45\equiv1\pmod{11}[/tex], so [tex]9^{-1}\equiv5\pmod{11}[/tex], and

[tex]5\cdot3x\equiv15x\equiv4x\equiv1\pmod{11}[/tex]

[tex]4\cdot3\equiv12\equiv1\pmod{11}[/tex], so [tex]4^{-1}\equiv3\pmod{11}[/tex] and

[tex]3\cdot4x\equiv x\equiv3\pmod{11}[/tex]

so [tex]x=3+11n[/tex] for [tex]n\in\mathbb Z[/tex].

If they're to be taken simultaneously, use the Chinese remainder theorem.

Combined:

[tex]\begin{cases}x\equiv6\pmod7\\x\equiv3\pmod5\\x\equiv3\pmod{11}\end{cases}[/tex]

Let's start with

[tex]x=5\cdot11+7\cdot11+7\cdot5[/tex]

so that two terms will vanish when considering the remainder of [tex]x[/tex] modulo 7, 5, or 11, respectively.

Taken modulo 7, we have

[tex]x\equiv5\cdot11\equiv55\equiv6\pmod7[/tex]

Taken modulo 5, we have

[tex]x\equiv7\cdot11\equiv77\equiv2\pmod5[/tex]

but we want to end up with 3, so we multiply the second term by the inverse of 2 modulo 5, then by 3. Note that [tex]2\cdot3\equiv1\pmod5[/tex], so our new choice of [tex]x[/tex] is

[tex]x=5\cdot11+7\cdot11\cdot3\cdot3+7\cdot5[/tex]

and taken modulo 5, we end up with a remainder of 3, as desired.

Taken modulo 11, we have

[tex]x\equiv35\equiv2\pmod{11}[/tex]

but we want to end up with 3, so we multiply the third term by the inverse of 2 modulo 11, then by 3. Note that [tex]2\cdot6\equiv1\pmod{11}[/tex], so [tex]x[/tex] becomes

[tex]x=5\cdot11+7\cdot11\cdot3\cdot3+7\cdot5\cdot6\cdot3=1378[/tex]

By the CRT, the least positive solution is

[tex]x\equiv1378\pmod{7\cdot5\cdot11}\implies x\equiv1378\pmod{385}\implies x\equiv223\pmod{385}[/tex]

so the general solution to the system would be [tex]x=223+385n[/tex] for [tex]n\in\mathbb Z[/tex].