# Solve a system of two congruences with modules not pairwise coprime

I have the following system of congruences:

$\left \{ \begin{array}{rcl} x & \equiv & 225 & \mbox{ (mod 250) } \\ x & \equiv & 150 & \mbox{ (mod 1225) } \end{array} \right .$

Since $\gcd(250, 1225) \ne 1$ the Chinese Remainder Theorem is not applicable.

I have tried to calculate the prime factors of both $250$ and $1225$ and I rewritten the system like this and try to obtain modules pairwise coprime:

$250 = 2 \cdot 5 \cdot 5 \cdot 5 \\ 1225 = 5 \cdot 5 \cdot 7 \cdot 7$

$\left \{ \begin{array}{rcl} x & \equiv & 225 & \mbox{ (mod 2) } \\ x & \equiv & 225 & \mbox{ (mod 5) } \\ x & \equiv & 225 & \mbox{ (mod 5) } \\ x & \equiv & 225 & \mbox{ (mod 5) } \\ x & \equiv & 150 & \mbox{ (mod 5) } \\ x & \equiv & 150 & \mbox{ (mod 5) } \\ x & \equiv & 150 & \mbox{ (mod 7) } \\ x & \equiv & 150 & \mbox{ (mod 7) } \end{array} \right .$

since
$x \equiv 225 \mbox{ (mod 5) } \iff x \equiv 0 \mbox{ (mod 5) }$ and the same for
$x \equiv 150 \mbox{ (mod 5) } \iff x \equiv 0 \mbox{ (mod 5) }$

I have reduced the system as the following:

$\left \{ \begin{array}{rcl} x & \equiv & 1 & \mbox{ (mod 2) } \\ x & \equiv & 3 & \mbox{ (mod 7) } \end{array} \right .$

and I have applied the Chinese Remainder Theorem:

$M = 2 \cdot 7 = 14 \\ M_1 = \frac{14}{2} = 7 \\ M_2 = \frac{14}{7} = 2$

the auxiliary system is:

$\left \{ \begin{array}{rcl} 7x & \equiv & 1 & \mbox{ (mod 2) } \\ 2x & \equiv & 1 & \mbox{ (mod 7) } \end{array} \right . \iff \left \{ \begin{array}{rcl} x & \equiv & 1 & \mbox{ (mod 2) } \\ x & \equiv & 4 & \mbox{ (mod 7) } \end{array} \right .$

$x = 7 \cdot 1 \cdot 1 + 2 \cdot 4 \cdot 3 = 31 \equiv 3 \mbox{ (mod 14) }$

Another way I tried is to consider this equation, but I don't know how to proceed:

$225 + 250h = 150 + 1225k$

Please, can you give me any suggestions? Many thanks!

$x \equiv 225 \pmod {250}$ so $x=25(9+10j)$ for some $j \in \mathbb{Z}$. $x \equiv 150 \pmod {1225}$ so $x=25(6+49k)$ for some $k \in \mathbb{Z}$. So we need to find $y$ satisfying \begin{eqnarray*} y \equiv 9 \pmod {10} \\ y \equiv 6 \pmod {49} \end{eqnarray*} $10$ and $49$ are coprime so we can use the Chinese remainder theorem. We have $y=349$ and $x=8725$.