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

System of linear congruences

  1. Dec 16, 2004 #1
    the system:

    24x + 11y= 4 (mod 35)
    5x + 7y= -13 (mod 35)

    is solved to get:

    -113y= 111 (mod 35)
    113x= 171 (mod 35)

    which gives: (17,8).

    should there not be more solutions?
     
  2. jcsd
  3. Dec 16, 2004 #2
    No, with two unknowns, x and y, we need exactly two linear equations to find the unique solution. Now, if x or y was quadratic, it would be different.

    You can see from your own work that, we use one of the equations to eliminate one of the terms. Thus what remains is all in one unknown.

    However, since it is a modulo equation, you can add or subtract any multiple of 35 to x or y.
     
    Last edited: Dec 16, 2004
  4. Dec 16, 2004 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You might want to check your solution by substituting it back into the original equations.
     
  5. Dec 16, 2004 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ask yourself two questions:

    (1) Why do you think there should be more solutions?
    (2) What things do you know about solutions to systems of linear equations?

    When answering these questions, it might help to consider things mod 7 and mod 5, so that you're working over a field (and thus most of what you learned in linear algebra is applicable)
     
  6. Dec 16, 2004 #5
    Oliver$: should there not be more solutions?

    Unfortunately "Yes," since there is a mistake in your value for y.

    It might be easier as Hurkyl suggests to work with modulo 5 and modulo 7.
     
    Last edited: Dec 16, 2004
  7. Dec 20, 2004 #6
    ok, upon doing it (mod 7) and (mod 5), i got (3,4) (mod 7) and (1,2) (mod 7). does that sit well? or should i now apply the CRT?
     
  8. Dec 20, 2004 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You can use the CRT after, but you might want to check your (1,2) answer mod 5 (I assume that's your mod 5 solution).
     
  9. Dec 20, 2004 #8
    sorry, i meant (2,1).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: System of linear congruences
  1. Linear Systems (Replies: 0)

  2. Linear congruence (Replies: 3)

Loading...