0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.