Results 1 to 4 of 4

Thread: 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 $\displaystyle 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    $\displaystyle \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: Nov 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: Jun 24th 2009, 02:25 PM
  4. Difficult problem
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: Nov 10th 2008, 10:50 PM
  5. A very difficult problem for me
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Oct 20th 2008, 08:51 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum