Skip to main content
MathOverflow

Return to Answer

primes dividing the discriminant
Source Link
Will Jagy
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

I recommend a book by Duncan A. Buell called "Binary Quadratic Forms."

First, we discard the case where $d$ is a square. In such a case the forms represent entire arithmetic progressions. For example, with $x^2 - y^2$ and $d = 4$ we get $ (n+1)^2 - n^2 = 2 n + 1.$ Or, with $x y$ and $d=1,$ we have $n \cdot 1 = n.$

Note that we always require $$ d \equiv 0,1 \pmod 4.$$

For what primes $p > 0$ is there any form, reduced or not, having $p$ as a "diagonal" coefficient? For one thing, the prime 2 is not represented if $ d \equiv 5 \pmod 8,$ otherwise it is. With odd $p$ that does not divide $d,$ this answer is essentially quadratic reciprocity. We are demanding $$ \beta^2 \equiv d \pmod p $$ If we can solve this, that is $(d | p) = 1,$ we can choose either $ b = \beta$ or $ b = \beta + p$ to arrange $$ b^2 \equiv d \pmod {4p}. $$ But this is the condition $$ b^2 = d + 4 p c, $$ or $ b^2 - 4 p c = d .$

Note that we also have the form $$ (-p)x^2 + b x y + (-c) y^2 $$ with the same discriminant. So as long as you do not ask whether the two forms are equivalent we are in good shape.

Finally, you asked about "reduced" forms, which is to say coefficients $$ \langle a,b,c \rangle $$ and discriminant $d$ with $$ 0 < b < \sqrt{d}, \; \; \mbox{and} \; \; \sqrt{d} - b < 2 | a | < \sqrt{d} + b. $$ Here we have Lagrange's theorem that any represented number $n$ occurs as a coefficient of $x^2$ in a reduced form if $$ | n | < \; \frac{1}{2} \; \sqrt{d}, $$ so you have a simple answer for small primes. It is a bit of a toss-up if you have $$ \frac{1}{2} \; \sqrt{d} < p < \; \sqrt{d} .$$ Here I suggest creating a form and then checking the entire cycle of reduced forms in its equivalence class. The recipe for doing exactly that is on pages 21-23 of Buell.

EDIT: I'm afraid I was not sufficiently cautious as relates to primes that divide the discriminant. It is true that 2 is represented when $ d \equiv 1 \pmod 8$ and not when $ d \equiv 5 \pmod 8.$ But as soon as we have even discriminant there is need for care. The trouble is the existence of imprimitive forms, $$ \langle a,b,c \rangle $$ with $$ \gcd(a,b,c) \neq 1 .$$ What follows is from page 75 in Buell. If $ d \equiv 0 \pmod {16}$ then 2 is not represented by a primitive form, but if $ d \equiv 8 \pmod {16}$ it is, by the class of the primitive (but not reduced) form $$ \langle 2,0,\frac{-d}{8} \rangle .$$ If $ d \equiv 4 \pmod {16}$ then 2 is not represented by a primitive form, but if $ d \equiv 12 \pmod {16}$ it is, by the class of the primitive (but probably not reduced) form $$ \langle 2,2,\frac{4-d}{8} \rangle. $$ Alright, now that I see Buell's Theorem 4.24, the case of odd primes $p$ dividing the discriminant is comparatively clean. If $$ p^2 | d$$ then only imprimitive forms represent $p.$ If $$ p \parallel d$$ then $p$ is represented by a primitive form, either $$ \langle p,0,\frac{-d}{4 p} \rangle $$ if $d$ is even, or $$ \langle p,p,\frac{p^2-d}{4 p} \rangle $$ if $d$ is odd. My comments about the size of $p$ and reduced forms still apply.

I recommend a book by Duncan A. Buell called "Binary Quadratic Forms."

First, we discard the case where $d$ is a square. In such a case the forms represent entire arithmetic progressions. For example, with $x^2 - y^2$ and $d = 4$ we get $ (n+1)^2 - n^2 = 2 n + 1.$ Or, with $x y$ and $d=1,$ we have $n \cdot 1 = n.$

Note that we always require $$ d \equiv 0,1 \pmod 4.$$

For what primes $p > 0$ is there any form, reduced or not, having $p$ as a "diagonal" coefficient? For one thing, the prime 2 is not represented if $ d \equiv 5 \pmod 8,$ otherwise it is. With odd $p$ that does not divide $d,$ this answer is essentially quadratic reciprocity. We are demanding $$ \beta^2 \equiv d \pmod p $$ If we can solve this, that is $(d | p) = 1,$ we can choose either $ b = \beta$ or $ b = \beta + p$ to arrange $$ b^2 \equiv d \pmod {4p}. $$ But this is the condition $$ b^2 = d + 4 p c, $$ or $ b^2 - 4 p c = d .$

Note that we also have the form $$ (-p)x^2 + b x y + (-c) y^2 $$ with the same discriminant. So as long as you do not ask whether the two forms are equivalent we are in good shape.

Finally, you asked about "reduced" forms, which is to say coefficients $$ \langle a,b,c \rangle $$ and discriminant $d$ with $$ 0 < b < \sqrt{d}, \; \; \mbox{and} \; \; \sqrt{d} - b < 2 | a | < \sqrt{d} + b. $$ Here we have Lagrange's theorem that any represented number $n$ occurs as a coefficient of $x^2$ in a reduced form if $$ | n | < \; \frac{1}{2} \; \sqrt{d}, $$ so you have a simple answer for small primes. It is a bit of a toss-up if you have $$ \frac{1}{2} \; \sqrt{d} < p < \; \sqrt{d} .$$ Here I suggest creating a form and then checking the entire cycle of reduced forms in its equivalence class. The recipe for doing exactly that is on pages 21-23 of Buell.

