Register to reply

Systems of linear congruences

by oliver$
Tags: congruences, linear, systems
Share this thread:
oliver$
#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
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
dextercioby
#2
Dec16-04, 10:50 PM
Sci Advisor
HW Helper
P: 11,893
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$
#3
Dec18-04, 06:05 PM
P: 6
i got x== 2(mod 35).

oliver$
#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
#5
Dec18-04, 06:49 PM
Sci Advisor
HW Helper
P: 11,893
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