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

Printable View

• 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)

need elaborate and quick answers please
• 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 $\displaystyle x$ that satisfy the following system of congruences:

. . $\displaystyle \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: $\displaystyle 20 = 2^2\cdot 5, 209 = 11\cdot 19, 21 = 3\cdot 7$ Then, consider $\displaystyle 9x$ mod 4 and mod 5 (this will allow you to easily calculate $\displaystyle x$ mod 4 and mod 5). Then consider $\displaystyle 52x$ mod 11 and mod 19 to calculate $\displaystyle x$ mod 11 and mod 19. Finally, consider $\displaystyle 8x$ mod 3 and mod 7 to calculate $\displaystyle x$ mod 3 and mod 7. Once you know $\displaystyle x$ mod 4, 5, 11, 19, 3, and 7, use the Chinese Remainder Theorem to find $\displaystyle x$ mod $\displaystyle 4\cdot 5\cdot 11\cdot 19\cdot 3\cdot 7 = 87780$.