I recommend a book by Duncan A. Buell called "Binary Quadratic Forms."

First, we discard the case where $d$ is a square. In such a case the forms represent entire arithmetic progressions. For example, with $x^2 - y^2$ and $d = 4$ we get $ (n+1)^2 - n^2 = 2 n + 1.$ Or, with $x y$ and $d=1,$ we have $n \cdot 1 = n.$

Note that we always require $$ d \equiv 0,1 \pmod 4.$$

For what primes $p > 0$ is there any form, reduced or not, having $p$ as a "diagonal" coefficient? With odd $p$ that does not divide $d,$ this answer is essentially quadratic reciprocity. We are demanding $$ \beta^2 \equiv d \pmod p $$ If we can solve this, that is $(d | p) = 1,$ we can choose either $ b = \beta$ or $ b = \beta + p$ to arrange $$ b^2 \equiv d \pmod {4p}. $$ But this is the condition $$ b^2 = d + 4 p c, $$ or $ b^2 - 4 p c = d .$

Note that we also have the form $$ (-p)x^2 + b x y + (-c) y^2 $$ with the same discriminant. So as long as you do not ask whether the two forms are equivalent we are in good shape.

Finally, you asked about "reduced" forms, which is to say coefficients $$ \langle a,b,c \rangle $$ and discriminant $d$ with $$ 0 < b < \sqrt{d}, \; \; \mbox{and} \; \; \sqrt{d} - b < 2 | a | < \sqrt{d} + b. $$ Here we have Lagrange's theorem that any represented number $n$ occurs as a coefficient of $x^2$ in a reduced form if $$ | n | < \; \frac{1}{2} \; \sqrt{d}, $$ so you have a simple answer for small primes. It is a bit of a toss-up if you have $$ \frac{1}{2} \; \sqrt{d} < p < \; \sqrt{d} .$$ Here I suggest creating a form and then checking the entire cycle of reduced forms in its equivalence class. The recipe for doing exactly that is on pages 21-23 of Buell.

EDIT: I'm afraid I was not sufficiently cautious as relates to primes that divide the discriminant. It is true that 2 is represented when $ d \equiv 1 \pmod 8$ and not when $ d \equiv 5 \pmod 8.$ But as soon as we have even discriminant there is need for care. The trouble is the existence of imprimitive forms, $$ \langle a,b,c \rangle $$ with $$ \gcd(a,b,c) \neq 1 .$$ What follows is from page 75 in Buell. If $ d \equiv 0 \pmod {16}$ then 2 is not represented by a primitive form, but if $ d \equiv 8 \pmod {16}$ it is, by the class of the primitive (but not reduced) form $$ \langle 2,0,\frac{-d}{8} \rangle .$$ If $ d \equiv 4 \pmod {16}$ then 2 is not represented by a primitive form, but if $ d \equiv 12 \pmod {16}$ it is, by the class of the primitive (but probably not reduced) form $$ \langle 2,2,\frac{4-d}{8} \rangle. $$ Alright, now that I see Buell's Theorem 4.24, the case of odd primes $p$ dividing the discriminant is comparatively clean. If $$ p^2 | d$$ then only imprimitive forms represent $p.$ If $$ p \parallel d$$ then $p$ is represented by a primitive form, either $$ \langle p,0,\frac{-d}{4 p} \rangle $$ if $d$ is even, or $$ \langle p,p,\frac{p^2-d}{4 p} \rangle $$ if $d$ is odd. My comments about the size of $p$ and reduced forms still apply.

Source Link
Will Jagy
Will Jagy
  • 25.7k
  • 2
  • 65
  • 121

I recommend a book by Duncan A. Buell called "Binary Quadratic Forms."

First, we discard the case where $d$ is a square. In such a case the forms represent entire arithmetic progressions. For example, with $x^2 - y^2$ and $d = 4$ we get $ (n+1)^2 - n^2 = 2 n + 1.$ Or, with $x y$ and $d=1,$ we have $n \cdot 1 = n.$

Note that we always require $$ d \equiv 0,1 \pmod 4.$$

For what primes $p > 0$ is there any form, reduced or not, having $p$ as a "diagonal" coefficient? For one thing, the prime 2 is not represented if $ d \equiv 5 \pmod 8,$ otherwise it is. With odd $p$ that does not divide $d,$ this answer is essentially quadratic reciprocity. We are demanding $$ \beta^2 \equiv d \pmod p $$ If we can solve this, that is $(d | p) = 1,$ we can choose either $ b = \beta$ or $ b = \beta + p$ to arrange $$ b^2 \equiv d \pmod {4p}. $$ But this is the condition $$ b^2 = d + 4 p c, $$ or $ b^2 - 4 p c = d .$

Note that we also have the form $$ (-p)x^2 + b x y + (-c) y^2 $$ with the same discriminant. So as long as you do not ask whether the two forms are equivalent we are in good shape.

Finally, you asked about "reduced" forms, which is to say coefficients $$ \langle a,b,c \rangle $$ and discriminant $d$ with $$ 0 < b < \sqrt{d}, \; \; \mbox{and} \; \; \sqrt{d} - b < 2 | a | < \sqrt{d} + b. $$ Here we have Lagrange's theorem that any represented number $n$ occurs as a coefficient of $x^2$ in a reduced form if $$ | n | < \; \frac{1}{2} \; \sqrt{d}, $$ so you have a simple answer for small primes. It is a bit of a toss-up if you have $$ \frac{1}{2} \; \sqrt{d} < p < \; \sqrt{d} .$$ Here I suggest creating a form and then checking the entire cycle of reduced forms in its equivalence class. The recipe for doing exactly that is on pages 21-23 of Buell.