# Math Help - Chinese Remainder Theorem

1. ## Chinese Remainder Theorem

I'm finding it hard to get my head around Chinese Remainder Theorem. So wondering if anyone could help with this problem?

Solve the egg problem used to illustrate the Chinese Remainder Theorem if the remainders on division by 2,3,4,5,6 and 7 are all 1 by (i) the given proceduce (ii) the easier way.

I have no idea what the easier way is.

But I have managed to set up the problem for (i) as below:

X=1(Mod2)
X=1(Mod3)
X=1(Mod4) this is ignored as it is the same as the first
X=1(Mod5)
X=1(Mod6)
X=1(Mod7)

Is this correct and if so what is my next step?

2. Originally Posted by LL_5
I'm finding it hard to get my head around Chinese Remainder Theorem. So wondering if anyone could help with this problem?

Solve the egg problem used to illustrate the Chinese Remainder Theorem if the remainders on division by 2,3,4,5,6 and 7 are all 1 by (i) the given proceduce (ii) the easier way.

I have no idea what the easier way is.

But I have managed to set up the problem for (i) as below:

X=1(Mod2)
X=1(Mod3)
X=1(Mod4) this is ignored as it is the same as the first
X=1(Mod5)
X=1(Mod6)
X=1(Mod7)

Is this correct and if so what is my next step?
If $x\equiv a(\bmod N)$ and $x\equiv a(\bmod M)$ and $\gcd(N,M)=1$ then $x\equiv a(\bmod NM)$. We will use this result.

The first congruence can be ignored since $x\equiv 1(\bmod 4)$ implies $x\equiv 1(\bmod 2)$.

The fifth congruence, $x\equiv 1(\bmod 6)$ is equivalent to $x\equiv 1(\bmod 2) \text{ and }x\equiv 1(\bmod 3)$. But these are already true. Thus, this congruence can be ignored also.

We are left with,
$x\equiv 1(\bmod 3)$
$x\equiv 1(\bmod 4)$
$x\equiv 1(\bmod 5)$
$x\equiv 1(\bmod 7)$

This is equivalent to,
$x\equiv 1(\bmod ~ 3\cdot 4\cdot 5\cdot 7)$

3. Thank you for that.

4. What would the 'easier' way be?

Would it be to take one egg away and then find the LCM.

5. Originally Posted by LL_5
What would the 'easier' way be?

Would it be to take one egg away and then find the LCM.
This is the simpliest way. You bring all moduli to the point that each two are pairwise relatively prime. And then apply the theory that was posted above. With this approach all chinese remainder computations are eliminated.