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

[quila]

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?

 

[robert Ihnot]

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.

 

[quila]

So if it ends up equaling 1 it will be solvable, and if it ends up equaling -1 it won't be solvable? If it is solvable, how do you solve it?

 

[robert Ihnot]

You'll have to do a little more reading on your own.

 

[quila]

k, thanks

 

[robert Ihnot]

If you want to spend time calculating it:

41637^2-19 = (25250)(68659)

 

[quila]

hmmm...I have no clue how you did that. Could you give me a hint or something, i.e. the name of the procedure?

 

[robert Ihnot]

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.

 

[ramsey2879]

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.

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?

 

[Gokul43201]

Shouldn't that be K = -2 + 8J?

 

[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?

 

[al-mahed]

if 19^{(p-1)/2} \equiv +1 mod p then your congruence is solvable

 

[robert Ihnot]

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.