Results 1 to 4 of 4

Thread: 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
    724
    Awards
    1
    $\displaystyle 2x \equiv 1 (mod7)\\
    x\equiv 3(mod5)\\
    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
    11,163
    Thanks
    736
    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:
    $\displaystyle 2x \equiv 1~\text{mod 7}$

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

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

    $\displaystyle x = 2~\text{mod 7}$

    So we need to solve
    $\displaystyle x = 2~\text{mod 7}$
    $\displaystyle x = 3~\text{mod 5}$
    $\displaystyle 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
    $\displaystyle 5r_1 + (7 \cdot 8)s_1 = 1$

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

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

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

    Then a solution to the system will be:
    $\displaystyle 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 $\displaystyle 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; Nov 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
    724
    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: Mar 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: Mar 18th 2009, 05:12 AM
  4. More congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 17th 2009, 10:40 PM
  5. Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum