1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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


    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


    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...
Similar Threads for Systems linear congruences Date
Energy for Linear 1D Systems - 1D potential Sep 28, 2016
Linear Momentum of system of two blocks Apr 9, 2016
System With Increasing Mass Mar 31, 2016
General question about conservation of momentum Nov 30, 2015
Non-linear system Nov 17, 2014