Results 1 to 6 of 6

Math Help - Find all values of X that satisfy multiple congruences

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    9

    Find all values of X that satisfy multiple congruences

    The question I'm given is this:

    Find all integral values of x such that 2x ≡ 4 (mod 5) and 3x ≡ 2 (mod 7).

    I can find all values of x that satisfy each individual congruence, but I'm not sure how to find all values that satisfy both. Could someone lend a hand?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by archon View Post
    The question I'm given is this:

    Find all integral values of x such that 2x ≡ 4 (mod 5) and 3x ≡ 2 (mod 7).

    I can find all values of x that satisfy each individual congruence, but I'm not sure how to find all values that satisfy both. Could someone lend a hand?

    2x=4\!\!\pmod 5\Longleftrightarrow x=2\!\!\pmod 5\,,\,\,3x=2\!\!\pmod 7\Longleftrightarrow x=3\!\!\pmod 7 , using inverses modulo 5 and modulo 7, resp.

    Well, you need all the numbers s.t. x=2\!\!\pmod 5=3\!\!\mod 7 ...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,710
    Thanks
    630
    Hello, archon!

    Here is a very primitive solution . . .


    \text{Find all integral values of }x\text{ such that: }\:\begin{array}{ccccc}2x &\equiv& 4 &\text{(mod 5)} \\ 3x &\equiv& 2 & \text{(mod 7)} \end{array}

    \text{We have: }\:\begin{array}{cccccccccccc}<br />
2x & \equiv & 4 & \text{(mod 5)} & \Rightarrow & x &\equiv& 2 & \text{(mod 5)} \\<br />
3x & \equiv & 2 & \text{(mod 7)} & \Rightarrow & x &\equiv& 3 & \text{(mod 7)} \end{array}


    This means: . \begin{array}{ccccccc}<br />
x &=& 5a + 2 & \text{for some integer }a & [1] \\<br />
x &=& 7b + 3 & \text{for some integer }b & [2] \end{array}

    We have: . 5a + 2 \:=\:7b + 3 \quad\Rightarrow\quad a \:=\:\dfrac{7b+1}{5} \;=\;b + \dfrac{2b + 1}{5}


    Since \,a is an integer, 2b+1 must be a multiple of 5.

    . . Then: . b \;=\;5k+2\:\text{ for some integer }k.


    Substitute into [2]: . x \;=\;7(5k+2) + 3 \;=\;35k + 14 + 3


    Therefore: . x \;=\;35k + 17 \quad\Rightarrow\quad x \:\equiv\:17\text{ (mod 35)}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2010
    Posts
    9
    Thanks a lot. I now understand how to solve this problem. I'm going to make sure I know how to solve all problems of this kind by trying them myself now.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2010
    Posts
    48
    Quote Originally Posted by tonio View Post
    2x=4\!\!\pmod 5\Longleftrightarrow x=2\!\!\pmod 5\,,\,\,3x=2\!\!\pmod 7\Longleftrightarrow x=3\!\!\pmod 7 , using inverses modulo 5 and modulo 7, resp.

    Well, you need all the numbers s.t. x=2\!\!\pmod 5=3\!\!\mod 7 ...

    Tonio
    Could you also solve this using the chinese remainder theorem?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by DarK View Post
    Could you also solve this using the chinese remainder theorem?

    Of course, since 5,7 are coprime: as 3\cdot 5 +(-2)\cdot 7 =1 , following the proof of the CRT we define

    x=3\cdot 15+2\cdot (-14)=17 , and any other solution will equal 17\!\!\pmod{35=5\cdot 7}

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Find vectors that satisfy the following conditions
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 21st 2011, 12:38 AM
  2. [SOLVED] For what values of r does the function y = e^rx satisfy
    Posted in the Calculus Forum
    Replies: 7
    Last Post: July 28th 2010, 04:25 PM
  3. Find two numbers that satisfy these conditions
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: February 14th 2010, 02:10 AM
  4. values which satisfy diferential equation
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: August 19th 2009, 11:08 AM
  5. Replies: 3
    Last Post: February 21st 2009, 08:47 AM

Search Tags


/mathhelpforum @mathhelpforum