# Find all integers x that satisfy the following system of congruences:

• Oct 1st 2013, 08:01 AM
virebbala90
Find all integers x that satisfy the following system of congruences:
Find all integers x that satisfy the following system of congruences:
9x≡1(mod 20) ; 52x≡2 (mod 209) ; 8x≡(mod 21)

• Oct 1st 2013, 09:52 AM
Soroban
Re: Find all integers x that satisfy the following system of congruences:
Hello, virebbala90!

There is an omission . . .

Quote:

Find all integers $x$ that satisfy the following system of congruences:

. . $\begin{array}{cccc}9x &\equiv& 1& \text{(mod 20)} \\ 52x &\equiv& 2 & \text{(mod 209)} \\ 8x &\equiv& {\color{red}?} & \text{(mod 21)} \end{array}$

• Oct 1st 2013, 11:40 AM
SlipEternal
Re: Find all integers x that satisfy the following system of congruences:
First, find the prime factorization for each: $20 = 2^2\cdot 5, 209 = 11\cdot 19, 21 = 3\cdot 7$ Then, consider $9x$ mod 4 and mod 5 (this will allow you to easily calculate $x$ mod 4 and mod 5). Then consider $52x$ mod 11 and mod 19 to calculate $x$ mod 11 and mod 19. Finally, consider $8x$ mod 3 and mod 7 to calculate $x$ mod 3 and mod 7. Once you know $x$ mod 4, 5, 11, 19, 3, and 7, use the Chinese Remainder Theorem to find $x$ mod $4\cdot 5\cdot 11\cdot 19\cdot 3\cdot 7 = 87780$.