Results 1 to 10 of 10

Math Help - Set of 4 simultaneous equations using modular

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    Set of 4 simultaneous equations using modular

    Hi all,

    I have the following set of equations:

    (13a + 4b)mod729 = 19
    (13c + 4d)mod729 = 15
    (4a + 3b)mod729 = 5
    (4c + 3d)mod729 = 3
    (11a + 4b)mod729 = 5
    (11c + 4d)mod729 = 7

    I feel a lot more comfortable solving this if i had 2 unknowns. With 4 unknowns do i need to create a matrix or anything to solve them?

    Thanks!
    Last edited by sirellwood; March 17th 2011 at 05:37 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by sirellwood View Post
    Hi all,

    I have the following set of equations:

    (13a + 4b)mod729 = 19
    (13c + 4d)mod729 = 15
    (4a + 3b)mod729 = 5
    (4c + 3d)mod729 = 3
    (11a + 4b)mod729 = 5
    (11c + 4d)mod729 = 7

    I feel a lot more comfortable solving this if i had 2 unknowns. With 4 unknowns do i need to create a matrix or anything to solve them?

    Thanks!
    I don't think that there is a solution to this. Consider the following two equations:
    13a + 4b = 19

    and
    4a + 3b = 5

    We should be able to solve this system. So from the second equation we get
    a = 4^{-1} \cdot (5 - 3b)

    Mind you this is in mod 729. So we need the multiplicative inverse of 4 in mod 729. This is 547. Thus
    a = 547 \cdot ( 5 - 3b) = 548 - 183b

    Put this value for a in the first equation:
    13(548 - 183b) + 4b= 19

    etc, etc. I get a = 65 and b = 158. But

    11a + 4b = 618
    which is not 5 as your equations specifiy.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    Thanks topdsquark... you are right. I made an error when forming my equations. Basially i am solving some cipher matrices and i thought this one was linear when it is infact affine so ill have to redetermine my equations and post a new thread!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,908
    Thanks
    767
    Hello, sirellwood!

    Is there a typo? .The system is inconsistent.


    I have the following set of equations:

    . . \begin{array}{cccccccc}<br />
\,[1] &13a + 4b &\equiv& 19 &\text{(mod 729} \\<br />
\,[2] & 13c + 4d  &\equiv& 15 &\text{(mod 729)} \\<br />
\,[3] & 4a  + 3b &\equiv& 5 & \text{(mod 729)} \\<br />
\,[4] & 4c + 3d &\equiv& 3 & \text{(mod 729)} \\<br />
\,[5] & 11a + 4b &\equiv& 5 & \text{(mod 729)} \\<br />
\,[6] & 11c + 4d &\equiv& 7 & \text{(mod 729)} <br />
\end{array}

    Look again . . . You don't have to solve for four unknowns all at one time.


    [1] and [3] comprise a system you should be able to solve.

    . . \begin{array}{ccccccc}<br />
\,[1] & 13a + 4b &\equiv& 19\text{ (mod 729)} \\<br />
\,[3] & 4a + 3b &\equiv& 5 \text{ (mod 729)} \end{array} . .
    . . . I'll drop the (mod 729) for now.


    \begin{array}{cccccccc}<br />
\text{Multiply [1] by 3:} & 39a + 12b &\equiv& 57 \\<br />
\text{Multiply [3] by 4:} & 16a + 12b &\equiv& 20 \end{array}

    \text{Subtract: }\:23a \:\equiv\:37


    \text{Multiply by 317: }\;317(23a) \:\equiv\;317(37)

    . . . . . . . . . . . . . . . 7291a \:\equiv\:11,\!729


    \text{Since }\,7291 \,\equiv\,1\text{ (mod 729)}\:\text{ and }\:11,\!729\,\equiv\,65\text{ (mod 729)}

    . . \text{we have: }\:\boxed{a \:\equiv\:65\text{ (mod 729)}}


    Substitute into [3]: . 4(65) + 3b \:\equiv\:5 \quad\Rightarrow\quad 260 + 3b \:\equiv\;5

    . . 3b \:\equiv\:-255 \:\equiv\:474 \quad\Rightarrow\quad \boxed{b \:\equiv\:158 \text{ (mod 729)}}



    Do the same for [2] and [4].

    You will find that: . \boxed{c\,\equiv\,255,\;d\,\equiv\,633\text{ (mod 729)}}


    But we find that these answers do not satisfy [5] and [6] . . .

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    The OP has said in a private communication that the equations were wrong. However, I believe the help given in this thread should be sufficient for the OP to attempt to solve the correct equations.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    thanks soroban. yeah as i posted above, this question was to do with an affine cipher matrix, not a linear cipher matrix so my set of equations should look like this i think....

    (13a + 4b)mod729 = 19-e
    (13c + 4d)mod729 = 15-f
    (4a + 3b)mod729 = 5-e
    (4c + 3d)mod729 = 3-f
    (11a + 4b)mod729 = 5-e
    (11c + 4d)mod729 = 7-f

    Does it work now?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    and yes mrfantastic, the help was very useful as i came out with

    a=7, b=680 c=4, d=705, e=124 and f=59....for the record
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    Sorry to keep going back to this thread but has anyone else tried to solve it and got the same numbers as me? I ask because the numbers form a 2x2 and 2x1 matrix that are needed to do something else and although my answers seem to hold fine in the first step, when i use them in the second, they do not anymore.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by sirellwood View Post
    Sorry to keep going back to this thread but has anyone else tried to solve it and got the same numbers as me? I ask because the numbers form a 2x2 and 2x1 matrix that are needed to do something else and although my answers seem to hold fine in the first step, when i use them in the second, they do not anymore.
    There may be more general solutions lurking out there, such as a = 7 + 35n or something. But I ran your numbers through the equations and they check out.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1
    ok, so as long as all the solutions are mod729, does that mean i take my answers to be correct?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. modular equations?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 1st 2012, 06:08 PM
  2. modular equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 27th 2009, 04:33 PM
  3. Replies: 3
    Last Post: February 27th 2009, 08:05 PM
  4. Modular Arithmetic - Simultaneous Equation
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: April 28th 2005, 09:52 AM

Search Tags


/mathhelpforum @mathhelpforum