Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By johnsomeone
  • 1 Post By johnsomeone

Math Help - congruence modulo 5

  1. #1
    Junior Member
    Joined
    Aug 2012
    From
    us
    Posts
    66

    congruence modulo 5

    Determine the set of integer solutions of the system:
    3x + y + 2z -t =1 (mod 5)
    2x + y + 4z +3t +2w=1 (mod 5)
    x - 2y +3t +w=3 (mod 5)
    x -z -t +3w=1 (mod 5)
    2x + 3y +3z - t -w=1(mod 5)
    in which (mod 5) denotes congruence
    modulo 5.
    I would like to get some help in understanding the answer:"Treat the system as a system of equations
    in which all calculations are done modulo 5. For example, adding the first row
    to the second gives [0 2 1 2 2 2 ] "
    Is there no "direct solution" for
    finding x, y, z ,t,w?
    Thanks in advance for any help you are able to provide...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: congruence modulo 5

    Do everything the same as you would if dealing with real numbers - except for 2 things to be aware of:

    1) You're free to reduce everything modulo 5. If you 4+3, you can replace it by 2. 1+4 = 0. Etc.
    Technically, it's all happening in the equivalence classes of remainders mod 5, and so when you see "12=2 mod 5", it means 12+5\mathbb{Z} = 2+5\mathbb{Z}. For shorthand, bearing that in mind, it's correct to write 12 = 2 mod 5. People often use a different symbol than =, like \equiv or \simeq, to clarify that it's "equal modulo 5". The point, you can add, subtract, and multiply exactly as you would with integers, adding (or subtracting) any multiple of 5 to any value whenever you please.
    2) When seeking to *divide* (say, to get a leading coeficent of 1 if you choose to solve this using matricies), the 5 becomes important - especially that 5 is a prime. Since 5 is a prime, division by non-zero numbers is possible, but will look a little weird.
    First note that "non-zero" here is already a little weird. 10 = 0 modulo 5. 10 = 385 = -90125 = -840 = 0 mod 5.
    For non-zero values, "dividing" means mulitplying by something to get 1. What do you mulitply 3 by to get 1 MODULO FIVE? The answer isn't the rational number 1/3, since modulo 5 only meaningful for integers. The answer is 2, because (2)(3) = 6 = 1 mod 5. Maybe an example makes this clearer:
    Solve: 3x-3 = 4.
    Solution: Add 3 to both sides: 23 = 7. Multiply both sides by (1/3) (meaning of "divide by 3"): (1/3)(3x) = (1/3)(7), so ((1/3)(3))x = 2 1/3, so (1)x = 2 1/3, so x = 2 1/3.
    I strung out how the "divide by 3" part works so that you can compare with how do it modulo 5:
    Now solve: 3x-3 = 4 mod 5.
    Solution: Add 3 to both sides: 3x = 7 mod 5. We can make the numbers smaller (we don't have to, but we can, so I will), since 7 = 2 mod 5. Thus 3x = 2 mod 5.
    Now want to divide by that 3 to solve for x. Which means we need to find "3 inverse mod 5" (written 3^{-1}, or sometimes 3^*, a number that when multiplied by 3 gives 1 modulo 5.
    Again (2)(3) = 1 mod 5, so 3^{-1} = 3^* = 2 \mod 5. Watch how multiplying both sides by 2 has the same effect as "dividing both sides by 3" did in the example above.
    Multiply both sides by 2: (2)(3x) = (2)(2) mod 5, so ((3)(2))x = 4 mod 5, so (1)x = 4 mod 5, so x = 4 mod 5. Check for yourself that x = 4 mod 5 solves the original equation.

    So do it the same, except "dividing by n" is instead done by "mulitplying by n^*". You can check the following yourself:
    0^* = undefined. 1^* = 1, 2^* = 3, 3^* = 2, 4^* = 4.

    Note that doing everything modulo n, where n is not a prime, is more difficult, because there will be non-zero (modulo n) numbers that don't have inverses.
    Ex: Solve 2x = 1 mod 10 (i.e. find "2* mod 10"). There is no solution, so 2* is undefined mod 10. It gets complicated, because then some equations of the form 2x = a mod 10 won't have any solutions (2x = 3 mod 10), but others will (2x = 4 mod 10).
    So the prime case is the simplest - and that's your case with this "mod 5" problem.
    Last edited by johnsomeone; September 17th 2012 at 02:24 PM.
    Thanks from jojo7777777
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2012
    From
    us
    Posts
    66

    Re: congruence modulo 5

    I'm grateful to you for your help.....however, I still have difficulty to solve the matrix according to the rules, I left with a matrix of the form:
    1 2 4 -2 0 |2
    0 1 -2 -4 -4 |1
    0 0 1 3 0 | 0
    0 0 0 0 0 |1
    0 0 0 0 0 |-2
    which is inconsistent, so where did I fail?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: congruence modulo 5

    I can't look at that and check the steps you took. I can say that when I did it quickly, I also got "no solution - inconsistent equations" result. I didn't double check my work, but since you and I agree, I assume that's right.

    Be aware that there's nothing "funny" going on here about the "mod 5" that's causing there to be no solutions. It's simply an inconsistent system of equations (geometrically, parallel lines and such - though the geometric interpretation is a bit strained when working mod 5). The same thing can happen when dealing with systems of equations over the real numbers.
    Ex:
    2x + y - z = 4
    x - 3y + 2z = -1
    4x - 5y + 3z = 1
    Or, even more transparently:
    Ex:
    x - 2y = 3
    x - 2y = 5
    Last edited by johnsomeone; September 19th 2012 at 02:48 PM.
    Thanks from jojo7777777
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2012
    From
    us
    Posts
    66

    Re: congruence modulo 5

    Thank you very much...!!!
    Last edited by jojo7777777; September 20th 2012 at 06:10 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence modulo
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 20th 2012, 06:06 AM
  2. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 26th 2010, 05:10 PM
  3. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 06:47 PM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 07:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 22nd 2007, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum