Results 1 to 4 of 4

Math Help - congruences

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    32

    congruences

    Solve the simultaneous congruences

    2x = 1 (mod7)
    x= 3(mod5)
    x= 3(mod8)

    those aren't supposed to be equal signs- they are three slashes(congruences).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    2x \equiv 1 (mod7)\\<br />
x\equiv 3(mod5)\\<br />
x\equiv 3(mod8)

    I would do the first one, but I'm out of time, gotta get ready for work, and wouldn't want to steer you wrong.

    For the second one, you can see that 3=5*0+3, so when x = 3, it is congruent to 3(mod5). So find the next in the progression by just adding 5, so x=3+5n for any integer n (this creates the series ...,3,8,13...)

    For the third one, you can see that 3=8*0+3, so when x=3 it is congruent to 3(mod8). So find the next progression by just adding 8, so x=3+8n for any integer n (this creates the series ...3,11,19...)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,901
    Thanks
    329
    Awards
    1
    Quote Originally Posted by anncar View Post
    Solve the simultaneous congruences

    2x = 1 (mod7)
    x= 3(mod5)
    x= 3(mod8)

    those aren't supposed to be equal signs- they are three slashes(congruences).
    See here.

    First let's solve the first congruence for x:
    2x \equiv 1~\text{mod 7}

    4 \cdot 2x \equiv 2 \cdot 1~\text{mod 7}

    8x \equiv 2~\text{mod 7}

    x = 2~\text{mod 7}

    So we need to solve
    x = 2~\text{mod 7}
    x = 3~\text{mod 5}
    x = 3~\text{mod 8}

    The modulos are pairwise coprime, so we may state a solution exists by the Chinese Remainder Theorem.

    Use the extended Euclidean algorithm to find integer r1 and s1 such that
    5r_1 + (7 \cdot 8)s_1 = 1

    One such pair is r_1 = -11 and s = 1.

    Now do the same for
    7r_2 + (5 \cdot 8)s_2 = 1 <-- r2 = -17 and s2 = 3
    and
    8r_3 + (5 \cdot 7)s_3 = 1 <-- r3 = -13 and s3 = 3

    Now, define e_1 = (7 \cdot 8)s_1 = 56, e_2 = (5 \cdot 8)s_2 = 120, and e_3 = (5 \cdot 7)s_3 = 105.

    Then a solution to the system will be:
    x = 3 \cdot 56 + 2 \cdot 120 + 3 \cdot 105 =  723
    which you may verify is a correct solution.

    Edit: Whoops! I just noticed. This answer will be correct a modulo 5 x 7 x 8 = 280. So we have a smaller answer which is equivalent to 723 \equiv 163~\text{mod 280}. So we can use x = 163 as the solution.

    -Dan

    (See, you can teach an old dog new tricks!)
    Last edited by topsquark; November 7th 2007 at 11:37 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Oh, my apologies, I looked at it as three independent equations, just ignore my earlier post.
    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