systems of linear congruences


by oliver$
Tags: congruences, linear, systems
oliver$
oliver$ is offline
#1
Dec16-04, 07:08 PM
P: 6
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?
Phys.Org News Partner Science news on Phys.org
Simplicity is key to co-operative robots
Chemical vapor deposition used to grow atomic layer materials on top of each other
Earliest ancestor of land herbivores discovered
dextercioby
dextercioby is offline
#2
Dec16-04, 10:50 PM
Sci Advisor
HW Helper
P: 11,863
Quote Quote by 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?

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

Daniel.
oliver$
oliver$ is offline
#3
Dec18-04, 06:05 PM
P: 6
i got x== 2(mod 35).

oliver$
oliver$ is offline
#4
Dec18-04, 06:11 PM
P: 6

systems of linear congruences


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
dextercioby is offline
#5
Dec18-04, 06:49 PM
Sci Advisor
HW Helper
P: 11,863
Quote Quote by oliver$
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 wanna 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
[tex] x=35c+12 [/tex](7)
,where "c" can take only positive odd values (eq.(5)/(6)).
So [tex] x\in\{47,117,187,...\}[/tex]

Daniel.

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


Register to reply

Related Discussions
Formal series solutions to systems of linear or non-linear DEs (Cauchy problem) General Physics 0
Using Linear Algebra to solve systems of non-linear equations Calculus 9
System of linear congruences... Help, please! Linear & Abstract Algebra 1
system of linear congruences Linear & Abstract Algebra 7
Solving linear congruences General Math 1