<s>[INST] Solve the system of conguruences: $x = 2 \bmod7, x = 5 \bmod12, x = 8 \bmod 25$ Question:
Solve the system of conguruences: $x = 2 \bmod7, x = 5 \bmod12, x = 8 \bmod 25$
So far I have
The solution:  $X= B_1X_1C_1 + B_2X_2C_2 + B_3X_3C_3$ and that the answer is -something- $\mod2100$
where
$B_1 = 300, B_2 = 175, B_3 = 84$
and
$C_1=2, C_2=5, C_3=8$
and
$300\times X_1 = 1 \mod7 \Rightarrow 6\times X_1 = 1 \mod7$
$175\times X_2 = 1 \mod12 \Rightarrow 7\times X_2 = 1 \mod12$
$84\times X_3 = 1 \mod25 \Rightarrow 9\times X_3 = 1 \mod25$
When I attempt to solve these for $X_1$, $X_2$ and $X_3$, the solution $X$ is either a lot bigger than 2100 or a negative number...
 [/INST] Let us first begin by trying to reduce this to a system of two congruencies.
Focus our attention first to the following two:
$\begin{cases} x\equiv 2\pmod{7}\\ x\equiv 5\pmod{12}\end{cases}$
We know that $\gcd(7,12)=1$ and so there should be some $a,b$ such that $7a+12b=1$.  We can find the $a$ and $b$ necessary as a byproduct of running the Euclidean Division Algorithm:
$\begin{array}{c|c|c}
12&1&0\\
\hline
7&0&1\\
\hline
5&1&-1\\
\hline
2&-1&2\\
\hline
1&3&-5\end{array}$
Implying that $3\cdot 12 + (-5)\cdot 7 = 1$  (indeed, $36-35=1$)
Note that this implies that $3\cdot 12 \equiv 1\pmod{7}$ and that $(-5)\cdot 7\equiv 1\pmod{12}$
Now, we can use this information to get:
$x\equiv 2\cdot 12\cdot 3 + 5\cdot (-5)\cdot 7\pmod{84}$
simplifying to
$x\equiv -103\equiv 65\pmod{84}$
(check: $65+84n\equiv 2\pmod{7}$ and $65+84n\equiv 5\pmod{12}$)

Continue the problem by combining the new congruence with the remaining congruence:
$\begin{cases}x\equiv 65\pmod{84}\\
x\equiv 8\pmod{25}\end{cases}$
It will combine to give you a solution to $x\equiv y\pmod{2100}$
Begin by noting that $14\cdot 84 -47\cdot 25 = 1$
</s>