<s>[INST] Number Theory: Mod Simultaneous Congruences I have this problem assigned for homework. I completed it but I wanted to see if there was a simpler way of solving it. Here it is:
Problem: Solve the set of simultaneous congruences:
$2x\equiv 1\pmod{5}$,
$3x\equiv 9\pmod{6}$,
$4x\equiv 1\pmod{7}$,
$5x\equiv 9\pmod{11}$.
Solution:
$2x\equiv 1\equiv 6\pmod{5}\implies x\equiv 3\pmod{5}$
$\implies x=3+5k$, some $k\in \mathbb{Z}$.
$3x\equiv 9\pmod{6}\implies x\equiv 3\pmod{2}\implies3+5k\equiv 3\pmod2\implies 5k\equiv 0\pmod2$
$\implies k\equiv 0\pmod2\implies k=2i$
$\implies x=3+5(2i)=3+10i$, some $i\in \mathbb{Z}$.
$4x\equiv 1\pmod7 \implies 4(3+10i)\equiv 1\equiv 8\pmod7\implies 3+10i\equiv 2\equiv 23\pmod7$
$\implies 10i\equiv 20\pmod7\implies i\equiv 2\pmod7\implies i=2+7j$
$\implies x=3+10(2+7j)=23+70j$, some $j\in \mathbb{Z}$.
$5x\equiv 9\equiv 20\pmod{11}\implies x\equiv 4\pmod{11}\implies 23+70j\equiv 4\equiv 653\pmod{11}$
$\implies 70j\equiv 630\pmod{11}\implies j\equiv 9\pmod{11}\implies j=9+11t$
$\implies x=23+70(9+11t)=653+770t$, some $t\in \mathbb{Z}$.
$\implies x\equiv 653\pmod{770}$.
 [/INST] There is a classic formula to "write down" the solution after solving some auxiliary congruences.  In your case, solve for the following inverses using your favorite algorithm for modular inversion:
$b_1 \equiv (2 \cdot 2 \cdot 7 \cdot 11)^{-1} \mod 5$
$b_2 \equiv (5 \cdot 7 \cdot 11)^{-1} \mod 2$
$b_3 \equiv (4 \cdot 5 \cdot 2 \cdot 11)^{-1} \mod 7$
$b_4 \equiv (5 \cdot 5 \cdot 2 \cdot 7)^{-1} \mod 11$
We find, by inspection, solutions $b_1 = 2$, $b_2 = 1$, $b_3 = 6$, and $b_4 = 5$.
A solution to your system is then
$b_1 \cdot 2 \cdot 7 \cdot 11 + b_2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + b_3 \cdot 5 \cdot 2 \cdot 11 + b_4 \cdot 9 \cdot 5 \cdot 2 \cdot 7$
which, using the above values, is $5273$.  It is easy to see this is congruent to 653 modulo 770.
</s>