Using the Chinese Remainder Theorem to Solve Systems of Linear Congruences

[oliver$]

ok, am i doing this right?

here's the system:

3x== 1 (mod 10)
4x== 3 (mod 5)
3x== 1 (mod 35)

(3,10), (4,5), (3,35) all are 1.

it reduces to:

x== -3 (mod 10)
x== 12 (mod 35)
x== 4 (mod 5)

and then i use the CRT to solve this system? is that right?

 

[dextercioby]

ok, am i doing this right?
here's the system:
3x== 1 (mod 10)
4x== 3 (mod 5)
3x== 1 (mod 35)
(3,10), (4,5), (3,35) all are 1.
it reduces to:
x== -3 (mod 10)
x== 12 (mod 35)
x== 4 (mod 5)
and then i use the CRT to solve this system? is that right?

I found x=47.What did u find??

Daniel.

 

[oliver$]

i got x== 2(mod 35).

 

[oliver$]

ok, so from
x== 7 (mod 10)
x== 2 (mod 5)
x== 12 (mod 35)

i got:
7 + 10t== 12 (mod 35), which reduces
10t==5 (mod 35)
(10, 35)= 5
10r + 35s = 5
r=-3, s= 1
(-3)(5)/5 = -5
t= -5 (mod 7)== 2 (mod 7)
t= 2 + 7l == 2 (mod 5)
7l== 0 (mod 5)
(7,5)= 1
7r + 5s=0
r=0 s=0
x= 0 (mod 5)
l=5m
x= 7 (5m) +2= 35m +2
or x== 2 (mod 35)

 

[dextercioby]

ok, so from
x== 7 (mod 10)
x== 2 (mod 5)
x== 12 (mod 35)

Here's how i see it:
x==7(mod 10)=>x=10a+7,a={0,1,...}(1)
x==2(mod 5)=>x=5b+2,b={0,1,...}(2)
x==12(mod 35)=>x=35c+12,c={0,1,...}(3)

You want to find "x" and hence "a","b","c".
From (1) and (2)=>b=2a+1,a={0,1,...}(4)
From (1) and (3)=>a=(7c+1)/2,c={1,3,5,...}(5)
From (4) and (5)=>b=7c+2,c={1,3,5,...}(6)
From (3),(5) and (6) u can write the solution to the problem
$$x=35c+12$$(7)
,where "c" can take only positive odd values (eq.(5)/(6)).
So $$x\in\{47,117,187,...\}$$

Daniel.

PS.I solved the problem in the positive numbers set,for the set of integers it can be generalized straightforwardly.