Results 1 to 5 of 5

Math Help - question on distinct solutions to congruences

  1. #1
    Junior Member
    Joined
    Aug 2008
    Posts
    42

    question on distinct solutions to congruences

    I had 5 problems to find all distinct solutions or show there are none. I did all 5 using a table of x values and just testing each, basically brute forcing them. I seem to be all over the place trying to figure them out in a more efficient manner. Any suggestions on how to do these with a good method would be greatly appreciated:

    1.
    x^2 + x + 3 = 0(mod 5)

    2.
    x^2 + 2x + 3 = 0(mod 5)

    3.
    x^2 = 4(mod 15)

    4.
    x^2 + x + 4 = 0(mod 8)

    5.
    x^3 + 2x^2 + 5x + 6 = 0(mod 11)

    As I said, I already know the answers from brute forcing and checking the back of the book, but I can not seem to find a consistent, better method, especially for number 5, and this is something I really want to understand how to do.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,658
    Thanks
    598
    Hello, Proggy!


    I'll help with a few of these.
    I'm still working on the others . . .


    1)\;\;x^2 + x + 3 \:\equiv \:0 \pmod{5}
    Note that: . 1 \equiv -4 \pmod{5}

    So we have: . x^2 - 4x + 3 \:\equiv\:0 \pmod{5}

    Factor: . (x - 1)(x - 3)\:\equiv\:0 \pmod{5}

    Therefore: . \begin{array}{ccccccc}x-1\:\equiv 0\pmod{5} & \Rightarrow & \boxed{x \:\equiv 1\pmod{5}} \\<br />
x -3\:\equiv\:0 \pmod{5}& \Rightarrow & \boxed{x \:\equiv 3\pmod{5}} \end{array}



    3)\;\;x^2 \:\equiv\:4 \pmod{15}
    We have: . x \:\equiv \:\pm2\pmod{15}

    Therefore: . \boxed{x \:\equiv\:2,\:13}



    4)\;\;x^2 + x + 4 \:\equiv\: 0 \pmod{8}

    Note that: . 1 \:\equiv -7\:\text{ and }\: 4 \:\equiv\:12 \pmod{8}

    So we have: . x^2 - 7x + 12 \:\equiv\:0 \pmod{8}

    Factor: . (x-3)(x-4) \:\equiv\:0 \pmod{8}

    Therefore: . \boxed{x \:\equiv\:3,\:4} \pmod{8}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,658
    Thanks
    598
    Hello again, Proggy!

    I just saw through the last one . . .


    5)\;\;x^3 + 2x^2 + 5x + 6 \:\equiv\: 0 \pmod{11}

    Note: . 2\:\equiv\:-9.\;\; 5 \:\equiv\:27,\;\;6 \:\equiv\:-27 \pmod{11}

    So we have: . x^3 - 9x^2 + 27x - 27 \:\equiv\:0 \pmod{11}

    Factor: . (x - 3)^3 \:\equiv\:0 \pmod{11}

    Therefore: . \boxed{x\:\equiv\:3\pmod{11}}

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Hi Soroban and thanks for the help!

    For 1, I actually did this similar by changing it to be x^2 + x - 2 to get factors of (x+2)(x-1), resulting in the same answer.

    Attempting to use the same method on successive problems is why I discarded it as possibly not the best way. Number 3 is the perfect example. You got the +/-2 part, but there is an additional answer of +/-7 that works as well. I ended up working the problem with mod 3 and mod 5 and brute forcing 3 and 5 values respectively. Then I took the common values mod 15 and tested all of them to see which ones worked. Basically a more efficient brute force technique, but still not very efficient as the mod value increases.

    For number 4, do you just have to basically know which numbers to change to make it factor or is there a way to help you choose?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by Soroban View Post
    Hello again, Proggy!

    I just saw through the last one . . .


    Note: . 2\:\equiv\:-9.\;\; 5 \:\equiv\:27,\;\;6 \:\equiv\:-27 \pmod{11}

    So we have: . x^3 - 9x^2 + 27x - 27 \:\equiv\:0 \pmod{11}

    Factor: . (x - 3)^3 \:\equiv\:0 \pmod{11}

    Therefore: . \boxed{x\:\equiv\:3\pmod{11}}
    Okay, so it looks like you just have to play around with it until you recognize a factorable equation? I brute forced all 11 possible incongruent numbers and found that only x congruent 3 (mod 11) worked. Your method is obviously better, but what if I don't immediately recognize the equation that you saw?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: December 19th 2011, 09:34 AM
  2. I think this question is on congruences and RSA
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 12:35 AM
  3. [SOLVED] Solutions of Congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 29th 2008, 09:11 AM
  4. [SOLVED] Linear Congruences - Classes of Solutions
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 12th 2008, 08:04 AM
  5. Replies: 0
    Last Post: March 21st 2007, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum