Results 1 to 6 of 6

Math Help - congruences 2

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    98

    congruences 2

    Slove the system of congruences

    3x = 2 mod 4
    4x = 1 mod 5
    6x = 3 mod 9

    is it no solution since 6 and 9 do not have an inverse since the gcd of 6 and 9 is not one thus u cant write it in the form x=a mod p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2008
    Posts
    98
    I have been trying to find the inverse and solve it that way but i dont know if that is right?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    If ac \equiv bc \ (\text{mod } m) and (c,m) = d, then a \equiv b \left(\text{mod } \frac{m}{d}\right)

    Keeping in this in mind, I'm going to simplify the congruences first:
    \begin{array}{rcll} 3x & \equiv & 2 & (\text{mod } 4) \\ 3x & \equiv & 6 & (\text{mod } 4) \\ x & \equiv & 2 & (\text{mod } 4) \end{array}........ \begin{array}{rcll} 4x & \equiv & 1 & (\text{mod } 5) \\ 4x & \equiv & -4 & (\text{mod } 5) \\ x & \equiv & -1 & (\text{mod } 5) \\ x & \equiv & 4 & (\text{mod } 5) \end{array}........ \begin{array}{rcll} 6x & \equiv & 3 & (\text{mod } 9) \\ 6x & \equiv & 12 & (\text{mod }9) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}

    So we're left with the system:
    \begin{array}{rcll} x & \equiv & 2 & (\text{mod } 4) \\ x & \equiv & 4 & (\text{mod } 5) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}

    And by the Chinese Remainder theorem, since (4, 5, 3) = 1, there is a unique solution modulo 4\cdot 5 \cdot 3 = 60. Should be pretty simply to solve this one.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by o_O View Post
    If ac \equiv bc \ (\text{mod } m) and (c,m) = d, then a \equiv b \left(\text{mod } \frac{m}{d}\right)

    Keeping in this in mind, I'm going to simplify the congruences first:
    \begin{array}{rcll} 3x & \equiv & 2 & (\text{mod } 4) \\ 3x & \equiv & 6 & (\text{mod } 4) \\ x & \equiv & 2 & (\text{mod } 4) \end{array}........ \begin{array}{rcll} 4x & \equiv & 1 & (\text{mod } 5) \\ 4x & \equiv & -4 & (\text{mod } 5) \\ x & \equiv & -1 & (\text{mod } 5) \\ x & \equiv & 4 & (\text{mod } 5) \end{array}........ \begin{array}{rcll} 6x & \equiv & 3 & (\text{mod } 9) \\ 6x & \equiv & 12 & (\text{mod }9) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}

    So we're left with the system:
    \begin{array}{rcll} x & \equiv & 2 & (\text{mod } 4) \\ x & \equiv & 4 & (\text{mod } 5) \\ x & \equiv & 2 & (\text{mod } 3) \end{array}

    And by the Chinese Remainder theorem, since (4, 5, 3) = 1, there is a unique solution modulo 4\cdot 5 \cdot 3 = 60. Should be pretty simply to solve this one.
    i get the right answer after applying the CRT to the reduced congruences, but i still dont know how u reduced the congruences or simplified them. Could you maybe explain it a little bit. Could u find the inverse modulo of each congruence and and reduce it to the form x=a mod m
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    80
    Hello,

    Divide the formula of o_O into 2 formulae:

    1) If ac\equiv bc\pmod m and (c, m)=1 then a\equiv b\pmod m.
    2) If ac\equiv bc\pmod {mc} then a\equiv b\pmod m.

    1) corresponds to the case where you can find an inverse.
    2) is a technique to decrease the modulus.
    You add the modulus as many times as you want so that the coefficient of x and the right-hand-side have a common divisor.

    Bye.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    What I did was play around with the congruences a little. Remember, they sort of act like equality signs as well. Let's take the middle one I did:

    <br />
\begin{array}{rcll} 4x & \equiv & 1 & (\text{mod } 5) \\ 4x & \equiv & -4 & (\text{mod } 5) \qquad \text{1. Subtracted 5} \\ x & \equiv & -1 & (\text{mod } 5) \qquad \text{2. Divided both sides by 4} \\ x & \equiv & 4 & (\text{mod } 5) \qquad \text{3. Added 5 to get a least residue} \end{array}<br />

    Basically, I wanted to get rid of the coefficient in front of the x and what I wanted is to ultimately divide it out:
    1. If something is congruent to 4x mod 5, then adding or subtracting multiple of 5's will still be congruent to 4x. Remember: a \equiv b \ (\text{mod m}) \ \iff \ a = b + km

    2. This refers to the very first statement I had in my first post

    3. Again, adding and subtracting multiples of the modulus will not change the congruence as we did in step 1. The main purpose in doing so was to get a least residue (i.e. the "remainder")

    Edit: Oh beaten!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  2. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  3. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum