Chinese remainder theorem problem

**FelixHelix** · March 31st 2012, 06:19 AM

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

$x\equiv 1\mod\17$
$x\equiv 8\mod\15$
$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:

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

Your help would be greatly received.

BR, Felix

**HallsofIvy** · March 31st 2012, 07:43 AM

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.

**princeps** · March 31st 2012, 07:47 AM

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

**princeps** · March 31st 2012, 07:49 AM

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

**hollywood** · April 1st 2012, 07:03 AM

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:

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

Since $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:

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

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

The first task is to find $r_i$ and $s_i$ such that $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, $-37\cdot{17}+6\cdot{105}=1$ . So $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 $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

Thread: Chinese remainder theorem problem

LinkBack

Thread Tools

Display

Chinese remainder theorem problem

Re: Chinese remainder theorem problem

Re: Chinese remainder theorem problem

Re: Chinese remainder theorem problem

Re: Chinese remainder theorem problem

Similar Math Help Forum Discussions

Basic Chinese Remainder Theorem Problem

Chinese Remainder Theorem

Chinese Remainder Theorem Problem

Chinese Remainder Theorem

CRT(chinese remainder theorem)

Search Tags