Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Neil Sloane asked me about commands in computer languages to find the (positive) primes represented by indefinite binary quadratic forms. So I wrote something in C++ that works. This is for the OEIS, these primes go into sequences... Note that, within a few hours, another guy had run the tables much higher with a one-line Maple command. Some days it does not pay to get up.

I thought of one I really do not understand. Discriminant $205$ has four classes of forms, $$ \langle 1, 13, -9 \rangle, \; \langle -1, 13, 9 \rangle, \; \langle 3, 13, -3 \rangle, \; \langle -3, 13, 3 \rangle. $$

The third and fourth are opposites so in the same genus, although distinct. The first two are in the principal genus, but they are not opposites, one is $-1$ times the other; in particular, they get diffeent positive primes, although both do residues $\pmod 5$ and $\pmod {41}.$ For $\langle 1, 13, -9 \rangle$ we get $$ 1,5,59,131,139,241,269,271,359,409, \ldots, $$ while for $\langle -1, 13, 9 \rangle$ we get $$ 31,41,61,251,349,379,389,401,419,431, \ldots. $$

For positive forms, low class number, there are polynomials, such as in Cox's book, such that primes represented by the principal form are those for which the polynomial factors a certain way. For a prime $p \equiv 1 \pmod 3,$ Gauss showed that $2$ is a cubic residue if an only if $p = u^2 + 27 v^2.$ Jacobi showed that $3$ is a cubic residue if an only if $p = u^2 + uv + 61 v^2.$ All I found in Henri Cohen's tables was the fact that $\mathbb Q(\sqrt {205})$ has class number $2$ and $L_K = \mathbb Q(\sqrt 5),$ appendix 12C on pages 533 and 534. See related information at IT'S A LINK.

Let's see, $34$ is the smallest number where it is a surprise that there is no solution to $x^2 - 34 y^2 = -1.$ The smallest such odd number is $205,$ as there is no solution to $x^2 - 205 y^2 = -1.$ For prime $p \equiv 1 \pmod 4,$ there is always a solution to $x^2 - p y^2 = -1.$ Proof in Mordell's book. Anyway, this is why $\langle 1, 13, -9 \rangle, \; \langle -1, 13, 9 \rangle$ are distinct classes.

So, that is the question, can I distinguish the represented (positive) primes by factoring some polynomial mod these primes?

share|improve this question

1 Answer 1

up vote 13 down vote accepted

Class field theory promises such a polynomial (more properly, such a number field $H$, since a polynomial generating $H$ might have to err on the first few primes, though in our case it turns out there's a polynomial with no exceptional primes). The proof is effective, though the recipe is often hard to carry out. So I attempted an end run by asking this database for number fields of degree $8$ and discriminant $205^4$, and was rewarded with $$ x^8 + 15 x^6 + 48 x^4 + 15 x^2 + 1, $$ which generates an unramified normal extension $H \, / \, {\bf Q}(\sqrt{205})$ with the right Galois group. This polynomial matches your list exactly: the gp code

   f = factormod(x^8+15*x^6+48*x^4+15*x^2+1, p)[,1];

returns your 5, 59, 131, 139, 241, 269, 271, 359, 409, and then continues 541, 569, 599, 661, 701, 761, 859, 881, 911, 941, still in exact agreement with the list of primes represented by $u^2 + 13uv - 9v^2$.

[added later] That gp code checks whether all factors of $P_8(x) := x^8 + 15 x^6 + 48 x^4 + 15 x^2 + 1 \bmod p$ have degree $1$. Since the polynomial is Galois, it would have been sufficient to check that one factor is linear:

   if(poldegree(factormod(x^8+15*x^6+48*x^4+15*x^2+1, p)[1,1])==1, print(p))

(I "cheated" a tad by excluding $p=2$, which is a factor of the discriminant of $P_8$ but not of the number field.) The Galois group of $P_8$ is dihedral, so one can find a quartic polynomial $P_4$ with the same Galois closure that factors completely mod $p$ iff $P_8$ does; such a polynomial was exhibited by NAME_IN_CAPS answering the follow-up Question 171846. Alternatively, we know already that $p$ is (either $5$ or) a quadratic residue of both $5$ and $41$, so by Quadratic Reciprocity $5$ and $41$ have square roots mod $p$, which means that $p$ factors completely in ${\bf Q}(\sqrt{5},\sqrt{41})$. And indeed $x^2$ generates that field and equals (some conjugate of) $$ -\frac14 (15 + 3 \sqrt{5} + \sqrt{41} + \sqrt{205}); $$ so you can also test whether $p$ is represented by $u^2 + 13uv - 9v^2$ by computing $\sqrt{5} \bmod p$ and $\sqrt{41} \bmod p$ (if they don't exist then there's no representation), and then testing whether $-(15 + 3 \sqrt{5} + \sqrt{41} + \sqrt{205})$ is a square mod $p$.

share|improve this answer
For the very similar discriminant 221 and $x^2 + 13 x y - 13 y^2, $ I was surprised to find that $$ f(x) = x^8 + x^6 - 4 x^5 - 38 x^4 - 2 x^3 + 123 x^2 -34 x + 17, $$ has a repeated root $\pmod {101},$ although still linear factors, seven of them with one of them squared. Is that allowed? After that it is always 8 roots. This time the primes are $ 17,101,103,127,179,251,263,373,433,$ –  Will Jagy Jun 15 at 20:47
For 221, the quartic $$ x^4 + x^3 + x^2 + 2 x + 4 $$ behaves well –  Will Jagy Jun 15 at 20:57
The repeated root mod $101$ is an example of my warning that "a polynomial generating [the Hilbert class field] $H$ might have to err on the first few primes" if $H$ has no generator $x$ such that ${\bf Z}[x]$ is the full ring of integers of $H$. A better choice for this purpose is $x^8 + 34 x^6 + 83 x^4 + 34 x^2 + 1$, which has spurious repeated roots only mod $2$ and $3$ (and as it happens no linear factors modulo either of these primes). Then $x+1/x$ generates a quartic isomorphic with the one you found with coefficients $1,1,1,2,4$. –  Noam D. Elkies Jun 15 at 22:14
Cool. Thanks, Noam. That does look much better. I found my degree eight on that website you mentioned, by putting in $221^4.$ Actually, the first time it thought i meant 2214 and complained. i decided it was better to multiply out the number. –  Will Jagy Jun 15 at 22:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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