# Quadratic residues and representations of integers by a binary quadratic form

Let $F = ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. We say $D = b^2 - 4ac$ is the discriminant of $F$. Let $m$ be an integer. If $m = ax^2 + bxy + cy^2$ has a solution in $\mathbb{Z}^2$, we say $m$ is represented by $F$. If $m = ax^2 + bxy + cy^2$ has a solution $(s, t)$ such that gcd$(s, t) = 1$, we say $m$ is properly represented by $F$.

My question Is there any other proof of the following theorem other than the Gauss's original proof? Since this theorem is important, I think having different proofs is meaningful.

It would be also nice if some one would post a modern form of the Gauss's proof, since not everybody can have an easy access to the book.

Theorem(Gauss: Disquisitiones Arithmeticae, art.154) Let $ax^2 + bxy + cy^2$ be a binary quadratic form over $\mathbb{Z}$. Let $D$ be its discriminant. Let $m$ be an integer. Suppose $m$ is properly represented by $ax^2 + bxy + cy^2$. Then $D$ is a quadratic residue modulo $4m$.

EDIT The Gauss's DA is notorious for its difficult read. This was even so for his contemporaries. Dirichlet devoted a lot of time to simplify DA. There is a legend that Dirichlet always carried DA in his travels. Gauss's proof often uses a "magic" equation which seems to come out of nowhere. One of the reasons is that, as he wrote, he could not afford elaborate proofs due to lack of enough available pages for an economical reason. So I think it would be nice if there is a more natural proof.

• Doesn't he prove this in his book? – Pedro Tamaroff Sep 4 '12 at 23:20
• What is frowned upon is that you don't give any hint of what you really want. I don't think there are many people that are going to read this and go "OK, let's find some proof, using some theory, that Makoto will like." Most seem to be cool with Gauss' proof. Maybe you can answer what we ask you so you can get what you want. "But do you want what: a more contemporary proof? Shorter? Clearer? More convoluted? Using other theory? Avoiding certain axioms? Let's put down some variables!" – Pedro Tamaroff Sep 4 '12 at 23:54
• I confess I am greatly saddened by the 6 downvotes to this question. I cannot imagine why anyone would downvote it. Please be more constructive. If you think the question needs improvement then please say why and/or help to improve it. – Bill Dubuque Sep 5 '12 at 1:21
• @PeterTamaroff it is Gauss composition, which takes two forms of the same discriminant and gives a third. It respects "equivalence." On the level of equivalence classes of forms, it makes a group. The difficult part of that proof is associativity. Dirichlet made a big simplification with his "united" pairs of forms. Many modern books do Gauss composition, some better than others. I like Buell. For one thing he does full detail on positive forms and indefinite forms in the same volume. – Will Jagy Sep 5 '12 at 2:15
• @SteveD My question is not of that sort. I took for granted that my question should be of interest for anyone who has the basic knowledge of elementary number theory. – Makoto Kato Sep 5 '12 at 3:36

"In this section, we'll deal primarily with bivariate functions of $x$ and $y$ of the form:

$$\tag 1 f(x,y)=ax^2 + 2bxy + cy^2$$(...) When we're not interested in the indeterminates $x,y$ we'll refer to $(1)$ as $(a,b,c)$

We'll say a number $M$ is represented in the form $(a,b,c)$ if $x,y$ can be given values such that $M=f(x,y)$.

Theorem. If the number $M$ can be represented in the form $(a,b,c)$ such that $(x,y)=1$, then $b^2-ac$ will be a quadratic residue modulus $M$.

Proof Let $m,n$ be the values of the indeterminates, that is $$am^2 + 2bmn + cn^2 = M$$ and take $\mu$ and $\nu$ such that $m\mu+n\nu=1$. Then by multipying out we can easily show that

$$\left( {a{m^2} + 2bmn + c{n^2}} \right)\left( {a{\nu ^2} - 2b\nu \mu + c{\mu ^2}} \right) =$$

$${\left( {\mu \left( {mb + nc} \right) - \nu \left( {ma + nb} \right)} \right)^2} - \left( {{b^2} - ac} \right){\left( {m\mu + n\nu } \right)^2}$$

or $$M\left( {a{\nu ^2} - 2b\nu \mu + c{\mu ^2}} \right) = {\left( {\mu \left( {mb + nc} \right) - \nu \left( {ma + nb} \right)} \right)^2} - \left( {{b^2} - ac} \right)$$

Thus it will be the case$${b^2} - ac \equiv {\left( {\mu \left( {mb + nc} \right) - \nu \left( {ma + nb} \right)} \right)^2}\bmod M$$ as we claimed.

• I don't know how much simpler it can get, really. – Pedro Tamaroff Sep 5 '12 at 0:10
• Do you think you could come up with the proof by yourself? As for me, I don't. – Makoto Kato Sep 5 '12 at 0:19
• Is this now a matter of personal achievement? – Pedro Tamaroff Sep 5 '12 at 0:42
• @PeterTamaroff the identity is Gauss composition, probaly the simplest occurrence. Taking $\Delta = b^2 - a c,$ the "principal form" of that discriminant i the one that represents $1,$ here $\langle 1,0, -\Delta \rangle.$ You wrote $\langle a,2b,c \rangle \circ \langle a, -2b, c \rangle = \langle 1,0, -\Delta\rangle$ with the relevant values of the "variables" included. Versions exist with the middle coefficient odd. See Duncan A. Buell, Binary Quadratic Forms. Page 57 for "united" forms, pages 61-65 in general. The forms become a group, historically the first nontrivial one. – Will Jagy Sep 5 '12 at 1:47
• @Peter See Will's comment on composition of forms. A more readable modern presentation of Gauss is George B. Mathews Theory of Numbers (free via Google Books). One can also clarify related proofs by translating them into the (linear!) language of ideals / modules, see here. – Bill Dubuque Sep 5 '12 at 2:38

By the proposition of this question, there exist integers $l, k$ such that $ax^2 + bxy + cy^2$ and $mx^2 + lxy + ky^2$ are equivalent. Hence $D = l^2 - 4mk$. Hence $D \equiv l^2$ (mod $4m$).

Let $f(x, y) = ax^2 + bxy + cy^2$. Suppose $m = ax^2 + bxy + cy^2$ has a solution $(p, r)$ such that gcd$(p, r) = 1$. There exist integers $s, q$ such that $ps - qr = 1$. Suppose $f(pu + qv, ru + sv) = m'u^2 + luv + kv^2$, where $u, v$ are indeterminate variables. Then

$m' = ap^2 + bpr + cr^2$

$l = 2apq + b(ps + qr) + 2crs$

$k = aq^2 + bqs + cs^2$

Hence $m' = m$.

Since $D = l^2 - 4mk$, $D \equiv l^2$ (mod $4m$).