Results 1 to 3 of 3

Math Help - linear congruences

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    98

    linear congruences

    Find the least nonnegative solution of each system of congruences below

    x=1mod7
    x=4mod6
    x=3mod5
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    x \equiv 1 \ (\text{mod } 7) \iff x = 1 + 7k_{1} \ \ k_{1} \in \mathbb{Z}

    x \equiv 4 \ (\text{mod } 6)
    ........ \begin{array}{rcll} \iff 1 + 7k_{1} & \equiv  & 4 & \ (\text{mod } 6) \\ 7k_{1} & \equiv & 3 & (\text{mod } 6) \\ 7k_{1} & \equiv & 21 & (\text{mod } 6) \\ k_{1} & \equiv & 3 & (\text{mod } 6) \\ k_{1} & = & 3 + 6k_{2} & k_{2} \in \mathbb{Z} \end{array}

    So: x = 1 + 7k_{1} = 1 + 7(3 + 6k_{2}) = 22 + 42k_{2} (So far, x satisfies the first two congruences)

    x \equiv 3 \ (\text{mod } 5)
    ........ \begin{array}{rcll} \iff 22 + 42k_{2} & \equiv & 3 & (\text{mod } 5) \\ 42k_{2} & \equiv & -19 & (\text{mod } 5) \\ 42k_{2} & \equiv & -84 & (\text{mod }5) \\ k_{2} & \equiv & -2 & (\text{mod }5) \\ k_{2} & \equiv & 3 & (\text{mod }5) \\ {\color{red}k_{2}} & = & 3 + 5k_{3} & k_{3} \in \mathbb{Z} \end{array}

    So: x = 22 + 42{\color{red}k_{2}} = \hdots
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by bigb View Post
    Find the least nonnegative solution of each system of congruences below

    x=1mod7
    x=4mod6
    x=3mod5
    x\equiv 1 ~ (7)
    x\equiv 3 ~ (5)
    Is equivalent to,
    x \equiv 8 ~ (7)
    x\equiv 8 ~ (5)
    These combine to,
    x\equiv 8 ~ (35)

    Thus, we have the system,
    x\equiv 4 ~ (6)
    x\equiv 8 ~ (35)

    This is equivalent to,
    x\equiv 4 + 6(24) ~ (6)
    x\equiv 8 + 35(4) ~ (35)

    Thus,
    x\equiv 148 ~ (6)
    x\equiv 148 ~ (35)

    This combines into,
    x\equiv 148 ~ (210)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 26th 2011, 09:28 PM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 02:07 AM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 19th 2009, 08:02 PM
  4. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 09:33 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 14th 2008, 09:40 AM

Search Tags


/mathhelpforum @mathhelpforum