Results 1 to 4 of 4

Math Help - a difficult problem

  1. #1
    Junior Member
    Joined
    Jun 2009
    Posts
    25

    a difficult problem

    Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by silentbob View Post
    Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).
    Getting rid of the modulo then solving as per usual works, although not all of my answers are whole numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by silentbob View Post
    Find all solutions of the congruence x^2 + 6x − 31 = 0 (mod 72).
    Complete the square and solve a congruence of the form X^2\equiv K\,(\bmod\,72).

    This is standard method for solving general quadratic congruences, as found in any good number-theory textbook.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Okay, I’ve tried the problem myself and found that it’s not very straightforward (I believe it’s because the modulus is not a prime). Here’s my solution.

    x^2 + 6x - 31 \equiv 0\,(\bmod\,72)

    x^2 + 6x + 9 \equiv 40\,(\bmod\,72)

    (x+3)^2 \equiv 40\,(\bmod\,72)

    X^2 \equiv 40\,(\bmod\,72)

    where X=x+3. It is clear that X must be even so let X=2Y.

    4Y^2 \equiv 40\,(\bmod\,72)

    Y^2 \equiv 10\,(\bmod\,18)

    Again we see that Y must be even, say Y=2Z.

    4Z^2 \equiv 10\,(\bmod\,18)

    2Z^2 \equiv 5\,(\bmod\,9)

    2Z^2 \equiv 14\,(\bmod\,9)\quad(\because\ 5\equiv14\,(\bmod\,9))

    Z^2 \equiv 7\,(\bmod\,9)\quad(\because\ \gcd(2,9)=1)

    Trying 1^2,\,2^2,\,3^2,\,\ldots,\,8^2 in turn, we find that Z=4,\,5 are the only solutions between 1 and 8. Hence the general solution is

    Z\,=\,4+9n,\,5+9n

    \implies\ Y\,=\,2Z\,=\,8+18n,\,10+18n

    \implies\ X\,=\,2Y\,=\,16+36n,\,20+36n

    \implies\ X-3\,=\,\fbox{$x\,=\,13+36n,\,17+36n$}

    Maybe someone has a neater solution?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. difficult problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 30th 2010, 03:41 AM
  2. Difficult problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 10th 2010, 06:23 PM
  3. a difficult problem
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: June 24th 2009, 02:25 PM
  4. Difficult problem
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: November 10th 2008, 10:50 PM
  5. A very difficult problem for me
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 20th 2008, 08:51 AM

Search Tags


/mathhelpforum @mathhelpforum