# Solve: $x^2-py^2=q$

Solve $$x^2-py^2=q$$ for integers $x,y$, here $p,q$ are both given prime numbers.

It's obvious that $p,q$ should satisfy $(\frac{p}{q})=(\frac{q}{p})=1,$ here $(\frac{p}{q})$ is the Jacobi symbol. However,this is not sufficient,for example,$(\frac{11}{37})=(\frac{37}{11})=1$,but $x^2-37y^2=11$ has no integer solution.

Addition:Maybe it's too hard to analysis this problem in general,one can analysis it in case of $p=37$.What's the necessary and sufficient condition so that $x^2-37y^2=q$ has integer solutions?It's known that the class number of $Q(\sqrt{37})$ is $1$.

• This is a tough question to answer in general. You need to consider the fact that $\mathbb{Q}(\sqrt{p})$ may have ring of integers that is NOT a UFD. When it is then your condition suffices! – fretty May 4 '13 at 14:24
• @fretty,thanks,but what will happen when it's not a UFD? – Next May 4 '13 at 14:34
• The point is that being able to write $x^2 - py^2 = q$ is the same as $q$ splitting in $\mathbb{Z}[\sqrt{p}]$. If you are lucky enough for this ring to be the ring of integers of $\mathbb{Q}(\sqrt{p})$ and that it is a UFD then the splitting behaviour is determined entirely by the Legendre symbol criterion. However if it is not a UFD (but is the ROI) then you must turn to prime ideals and notice that $q$ splitting is not enough but also the fact that it "splits into principal ideals" too...something which is more specific! Class field theory lets you study this question generally. – fretty May 4 '13 at 14:37
• Alternatively from a brute force point of view you can use QR to find congruence conditions for those Legendre symbols to be 1 and find out which classes do NOT work by testing an example of a prime from each. – fretty May 4 '13 at 14:41

This kind of question is answered by looking at how $q$ factors in a precise abelian extension of $\Bbb Q(\sqrt p)$.

In your example, $\Bbb Q(\sqrt p)$ has class number $1$. Its ring of integer is $\Bbb Z\left[\frac{1+\sqrt {37}}2\right]$, and the norm quadratic form is $x^2+xy-9y^2$. $11$ splits in this quadratic extension, so it is a norm, as $11 = 4^2+4-9$.

Now, your quadratic form has discriminant $4*37$. It is the norm form of the lattice $\Bbb Z[\sqrt{37}]$, so the question is : When do the primes that split, give primes that land on this lattice (up to multiplication by a unit) ?

A quick computation shows that the units are generated by $6 \pm \sqrt {37}$, and importantly, they are in $\Bbb Z[\sqrt{37}]$, and $(6+\sqrt{37})(6- \sqrt{37}) = -1$. Hence, modulo $(2)$ and the two infinite places, the units are $\{\overline 1 \}\times\{\pm 1\}^2$. This also shows that $-1$ is represented by $x^2+xy-9y^2$ and $x^2-37y^2$, and that the positive represented primes are the same are the negative represented primes.

The elements of $\Bbb Z[\sqrt {37}]$ are those congruent to $0,1$ modulo the ideal $(2)$. Those who are prime are then (except $2$) those congruent to $1$ modulo $(2)$, and so we are looking for the primes which are in the trivial class of $G = \left(\Bbb Z\left[\frac{1+\sqrt {37}}2\right]/(2)\right)^* \approx \Bbb Z/3 \Bbb Z$, and which is the ray class group of conductor $(2)\infty_1\infty_2$ (quotienting by the units removes the sign components of the infinite places).

Now, as a reality check, the primes of norm $11$ are $\frac{9 \pm \sqrt{37}}2 \equiv \frac{1 \pm \sqrt{37}}2 \neq 1 \pmod {(2)}$

