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...