Can you write 67 in the form $x^2 + 7 y^2$? By brute force, we find $67 = 2^2 + 7 \times 3^2$, so the answer is yes. But what if I ask the same question about a larger prime like 1234577?

It turns out $1234577 = x^2 + 7 y^2$ if and only if 7 is quadratic residue modulo 1234577. Using quadratic reciprocity, we find that $(7|1234577) = -(1|7) = -1$, so this time there are no solutions. We’ll need a bit of theory to explain why.

A binary quadratic form is written $[a, b, c]$ and refers to the expression $a x^2 + b x y + c y^2$. We are interested in what numbers can be represented in a given quadratic form.

If $gcd(a, b, c)$ (the divisor of a quadratic form) is 1 then the quadratic form is primitive.

Representations $x, y$ with $gcd(x, y) = 1$ are primitive representations. We need only study these as scaling up by a constant factor is trivial.

Completing the square, we find:

$4a(a x^2 + b x y + c y^2) = (2a x + b y)^2 - d y^2$

where $d = b^2 - 4a c$. We call $d$ the discriminant.

If $d = 0$, then the quadratic form is a perfect square. This case is trivial.

If $d \lt 0$ then we must have $a c \gt 0$, implying $a, c$ have the same sign. From the above equality we see if $a \gt 0$ then the form is nonnegative for any $x, y$. We call such a form positive definite. Similarly, if $a \lt 0$ then the form is negative definite.

If $d \gt 0$ then a little experimentation shows the form takes negative and positive values. Such a form is termed indefinite.

Equivalent forms

Given a form, if we swap $x$ and $y$ then the resulting form represents the same numbers. In a sense they are really the same form. There are less trivial ways to change a form so it represents the same numbers. If we replace $x$ with $x+y$, then $x = u - v, y = v$ represents the same number that $x = u, y = v$ did in the original form.

More generally, let $T$ be a 2x2 matrix with integer entries of determinant $\pm 1$ (an integral unimodular matrix). We state some facts that are tedious to prove, though not difficult.

Each quadratic form $[a, b, c]$ can be written as the matrix:

$A = \begin{pmatrix} a & b/2 \\ b/2 & c \end{pmatrix}$

(apply $T$ to the vector $x, y$). Then

$T^- A T = \begin{pmatrix} a' & b'/2 \\ b'/2 & c' \end{pmatrix}$

for some $a', b', c'$. We denote this matrix by $A'$. We write $[a, b, c] ~ [a', b', c']$; this relation is an equivalence relation.

Equivalent forms represent the same integers, have the same divisor and discriminant. Also, equivalent representations of an integer $n$ (namely T(u, v) = (u', v') for some integral unimodular matrix $T$ where $u, v$ and $u', v'$ are the values we substitute in the forms) have the same divisor.

Reduced forms

By applying appropriate transformations, we can always find a form $[a, b, c]$ equivalent to any given form such that $-|a| \lt b \le |a| \lt |c|$ or $0 \le b \le |a| = |c|$. Such a form is called a reduced form.

These conditions imply $b^2 \le |a c| \le |d|/3$.

Also, the bounds imply there are only finitely many reduced forms, and hence the number of equivalence classes of forms for a given discriminant $d$ is finite. We call this number the class number of the discriminant $d$.

Theorem: Every equivalence class of positive definite binary quadratic forms contains exactly one reduced form. The indefinite case is trickier.

Principal forms

For a discriminant $d$, set $k = 0$ if $d = 0 \bmod 4$ and $k = 1$ if $d = 1 \bmod 4$. Then

$[1, k, (k^2 - d)/4 ]$

is the principal form of discriminant $d$. It is a reduced form. The equvalence class containing it is called the principal class of forms of discriminant $d$.

Power tools

Theorem: An integer $n$ is primitively representable by a quadratic form $[a, b, c]$ if and only if $[a, b, c] ~ [n, b', c']$ for some $b', c'$.

Theorem: A nonzero integer $n$ is primitively representable by a form of discriminant $d$ if and only if

$x^2 = d \bmod 4 |n|$

for some $x$.

Proof. If $n$ is primitive representable, by the previous theorem there exists a form $[n, b', c']$ that primitively represents $n$. The condition follows immediately from $d = b'^2 - 4 n c'$.

Conversely, the condition implies $b'^2 - 4 n c' = d$ for some integers $b', c'$, and 1, 0 is a primitive representation of $n$ by the form $[n, b', c']$.∎.

[Something seems to be missing from the book I got this from, as it claims when the class number of a positive definite form is one, then it represents a number if and only if this condition holds. But take $x^2 + 3y^2$, the only reduced form with $d = -12$. Then $2^2 = -12 \pmod{8}$, yet $2$ cannot be represented by $x^2 + 3y^2$. In the proof, we get $[n, b', c'] = [2, 2, 2]$; this form is not primitive. Fortunately, we usually consider prime $n$ so the form is primitive.]