Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Systems of linear congruences

  1. Dec 16, 2004 #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. Dec 16, 2004 #2

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper
    Insights Author


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

    Daniel.
     
  4. Dec 18, 2004 #3
    i got x== 2(mod 35).
     
  5. Dec 18, 2004 #4
    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. Dec 18, 2004 #5

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper
    Insights Author


    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 this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Systems of linear congruences
  1. Linearize this system (Replies: 1)

  2. Non-linear system (Replies: 2)

Loading...