Results 1 to 3 of 3

Math Help - Congruence problem

  1. #1
    Member
    Joined
    Nov 2007
    Posts
    108

    Congruence problem

    I have this problem in my book:
    Solve the congruences:
    x^3+2x-3\equiv0(mod 9);
    x^3+2x-3\equiv0(mod 5);
    x^3+2x-3\equiv0(mod 45) .

    Does this question ask me to solve this as a system of congruences? I'm unsure on this.If not, here is my way to solve each individually, can someone check if what I'm doing is correct. Thanks.
    Since 9=3x3, by the CRS we can solve the system x^3+2x-3\equiv0(mod 3) and x^3+2x-3\equiv0(mod 3). I check {0,1,2} and see that all of them are solutions, so the answer for the first congruence are {0,1,2}.
    Do the same thing for the second congruence, and I get {1,3}
    Since 45=3x3x5. We can solve the third congruence by solving a system of
    x^3+2x-3\equiv0(mod 3) , x^3+2x-3\equiv0(mod 3) and  x^3+2x-3\equiv0(mod 5) .
    So,the solution for the third congruence is the common solution for the first and second, which is {1}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by namelessguy View Post
    Since 9=3x3, by the CRS we can solve the system
    Be careful, in the Chinese Remainder Theorem you must are relatively prime numbers, which 3 and 3 are not. Otherwise, it would mean than being divisible by 3 is the same as being divisible by 9...

    Then I can't see a quicker solution than looking at the 9 cases (it is pretty quick though, since the remainder modulo 9 is just the sum of the digits). I think 1, 2 and 6 are solutions.

    For the third one, using the CRS is correct however, since 5 and 9 have no common divisor except 1. What you get is that the solutions are the integers congruent to 1, 2 or 6 modulo 9, and to 1 or 3 modulo 5. This makes 3x2=6 possibilities of congruence systems. The CRS gives you that the solutions of these systems are the integers congruent to any particular solution modulo 45. For these particular solutions, I get 1 (congruent to 1 mod 5 and 1 mod 9), 11 (1 and 2), 6 (1 and 6), 28 (3 and 1), 38 (3 and 2) and 33 (3 and 6).
    Last edited by Laurent; September 23rd 2008 at 02:30 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Also note that x^3+2x-3=(x-1)(x^2+x+3)

    So 1 is a solution in each equation !
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 29th 2011, 08:41 AM
  2. [SOLVED] Congruence Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 18th 2011, 10:23 PM
  3. Congruence problem with gcd
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 9th 2009, 01:18 AM
  4. Another congruence problem
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 3rd 2009, 06:14 PM
  5. Congruence problem with LCM
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 19th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum