Results 1 to 5 of 5

Math Help - CRT and System of Congruences

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    CRT and System of Congruences

    x\equiv1\ (mod\ 3)
    x\equiv3\ (mod\ 5)
    x\equiv5\ (mod\ 7)

    I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
    And I just want to know if I did this properly and if this is the right approach.

    x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)
    x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)
    Adding gives x\equiv-17 \ (mod\ 15)

    Comparing with the third equation:

    x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)
    x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)
    Adding gives x\equiv313\ (mod\ 15)

    So the solution is  \{313+15k:k\in\mathbb{Z}\}

    While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by kyldn6 View Post
    x\equiv1\ (mod\ 3)
    x\equiv3\ (mod\ 5)
    x\equiv5\ (mod\ 7)

    I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
    And I just want to know if I did this properly and if this is the right approach.

    x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)
    x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)
    Adding gives x\equiv-17 \ (mod\ 15)

    Comparing with the third equation:

    x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)
    x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)
    Adding gives x\equiv313\ (mod\ 15)

    So the solution is  \{313+15k:k\in\mathbb{Z}\}

    While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.

    Let me suggest you a nice observation here.

    x+2 = 0(mod 3)
    x+2 = 0(mod 5)
    x+2 = 0(mod 7)

    Now can you take it fwd?

    Also haven't seen your eqs in details but answer appear wrong. Put k=1 and try the last congruence?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,393
    Thanks
    1327
    Quote Originally Posted by kyldn6 View Post
    x\equiv1\ (mod\ 3)
    x\equiv3\ (mod\ 5)
    x\equiv5\ (mod\ 7)

    I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
    And I just want to know if I did this properly and if this is the right approach.

    x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)
    x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)
    Adding gives x\equiv-17 \ (mod\ 15)

    Comparing with the third equation:

    x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)
    x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)
    Adding gives x\equiv313\ (mod\ 15)
    I think you mean x\equiv 313 (mod 105) here.

    So the solution is  \{313+15k:k\in\mathbb{Z}\}
    And  \{313+105k:k\in\mathbb{Z}\} here.

    While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.
    What do you mean by "inverse of a congruence"?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by HallsofIvy View Post
    I think you mean x\equiv 313 (mod 105) here.


    And  \{313+105k:k\in\mathbb{Z}\} here.


    What do you mean by "inverse of a congruence"?
    Yes this looks correct. Thanks.
    @kyldn6 But you don't have to perform any of these modular calculations if you look at the observations I said earlier. It comes directly from there, atleast in this question.
    Last edited by aman_cc; October 12th 2009 at 10:03 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    12
    Yes, those were typos. And thanks everyone!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is there a fast way to solve this system of congruences on paper?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: October 19th 2010, 09:15 PM
  2. Trouble solving a system of linear congruences.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 14th 2010, 10:10 AM
  3. System of Congruences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 29th 2008, 11:00 PM
  4. Congruences
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 10th 2007, 07:59 PM
  5. Replies: 0
    Last Post: March 21st 2007, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum