Results 1 to 4 of 4

Math Help - equations involving modulo

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    2

    Question equations involving modulo

    Hi,
    I need help on solving equation system witch involves modulo.
    My equation looks like this:
    a11x1+a12x2+a13 mod 10 = a14
    a21x1+a22x2+a23 mod 10 = a24

    It would be pretty simple if there where no mod operation, but now i've no idea how to solve it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    You can always just solve it as you would without the modulo, then transfer your answers into modulo notation (e.g. 1/3 = 7 mod 10 because 7*3=1 mod 10).

    Or, you can try and use the modulo at the same time.

    For example, I have the following two equations. They have solutions x=11, y=12 (so mod 10 x=1 and y=2),

    2x-y=9,
    x+y-9=15.

    These become,

    2x-y=-1\text{ mod }10,
    x+y+1=5\text{ mod }10 \Rightarrow x+y=4 \text{ mod }10.

    Add them, to get,

    3x=3 \text{ mod }10.

    We now have the question `what is x'? In this case, it is obviously 1. However, it won't always be so simple. For example, if 3x=8 mod 10, how would you proceed?

    Well, 3*7=21=1 mod 10, so we have found the multiplicative inverse of 3 mod 10. Therefore, 3*(7*8)=8 mod 10. 7*8=56=6 mod 10. Therefore, 3*6=8 mod 10, and so x=6. This is the `standard' way of solving for such an x. You find the z such that az=1 mod n, and then you have a*(zm)=m mod n.

    Anyway, I deviate. We have x=1 and the two equations,

    2x-y=-1\text{ mod }10,
    x+y=4 \text{ mod }10.

    Substituting into the second equation, we have y=3, as required.

    Does that help?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2011
    Posts
    2
    Thanks for reply,
    I understand that these equations are pretty simple, have many solutions and it's easy to solve them manualy.
    Like in your example x=11 and y=23 works too.

    But i'm trying to write a computer code to solve these equations amd manual method doesn't work here.

    Some how i need to get rid of modulo operation
    transform my equations from this form:
    a11x1+a12x2+a13 = a14 mod 10
    a21x1+a22x2+a23 = a24 mod 10

    to:
    a11x1+a12x2+a13 = a14 + 10*q1
    a21x1+a22x2+a23 = a24 + 10*q2

    For the first equation i just could choose random quotient and eliminate mod operation, but i'm not sure what to do with second.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by spak View Post
    Thanks for reply,
    I understand that these equations are pretty simple, have many solutions and it's easy to solve them manualy.
    Like in your example x=11 and y=23 works too.

    But i'm trying to write a computer code to solve these equations amd manual method doesn't work here.

    Some how i need to get rid of modulo operation
    transform my equations from this form:
    a11x1+a12x2+a13 = a14 mod 10
    a21x1+a22x2+a23 = a24 mod 10

    to:
    a11x1+a12x2+a13 = a14 + 10*q1
    a21x1+a22x2+a23 = a24 + 10*q2

    For the first equation i just could choose random quotient and eliminate mod operation, but i'm not sure what to do with second.
    No, you want keep the modulo. You can use the Euclidean algorithm to solve the equation ax=b \text{ mod } n as follows,

    By the E.A. gcd(a, n) = ap+nq. It must be that gcd(a, n) \mid b, otherwise your equation has no solutions. Therefore, x=pr \text{ mod }n where gcd(a, n) = br (by multiplying gcd(a, n) = ap+nq through by r and then applying mod n).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Simultaneous equations involving cos and sin
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: October 17th 2010, 05:18 AM
  2. Modulo of squares = modulo of roots
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 1st 2009, 10:04 AM
  3. solving diophantine equations with modulo
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 3rd 2009, 12:23 AM
  4. Equations Involving Brackets
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 1st 2009, 06:54 PM
  5. simultaneous equations involving e and ln.
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 13th 2007, 01:40 PM

Search Tags


/mathhelpforum @mathhelpforum