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,408
    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
    10
    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, 10:28 PM
  2. solving linear congruences...please help
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 30th 2010, 03:07 AM
  3. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 19th 2009, 09:02 PM
  4. Linear Congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 19th 2009, 10:33 PM
  5. linear congruences
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 14th 2008, 10:40 AM

Search Tags


/mathhelpforum @mathhelpforum