Results 1 to 4 of 4

Math Help - Trouble solving a system of linear congruences.

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    4

    Question Trouble solving a system of linear congruences.

    Hi all,

    I have three related linear congruences, described below, and I'm trying to solve for x and y.

    224x + 225y = 226 (mod 228)
    3x + 6y = 153 (mod 228)
    0x + 226y = 132 (mod 228)

    The trouble I'm having is that these can have multiple solutions and I don't know of a good way to determine which ones to use without calculating all of them.

    For example, 226y = 132 (mod 228) has two solutions, y=48 and y=162.

    The second equation (3x + 6y = 153 mod 228) will have three solutions for x regardless of which of the values for y is chosen (x=31, x=107, x=183). However, the first equation (224x + 225y = 226 mod 228) has no solution for x when y=48 and has 4 solutions when y=162 (x=50, x=107, x=164, x=221).

    After having calculated all of the combinations, I can tell by looking at it that y=162 (because y=48 doesn't solve the first congruence) and that x=107 (because it is common in the solutions for both the first and second congruence.

    Is there a formula I can apply to determine which solutions to use for any particular congruence, given the related congruences? Maybe some way to calculate them all simultaneously? While calculating solutions for all of the combinations worked out in this case, I don't think it is practical when the number of unknowns increases. I started with five unknowns across six congruences but used matrix reduction to get it down to this.

    I'm a computer science major without a very strong number theory background and I'm not even sure what to call the problem I'm trying to solve, which makes it difficult to search for on the internet (though I've tried) or to find what sections of math books might be related (though I've scoured the local book stores). Any help would be appreciated.


    Thank you for your time,
    m
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    913
    Thanks
    205
    The congruence ax\equiv{b}\ (\text{mod}\ m) has a solution if and only if d=gcd(a,m) divides b. The solution is given by x\equiv{x_0}\ \left(\text{mod}\ \frac{m}{d}\right). That much I know. And I see you have put the system into upper triangular form, which is probably a good idea.

    One idea is to break the modulus down to powers of primes (in your case 228=4*3*19) and solve for each modulus, then use the Chinese Remainder Theorem to get the final solution. I haven't worked out what happens for your system.

    I would just work backward through the equations (as you did):

    226y\equiv{132}\ (\text{mod}\ 228)

    y\equiv{48}\ (\text{mod}\ 114), since gcd(226,228)=2. Or,

    y\equiv{48}+114z\ (\text{mod}\ 228) where z=0 or 1. Now the next equation up:

    3x+6y\equiv{153}\ (\text{mod}\ 228)

    3x+6(48+114z)\equiv{153}\ (\text{mod}\ 228)

    3x+60\equiv{153}\ (\text{mod}\ 228) (z dropped out of the equation, otherwise we would treat it like a constant)

    x\equiv{31}+76w\ (\text{mod}\ 228) where w=0,1, or 2. So that gives us six solutions. But there is another equation:

    224x+225y\equiv{226}\ (\text{mod}\ 228) Since gcd(224,228)=4 and gcd(225,228)=1, substitute for y:

    224x+225(48+114z)\equiv{226}\ (\text{mod}\ 228)

    224x+84+114z\equiv{226}\ (\text{mod}\ 228)

    224x\equiv{142}-114z\ (\text{mod}\ 228) and since gcd(224,228)=4 must divide 142-114z, we must have z=1.

    224x\equiv{28}\ (\text{mod}\ 228) Now substitute for x:

    224(31+76w)\equiv{28}\ (\text{mod}\ 228)

    104+152w\equiv{28}\ (\text{mod}\ 228) and only w=1 works. So only the solution z=1, w=1 is valid, so the solution is:

    x\equiv{107}\ (\text{mod}\ 228)
    y\equiv{162}\ (\text{mod}\ 228)

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2010
    Posts
    913
    Thanks
    205
    It does work to break down the modulus into powers of primes and solve 3 systems of congruences:

    224x + 225y = 226 (mod 228)
    3x + 6y = 153 (mod 228)
    0x + 226y = 132 (mod 228)

    The three systems are:

    0x + 1y = 2 (mod 4)
    3x + 2y = 1 (mod 4)
    0x + 2y = 0 (mod 4)
    solution: x=3, y=2 (mod 4)

    2x + 0y = 1 (mod 3)
    0x + 0y = 0 (mod 3)
    0x + 1y = 0 (mod 3)
    solution: x=2, y=0 (mod 3)

    15x + 16y = 17 (mod 19)
    3x + 6y = 1 (mod 19)
    0x + 17y = 18 (mod 19)
    solution: x=12, y=10 (mod 19)

    And applying the CRT gives the solution.

    - Hollywood
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2010
    Posts
    4

    Thanks Hollywood, I hadn't considered CRT.

    Thanks Hollywood for spotting that.

    I was looking into calculating an inverse matrix and using that to coordinate the different congruences, but I was worried because not all matrices have an inverse. I'll try coding your method up and seeing if there are any cases in which it does not work.

    Thanks again,
    m
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 14th 2011, 10:30 AM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  3. Trouble learning how to manipulate congruences
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 6th 2010, 05:34 PM
  4. Solving linear congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 12th 2010, 10:46 PM
  5. Solving linear system under Z_p
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 20th 2007, 08:43 AM

Search Tags


/mathhelpforum @mathhelpforum