Results 1 to 5 of 5

Thread: CRT and System of Congruences

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    CRT and System of Congruences

    $\displaystyle x\equiv1\ (mod\ 3)$
    $\displaystyle x\equiv3\ (mod\ 5)$
    $\displaystyle 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.

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

    Comparing with the third equation:

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

    So the solution is $\displaystyle \{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
    678
    Thanks
    1
    Quote Originally Posted by kyldn6 View Post
    $\displaystyle x\equiv1\ (mod\ 3)$
    $\displaystyle x\equiv3\ (mod\ 5)$
    $\displaystyle 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.

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

    Comparing with the third equation:

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

    So the solution is $\displaystyle \{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
    19,724
    Thanks
    3007
    Quote Originally Posted by kyldn6 View Post
    $\displaystyle x\equiv1\ (mod\ 3)$
    $\displaystyle x\equiv3\ (mod\ 5)$
    $\displaystyle 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.

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

    Comparing with the third equation:

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

    So the solution is $\displaystyle \{313+15k:k\in\mathbb{Z}\}$
    And $\displaystyle \{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
    678
    Thanks
    1
    Quote Originally Posted by HallsofIvy View Post
    I think you mean $\displaystyle x\equiv 313 (mod 105)$ here.


    And $\displaystyle \{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; Oct 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: Oct 19th 2010, 09:15 PM
  2. Trouble solving a system of linear congruences.
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 14th 2010, 10:10 AM
  3. System of Congruences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 29th 2008, 11:00 PM
  4. Congruences
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Oct 10th 2007, 07:59 PM
  5. Replies: 0
    Last Post: Mar 21st 2007, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum