# Solve the system of congruences (CRT)

$$560x \equiv 1 \pmod{3, 11, 13}$$

I found a few (by trial and error)

$560x \equiv 1 \pmod{13} \implies x = 1 + 13k$.

$560x \equiv 1 \pmod{3} \implies x = 2 + 3k$.

$560x \equiv 1 \pmod{11}$ Is the hard congruence.

I am trying to use Euclid;s algorithm,

$560 = 50(11) + 10$ and $11 = 1(10) + 1 \implies 1 = 11 - 10$

$$\implies 1 = 11 - (560 - 50(11))$$

But how do I proceed with Euclid's algorithm? the actual answer is: $x = 10 + 11k$ (wolframalpha) so

$x \equiv 1 \pmod{13}$

$x \equiv 2 \pmod{3}$

$x \equiv 10 \pmod{11}$.

then by the chinese remainder theorem there is one solution $\pmod{429}$. But how should I solve it?

• Hint: the last two congruences can be rewritten as $x\equiv-1$ modulo both 3 and 11. Hence they are both solved when $x\equiv-1\;mod(33)$. – lulu Aug 8 '15 at 16:00

The general strategy for any system of congruence equations

$x \equiv r_1 \pmod{n_1}$

$\vdots$

$x \equiv r_k \pmod{n_k}$

where $n_1, \cdots n_k$ are pairwise coprime, is to first find a $k$-tuple $(a_1, \cdots , a_k)$ such that

$a_1 \equiv 1 \pmod{n_1}, \quad a_1 \equiv 0 \pmod{n_1^{\prime}}$

$\vdots$

$a_k \equiv 1 \pmod{n_k}, \quad a_k \equiv 0 \pmod{n_k^{\prime}}$

where $n_i^{\prime} = \prod_{j \neq i} n_j$. This is easy to do. Since $n_i$ and $n_i^{\prime}$ are coprime, we can use the extended Euclid's algorithm to find $p$ and $q$ such that $1 = pn_i + qn_i^{\prime}$. Now set $a_i = 1 - pn_i = qn_i^{\prime}$. The required solution is $x=r_1a_1 + \cdots + r_ka_k$.

In this case, using the hint in the comments, the system becomes

$x \equiv 1 \pmod{13}$

$x \equiv -1 \pmod{33}$

Now, $1 = - 65 + 66$, and therefore our $a_1 =66$ and $a_2 = -65$. The final answer is $1\cdot 66 + -1 \cdot -65 = 131$.