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: Solving linear system of congruences

  1. Jul 2, 2012 #1
    1. The problem statement, all variables and given/known data
    Solver for n and m in the following equations:
    2n + 6m [itex]\equiv[/itex] 2 (mod 10)
    n + m [itex]\equiv[/itex] -2 (mod 10)

    2. Relevant equations

    3. The attempt at a solution
    I've worked through several of these problems prior, including ones in the book and most take the form:
    2n + 3m = 3 (mod 10)
    n + 3m = -2 (mod 10)
    or something similar, where it is easy to subtract one equation from the other and solve for one variable, then plug back in and solve for the other. Or cases where it's easy to multiply and then subtract. In this case though, my textbook explicitly says you cannot multiply the equation by a number that's not relatively prime with the modulus, so I'm at a loss for how to cancel out a variable to solve these equations. This multiplying / subtracting or adding method is all we've been shown. I would greatly appreciate some advice on how to approach the problem!
  2. jcsd
  3. Jul 2, 2012 #2


    Staff: Mentor

    It's been many years since I took a number theory class, so I might be offbase here.
    What about dividing the first equation by 2? That's the same as multiplying by 1/2, which would seem to be relatively prime to 10.
  4. Jul 2, 2012 #3
    We actually went over an example like that in class where we showed at if:
    ac = bc (mod n) and the gcd(a,n) = 1, then a = b (= meaning congruent)
    otherwise it's not valid.
    Correct me if I'm wrong, but in this case c would be 2 and n would be 10, and since those are not relatively prime you can't divide it. I could be way out in left field here, this is just the first one of these questions I'm totally stumped on..
  5. Jul 2, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    Well, I haven't done these for a while either, but 2n+6m=2 (mod 10) does mean that either n+3m=1 (mod 10) or n+3m=6 (mod 10). Doesn't it? How about splitting it into cases?
    Last edited: Jul 3, 2012
  6. Jul 3, 2012 #5
    I apologize if this is a dumb question, but how do you get the second case?
    I'm still struggling with this, I know there obviously are solutions because just looking at at n = m = 4 is one possible solution.
  7. Jul 3, 2012 #6


    User Avatar
    Science Advisor
    Homework Helper

    That's ok. 2k=2 (mod 10) has two solutions. k=1 and k=6. 2*6=2 (mod 10). 2 doesn't have an inverse mod 10. But if you know 2k=2 (mod 10) you do know something about k.
  8. Jul 3, 2012 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Try adding the equations together.

    [itex]2n+6m\equiv2(\mod 10)[/itex]

    [itex]n+m\equiv-2(\mod 10)[/itex]

    Resulting congruence: [itex]3n+7m\equiv-6(\mod 10)[/itex]

    Multiply that result by 3.

    Add that and [itex]n+m\equiv-2(\mod 10)\ .[/itex]
  9. Jul 3, 2012 #8
    Thanks for the replies everyone! SammyS, I wasn't sure if that was valid to do, but it seems to give me correct solutions. One note: adding the two gives 3n + 7m = 0 (mod 10). But solving using that equation as you proposed gave me the solutions n = m = 4 and n = m = 9, I'm not sure if you solved it and could tell me if that's all the solutions? Thank you everyone for your help!
  10. Jul 3, 2012 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Of course it's valid. If 2n + 3m ≣ 3 (mod 10) and n + 3m ≣ -2 (mod 10), then 3n + 7m ≣ 0 (mod 10).

    Take 3n + 7m ≣ 0 (mod 10). Either multiply it by 3 giving 9n + 21m ≣ 0 (mod 10) which is equivalent to -1n + 1m ≣ 0 (mod 10). That can be added to (or subtracted from) n + m ≡ -2 (mod 10)

    Otherwise, multiply n + m ≡ -2 (mod 10) by -3 and add that to 3n + 7m ≣ 0 (mod 10) .

    Yes, I get m, n = 4, or m, n = 9 .
  11. Jul 5, 2012 #10
    You can also divide

    [itex]2n + 6m \equiv 2( mod\ 10)[/itex]

    by 2 on both sides to get

    [itex]n + 3m \equiv 1( mod\ 5)[/itex]

    [itex]n + m \equiv -2 (mod\ 10)[/itex]
    [itex]\implies n + m \equiv 8 (mod\ 10)[/itex]
    [itex]\implies n + m \equiv 3 (mod\ 5)[/itex]

    Now solving the mod 5 congruences, gives

    [itex] m \equiv 4 (mod\ 5)[/itex]
    which means 2 solutions mod 10, 4 and 9.
    similarly for n.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook