Thread: Where's my mistake?! (Chinese Remainder Theorem)

1. Where's my mistake?! (Chinese Remainder Theorem)

All '=' mean 'congruent to'

P1: 3x=5(mod2) --> x=1(mod2)
P2: 5x=4(mod3) --> x=2(mod3)
P3: 2x=1(mod5) --> x=3(mod5)
P4: 5x=6(mod7) --> x=4(mod7)

M1 is 210/2 = 105
M2 is 210/3 = 70
M3 is 210/5 = 42
M4 is 210/7 = 30

Therefore,
105*Y1=1(mod2) --> Y1=1(mod2)
70*Y2=2(mod3) --> Y2=2(mod3)
42*Y3=3(mod5) --> Y3=4(mod5)
30*Y4=4(mod7) --> Y4=2(mod7)

x equals 1*105*1 + 2*70*2 + 3*42*4 + 4*30*2 --> 1129

x=1129(mod210)
x=79(mod210)

Check:
Works for P1 and P2, but fails for P3 and P4.

Where'd I go wrong?!

2. Originally Posted by AgentNXP
Therefore,
105*Y1=1(mod2) --> Y1=1(mod2)
70*Y2=2(mod3) --> Y2=2(mod3)
42*Y3=3(mod5) --> Y3=4(mod5)
30*Y4=4(mod7) --> Y4=2(mod7)
..should be..

105*Y1=1(mod2) --> Y1=1(mod2)
70*Y2=1(mod3) --> Y2=1(mod3)
42*Y3=1(mod5) --> Y3=3(mod5)
30*Y4=1(mod7) --> Y4=4(mod7)

and corrections consequently follow..

Correct? Yes/No?

... I tried it out, and this doesnt work. Is there another mistake? or am I doing this completely wrong?

3. Originally Posted by AgentNXP
P1: 3x=5(mod2) --> x=1(mod2)
P2: 5x=4(mod3) --> x=2(mod3)
P3: 2x=1(mod5) --> x=3(mod5)
P4: 5x=6(mod7) --> x=4(mod7)
Here's how I solve it:

(For integers a, b, c, and d)

$\displaystyle x \equiv 1 \mod 2 \Rightarrow x = 2a+1$, so
$\displaystyle 2a + 1 \equiv 2 \mod 3 \Rightarrow a = 3b+2 \Rightarrow x = 2(3b+2)+1 = 6b+5$, so
$\displaystyle 6b+5 \equiv 3 \mod 5 \Rightarrow b = 5c + 3 \Rightarrow x = 6(5c+3)+5 = 30c+23$, so
$\displaystyle 30c+23 \equiv 4 \mod 7 \Rightarrow c = 7d + 1 \Rightarrow x = 30(7d+1)+23 = 210d + 53$.

So $\displaystyle x \equiv 53 \mod 210$.