# Thread: Chinese remainder theorem problem

1. ## Chinese remainder theorem problem

Hi - I've come unstuck on a problem as I've not seen the like before:

$\displaystyle x\equiv 1\mod\17$
$\displaystyle x\equiv 8\mod\15$
$\displaystyle x\equiv 3\mod\35$

With out going into too much detail regarding the finer details of solving this I proceeed as moduli are all co-prime as required ( I thought that if this was the case then it is definately solveable!?). However, when looking at the last equation I'm trying to solve:

$\displaystyle 10y\equiv 1\mod\35$

Here 10 and 35 are not co-prime so I cannot have an inverse or therefore solve it. If I rearrange the original equations to redefine $\displaystyle x\equiv 3\mod\35$ I end up with contradictions in the question.

How do I proceed? As mentioned, my understading is if the moduli are co-prime then an answer will always exist.

BR, Felix

2. ## Re: Chinese remainder theorem problem

You "understanding" is not quite correct. If a system of modulus equation has co-prime moduli and each equation has a solution itself, then there exist values satifying all of them.
However, here, because 10 and 35 have common factor, 5, there is NO x such that 10x is one more than a multiple of 35 there is no x satisfying the last equation alone and so cannot be a value of x satisfying all of them.

3. ## Re: Chinese remainder theorem problem

solution must be congruent modulo the$\displaystyle ~\operatorname{lcm} (15,17,35)$

4. ## Re: Chinese remainder theorem problem

Originally Posted by HallsofIvy
You "understanding" is not quite correct. If a system of modulus equation has co-prime moduli and each equation has a solution itself, then there exist values satifying all of them.
However, here, because 10 and 35 have common factor, 5, there is NO x such that 10x is one more than a multiple of 35 there is no x satisfying the last equation alone and so cannot be a value of x satisfying all of them.
solution

5. ## Re: Chinese remainder theorem problem

To be exact, the moduli have to be pairwise co-prime, so CRT doesn't work directly since 15 and 35 are not co-prime. But you can split up the second and third congruences:

$\displaystyle x\equiv{1}\mod{17}$
$\displaystyle x\equiv{2}\mod{3}$
$\displaystyle x\equiv{3}\mod{5}$
$\displaystyle x\equiv{3}\mod{7}$
$\displaystyle x\equiv{3}\mod{5}$

Since $\displaystyle x\equiv{3}\mod{5}$ agrees, you still have solutions. If you got two different congruences, then of course you would have no solutions. So now you have four congruences:

$\displaystyle x\equiv{1}\mod{17}$
$\displaystyle x\equiv{2}\mod{3}$
$\displaystyle x\equiv{3}\mod{5}$
$\displaystyle x\equiv{3}\mod{7}$

You will get a solution of the form $\displaystyle x\equiv{x_0}\mod{N}$ where $\displaystyle N=1785$ is the LCM of the moduli.

The first task is to find $\displaystyle r_i$ and $\displaystyle s_i$ such that $\displaystyle r_im_i+s_i\frac{N}{m_i}=1$. If the numbers were bigger, you would use the extended Euclidean algorithm, but here trial and error should do the job. For example, $\displaystyle -37\cdot{17}+6\cdot{105}=1$. So $\displaystyle 6\cdot{105}=630$ is congruent to 1 (mod 17), 0 (mod 3), 0 (mod 5), and 0 (mod 7).

So you get 4 values for $\displaystyle s_i\frac{N}{m_i}$, multiply them by 1, 2, 3, and 3 and add them together to get the final solution, which will be congruent to the solution from princeps.

- Hollywood