How to reduce congruence systems with moduli not coprime?

Essentially you have to figure out congruences that mean kind of the same thing.

For example, if $x \equiv 1 \bmod 108$, then $x \equiv 1 \bmod 3$ as well. However, you don't have to divide $108$ that much, since dividing out the $4$ to get $x \equiv 1 \bmod 27$ is enough to make the first modulus coprime to the other two moduli.

Now you just need to to make the moduli $40$ and $225$ coprime. You could divide the $25$ out of $225$ and then the third modulus is coprime to the second, but not to the first.

Therefore the most straightforward choice at this point is to divide the $5$ out of $40$, and divide the $9$ out of $225$, giving you $8$ and $25$ for the second and third moduli.

But watch out: since $13 > 8$ and $28 > 25$, you need to change those two remainders. Well, technically you don't have to, but some implementations of the algorithm could be thrown off and fail to deliver the correct result, or any result at all.

Thus $x \equiv 13 \bmod 40$ becomes $x \equiv 5 \bmod 8$ (since $13 - 8 = 5$) and $x \equiv 28 \bmod 225$ becomes $x \equiv 3 \bmod 25$ (since $28 - 25 = 3$).

To check your answers in Wolfram Mathematica or Wolfram Alpha: do ChineseRemainder[{1, 13, 28}, {108, 40, 225}] and compare the results to ChineseRemainder[{1, 5, 3}, {27, 8, 25}] (depending on circumstances beyond your control, Wolfram Alpha may fail to give a result when the moduli are not coprime).

$x = 2053$, since $2053 = 19 \times 108 + 1 = 51 \times 40 + 13 = 9 \times 225 + 28$. Also $2053 = 76 \times 27 + 1 = 256 \times 8 + 5 = 82 \times 25 + 3$.

(I just wanted to try that "invisible until hover" text that I see on so many answers on this site).

Reducing is trivial:

If $a \equiv b \mod n$ then $a \equiv b \mod k$ for all $k|n$.

Just think about it......

=======

$x \equiv 1 \mod 108 \implies x= 108k + 1 = 27(4k) + 1 \implies x \equiv 1 \mod 27$.

$x \equiv 13 \mod 40 \implies x = 40k + 13 = 8(5k) + 13 \implies x \equiv 13 \equiv 5 \mod 8$. etc.

=======

It's going the other way that requires (minor) stipulation.

If $a \equiv b \mod k$ then $a \equiv b + ck \mod n$ for any $n$ a multiple of $k$ and $c$ is some integer; (exactly which integer is not necessarily known).

====

So $x \equiv 1 \mod 3^3*2^2$

$x \equiv 13 \mod 2^3*5$

$x \equiv 28 \mod 5^2*3^2$

Pick the largest of the mutually prime factors: $3^3;2^3;5^2$

So

$x \equiv 1 \mod 3^3$

$x \equiv 13\mod 2^3$

$x \equiv 28 \mod 2^5$.

The idea is to use CRT to split the congruences into equivalent congruences to prime powers, then eliminate redundant congruences (shown as up and down arrow implications below)

$\begin{array}{lll} x\equiv1 \pmod{\!2^2\cdot 3^3}\iff &\!\!\!\!\!\!\color{#0a0}{x\equiv1} \pmod{\!2^2}, &\!\!\!\!\!\! x\equiv 1\pmod{\!3^3}\\[-.5em] & \Uparrow & \\[-.3em] x\equiv 13 \pmod{\!2^3\cdot 5}\iff &\!\!\!\!\!\!\color{#c00}{x\equiv 13\equiv5} \pmod{\!2^3}, & \Downarrow&x\equiv 13\equiv3\pmod{\!5}\\[-.5em] & & & \quad \Uparrow\\[-.2em] x\equiv28\pmod{\!3^3\cdot 5^2}\!\iff &&\!\!\!\!\!\!x\equiv28\equiv1\pmod{\!3^2}, &x\equiv 28\equiv 3\pmod{\!5^2} \end{array}$

E.g. note $\,\color{#c00}{x\equiv 5}\pmod{\!2^3}\,\Rightarrow\, \color{#0a0}{x\equiv 5\equiv 1}\pmod{\!2^2},\,$ so the latter is redundant and can be deleted.

Similarly we can delete the implied congruences mod $3^2$ and mod $5,\,$ leaving the said equivalent system of three congruences to prime powers.