1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is 19 = x^2 mod p solvable? p=68659

  1. Dec 10, 2007 #1
    Can some one tell me how to figure out if this is solvable or not?

    For the Prime number p=68659,

    19=x^2 mod p.

    Why?
     
  2. jcsd
  3. Dec 11, 2007 #2
    This is a matter in quadratic reciprocity. Since 68659 and 19 are both prime and congruent to 3 modulo 4. The problem depends upon applying that case.
     
  4. Dec 11, 2007 #3
    So if it ends up equaling 1 it will be solvable, and if it ends up equaling -1 it wont be solvable? If it is solvable, how do you solve it?
     
  5. Dec 11, 2007 #4
    You'll have to do a little more reading on your own.
     
  6. Dec 11, 2007 #5
    k, thanks
     
  7. Dec 11, 2007 #6
    If you want to spend time calculating it:

    [tex]41637^2-19 = (25250)(68659)[/tex]
     
  8. Dec 11, 2007 #7
    hmmm...I have no clue how you did that. Could you give me a hint or something, i.e. the name of the procedure?
     
  9. Dec 11, 2007 #8
    I just ran a calculator, however, you would have to go through 25250 terms, so I had to shorten that. The fact is all odd squares are congruent to 1 Mod 8. Both 19 and 68659 and congruent to 3 Mod 8. So to solve the equation X^2 = 19 + 68659K, we must have K==2 Mod 8. Thus K=2+8J.

    So we are left with the form X^2 = 19 + 137318 + 549272(J) = 137337 + 549272(J). So the program runs much faster now through values of J. J = 3156.

    But, if you'd go back to how the problem is supposed to be worked, such details are unnecessary.
     
  10. Dec 11, 2007 #9
    OK how do you work the problem x^2 = 7 mod 67 since according to the law of quadratic recprocity there is a solution. I have

    X^2 = 7 + 67K where K = 2 + 8J
    X^2 = 7 + 134 + 536J = 141 + 536J

    Where do we go from here?
     
  11. Dec 11, 2007 #10

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Shouldn't that be K = -2 + 8J?
     
  12. Dec 11, 2007 #11

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    A highly inefficient Pari/GP program will give the answer in 63 milliseconds. I'm sure that code could be optimized to run in less than 10 ms, but why bother?
     
  13. Dec 11, 2007 #12
    if [tex]19^{(p-1)/2}[/tex] [tex]\equiv[/tex] +1 mod p then your congruence is solvable
     
  14. Dec 11, 2007 #13
    Ramsey2879: OK how do you work the problem x^2 = 7 mod 67 since according to the law of quadratic recprocity there is a solution.

    What solution? Both 67 and 7 are congruent to 3 mod 4. So since x^2==67==4 Mod 7 has a solution, your problem does not.

    CRGreathouse: A highly inefficient Pari/GP program will give the answer in 63 milliseconds. I'm sure that code could be optimized to run in less than 10 ms, but why bother?

    As far as what I was working on, I only used a old HP 15c, which does about 60 to 100 things a minute.

    al-mahed: if 19^((p-1)/2) == +1 mod p then your congruence is solvable.

    That's true, but its easier to use quadratic reciprocity. We look at X^2 ==68659 ==12 Mod 19, which is the same as (X/2)^2 == 3 Mod 19, and then reverse again getting X^2==19==1 Mod 3.

    Since the cases are congruent to 3 Mod 4, the last equation is easily seen to be true, so the previous equation is false and so the original problem is true, i.e. has a solution.
     
    Last edited: Dec 11, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Is 19 = x^2 mod p solvable? p=68659
  1. A=x^b mod p, solvable? (Replies: 3)

  2. X² + y² = 1 (mod p) (Replies: 7)

Loading...