Systems of linear congruences

  1. 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?
     
  2. jcsd
  3. dextercioby

    dextercioby 12,317
    Science Advisor
    Homework Helper


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

    Daniel.
     
  4. i got x== 2(mod 35).
     
  5. 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)
     
  6. dextercioby

    dextercioby 12,317
    Science Advisor
    Homework Helper


    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.
     
    Last edited: Dec 18, 2004
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?