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

  • 1
    $\begingroup$ 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! $\endgroup$ – fretty May 4 '13 at 14:24
  • $\begingroup$ @fretty,thanks,but what will happen when it's not a UFD? $\endgroup$ – lsr314 May 4 '13 at 14:34
  • 5
    $\begingroup$ 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. $\endgroup$ – fretty May 4 '13 at 14:37
  • $\begingroup$ 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. $\endgroup$ – 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$
  • $\begingroup$ 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. $\endgroup$ – awllower May 8 '13 at 8:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – mercio May 8 '13 at 9:46
  • 1
    $\begingroup$ 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 $\endgroup$ – mercio May 8 '13 at 10:05
  • 1
    $\begingroup$ @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. $\endgroup$ – mercio May 8 '13 at 10:11
  • $\begingroup$ 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.:) $\endgroup$ – 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.