According to class field theory, the primes that land in the trivial class (and so are representable as $x^2-37y^2$) are those that split in a particular abelian cubic extension $K$ of $\Bbb Q(\sqrt {37})$. If by chance $K$ is abelian over $\Bbb Q$, then we know from Kronecker's theorem that this is equivalent to a modular condition on the original prime, and it should be obvious when looking back at $x^2-37y^2$ mod $4*37$.

Sadly this is not the case : $x^2-37y^2$ can take every odd value modulo $4$, and so the Galois group of $K$ over $\Bbb Q$ is not abelian, but it is $S_3$. So there should be a cubic polynomial $P(X) = X^3+aX+b$, such that $x^2-37y^2$ represents a prime $q$ if and only if $P$ splits into linear factors modulo $q$.

If $P(X) = X^3-4X-2$, it turns out that the class field is the splitting field of $P$, and for $p \neq 37$, we have the equivalences :

• $P(X)$ splits in $3$ distinct linear factor if and only if $p = x^2-37y^2$
• $P(X)$ has $1$ linear factor if and only if $p$ isn't a square modulo $37$
• $P(X)$ doesn't factor at all if and only if $p = 4x^2+6xy-7y^2$
• Excuse me, some points are still beyond my understanding. First, why $Z[\dfrac{1+\sqrt{37}}{2}]/(2)\approx Z/3Z$? Secondly, I cannot see how one deduces that the galois group of $K$ over $Q$ is not abelian, by saying that $x^2-37y^2$ can take every odd value modulo $4$. Finally, now that we know that the class-field of the particular congruence subgroup is a cubic extension, are there methods we could apply to find out that extension explicitly? Namely, could we determine explicitly the polynomial $P(X)$? Thanks in advance for any clarifications. – awllower May 8 '13 at 8:45
• Say $u = (1+\sqrt{37})/2$ (meaning $u^2=u+9$). Then $\Bbb Z[u]/(2) = \{\overline{0},\overline{1},\overline{u},\overline{1+u}\}$, which is isomorphic to $\Bbb F_4$. Its group of invertible has $3$ elements, hence is isomorphic to $\Bbb Z/3 \Bbb Z$. Or you can simply check that $u^3 = u(u+9) \equiv u^2+u = 2u+9 \equiv 1 \pmod 2$. – mercio May 8 '13 at 9:46
• Suppose $K/\Bbb Q$ is abelian and contained a cyclotomic extension $\Bbb Q(\zeta_m)$. Then, the positive rational primes that split in $K$ are those who are in a certain subgroup of $(\Bbb Z/m \Bbb Z)^*$. We also know that they are the primes that can be written as $x^2-37y^2$. If you study locally the possible values of $x^2-37y^2$ mod $p^l$, you get that it has to be a square mod $37$, and it takes every possible value modulo all the other prime powers, especially modulo $2^l$ (the only one where it could possibly miss some values). And so you would get $K = \Bbb Q(\sqrt{37})$. Contradiction – mercio May 8 '13 at 10:05
• @awllower : finally, explicit class field theory is difficult. You would have to look for integers $a,b$ such that the discriminant of $X^3+aX+b$ is $37$ modulo a square, and then check if it works out, I guess. It would be easier with $\Bbb Q(\sqrt{-3})$ since then you would look for how you can adjoin cubic roots. – mercio May 8 '13 at 10:11
• Thanks. I shall ponder more to figure out, if I can, what that particular field is, in order to enhance my poor understanding of this marvellous subject. Thanks again.:) – awllower May 8 '13 at 16:09

$$\left(\frac{37}{11}\right)=1\implies$$ there exists an integer such that

$$z^2\equiv 37\pmod {11}$$

If $z=\frac xy$ where $(y,37)=1$ $$x^2\equiv37y^2\pmod {11}\iff x^2-37y^2=11a$$ for some integer $a$ not necessarily $=1$

• how can we prove that $a$ cannot equal 1? – Next May 4 '13 at 14:32
• @Sophie, I'm not saying that. I mean the Quadratic Reciprocity does not ensure $a=1$ – lab bhattacharjee May 4 '13 at 14:34