Results 1 to 4 of 4

Math Help - how to show that a quadratic congruence is solvable

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    3

    how to show that a quadratic congruence is solvable

    Verify that x^2 \equiv 10 \mbox{ (mod 89)} is solvable. Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by rsvp mx View Post
    Verify that x^2 \equiv 10 \mbox{ (mod 89)} is solvable. Thanks in advance!
    (\frac{10}{89})=(\frac{2}{89})(\frac{5}{89})

    (\frac{2}{89})=(-1)^\frac{89^2-1}{8}=1

    (\frac{5}{89})=(\frac{89}{5})(-1)^{\frac{4}{2}\frac{88}{2}}

    = (\frac{-1}{5})

    = (-1)^\frac{5-1}{2}

    = 1

    Hence (\frac{10}{89})=1

    So x^2 \equiv 10 \mbox{ (mod 89)} is solvable.
    Last edited by alexmahone; November 15th 2009 at 08:45 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by rsvp mx View Post
    Verify that x^2 \equiv 10 \mbox{ (mod 89)} is solvable. Thanks in advance!

    This follows at once from the properties of Legendre's symbol and Gauss' Quadratic Reciprocity Law.
    But if you haven't yet studied this or if you can't use it then I know of no methods but "wise" brutal force: for example, it's not too hard to

    check that 5=19^2\!\!\pmod {89} (just taking multiples of 89 and checking which one summed to 5 is a perfect square. In this case it was 89\cdot 4=356=361-5=19^2-5)


    Then, as 2 = 36\cdot 5\!\!\pmod {89}=(6\cdot 19)^2\!\!\pmod {89}=25\!\!\pmod {89}\,,\,\,we\,\,get 10=2\cdot 5=(25\cdot 19)^2=30^2\!\!\pmod {89}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    3
    Thank you all so much! My understanding of the Legendre symbol was a little unclear, but not anymore

    So if I wanted to show that for what primes p would make x^2 \equiv 13 \mbox{ (mod p)} solvable, I would set (\frac{13}{p}) = 1.

    Then, (\frac{13}{p}) = (\frac{p}{13})(-1)^{\frac{p-1}{2} * \frac{13-1}{2}} = (\frac{p}{13})

    Besides "brute force", how can I find values of p that satisfy the equation (\frac{p}{13}) = 1?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Is this congruence solvable?
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: July 20th 2011, 09:42 PM
  2. Replies: 7
    Last Post: February 20th 2010, 07:28 PM
  3. quadratic congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2009, 03:02 PM
  4. prove that a congruence is solvable
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 14th 2009, 02:45 PM
  5. quadratic congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 1st 2009, 10:14 PM

Search Tags


/mathhelpforum @mathhelpforum