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

User John Blum
by
8.6k points

1 Answer

4 votes

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.

User Matheusvmbruno
by
7.8k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories