How to solve this Diophantine equation?

This is an exam question from Number theory (especially of quadratic field extensions):

For which prime number $p$ can we solve the Diophantine equation $x^2-31y^2=-p$. Find also a solution for $p=3$.

I have the following solution: For $x^2-31y^2=1$ we can use the fundamental unit for $\Bbb{Z}[\sqrt{31}]$. This is given by $\epsilon=1520-273\sqrt{31}$ with $N(\epsilon)=1$. Thus for $x^2-31y^2=(x-y\sqrt{31})(x+y\sqrt{31})$ we find $x=\pm1520$ and $y=\pm273$. But how to find the $p$ and the other solutions? I thought over the factorization of $1520$ and $273$ and common prime divisor and $x^2-31y^2=-p$ equivalent with $-\frac{1}{p}(x^2-31y^2)=1$. But how to go on?

-
Well, what exam? –  Will Jagy Dec 31 '12 at 18:43

You might want to review the paper Solving the generalized Pell equation $x^{2} − Dy^{2} = N$.

Also, have a look at the web site Quadratic diophantine equations and fundamental unit BCMATH programs.

For example, you can play around with the methods by Lagrange-Mollin-Matthews and Nagell's method on that web site.

For your particular example with the equation:

$x^{2} - 31 y^{2}=-3$,

Using Nagell's method

Calculating $x1$ and $y1$, the least solution of Pell's equation $x^{2} - 31 y^{2} = 1$

Finished calculating $x1 ~ and ~ y1$

$x1=1520, y1=273$

$(11, 2)$ is a fundamental solution

$(-11, 2)$ is a fundamental solution

There are 2 fundamental solutions

You might also want tp look at WolframAlpha's solution.

Regards

-
The discriminant has two classes only, $x^2 - 31 y^2$ and $-x^2 + 31 y^2.$ As a result, $x^2 - 31 y^2$ represents prime $q > 0$ when $(q|31) = 1,$ but $-p$ for $p > 0$ when $(p|31) = -1.$ Then $-3$ can be found by continued fractions, here is the entire Lagrange cycle: $$\langle 1, 10, -6 \rangle , \; \langle -6, 2, 5 \rangle , \; \langle 5, 8, -3 \rangle , \; \langle -3, 10, 2 \rangle , \; \langle 2, 10, -3 \rangle , \; \langle -3, 8, 5 \rangle , \; \langle 5, 2, -6 \rangle , \; \langle -6, 10, 1 \rangle , \; \langle 1, 10, -6 \rangle.$$ –  Will Jagy Dec 31 '12 at 20:18