How to reduce congruence systems with moduli not coprime? I'm given a system of congruences and want to apply the Chinese remainder theorem (CRT) on it, but the greatest common divisor (GCD) of the moduli is not $1$.
Well, I need to reduce the system, such that the GCD is $1$, but I don't know how the "reducing" works. I mean I need an explanation.
I found an example, but don't get how they magically transform it from
$$x \equiv 1 \mod 108$$
$$x \equiv 13 \mod 40$$
$$x \equiv 28 \mod 225$$
to
$$x \equiv 1 \mod 27$$
$$x \equiv 5 \mod 8$$
$$x \equiv 3 \mod 25$$
I see that 
$$108 = 2^2 \times 3^3$$
$$ 40 =5 \times 2^3$$
$$225=3^2 \times 5^2$$
but not sure when and how they used it... thanks for the help! 

The key idea is to use $\,\rm \color{darkorange} C\!=$ CRT to split the congruences into equivalent congruences to prime powers, then eliminate redundant congruences (shown as up and down arrow implications below), e.g. note:  $\, \color{#c00}{x\equiv 5\pmod{\!2^3}}\ \Rightarrow\ \color{grey}{x\equiv 1\pmod{\!2^2}},\,$ so the latter is redundant and can be deleted.
$\!\begin{array}{lll} x\,\equiv\,1 \pmod{\!\color{grey}{2^2}\cdot \color{#0a0}{3^3}}\!\!\!\!\overset{\color{darkorange}{\rm C}\!\!}\iff &\!\!\!\!\!\!\color{grey}{x\equiv1 \pmod{\!2^2}}, &\!\!\!\!\!\ \color{#0a0}{x\equiv 1\pmod{\!3^3}}\\[-0.5em]
 &\! \Uparrow & \ \:\!{||}\\[-1em]
 x\equiv 13 \pmod{\!\color{#c00}{2^3}\cdot 5}\smash[t]{\overset{\color{darkorange}{\rm C}\!\!}\iff} &\!\!\!\!\!\!\color{#c00}{x\equiv 5 \pmod{\!2^3}}, \rlap{\ .\ .}&\:\! \ \raise 0.03em{||}\ .\ .\ .\ .\ .\ .\ .\ . &\!\!\! x\equiv 3\pmod{\!5}\\[-.5em]
& & \,\:\!\large \raise 0.1em{\Downarrow} & \,\,\:\!\Uparrow\\[-.2em]
x\equiv28\pmod{\!3^2\cdot \color{#90f}{5^2}}\!\smash{\overset{\color{darkorange}{\rm C}}\iff}&\!\!\!\!\!. \ .\ .\ .\ .\ .\ .\ .\ .\ .&\!\!\!\!x\equiv1\pmod{\!3^2}, &\!\!\!\color{#90f}{x\equiv 3\pmod{\!5^2}}
\end{array}$
Similarly, deleting congruences implied by $\!\color{#0a0}{\bmod 3^3}\,$ & $\color{#90f}{\bmod 5^2}\,$ leaves the equivalent system
$$\begin{align} 
&\color{#c00}{x\equiv 5\!\!\pmod{2^3}}\\ 
&\color{#0a0}{x\equiv 1\!\!\pmod{3^3}}\\ 
&\color{#90f}{x\equiv 3\!\!\pmod{5^2}}
\end{align}\qquad\qquad$$
Since the moduli are now pairwise coprime we can now apply CRT to solve it.
The above implications are a special case of: congruences persist mod factors of the modulus (above the factor(izations) have special form $\,p^k\mid p^{k+n},\,$ since the moduli are prime powers).
