Exercise 3.7.3 (Number of proper representations of $n$ by $x^2 + xy + y^2$)

Proof.

(a)

First we search the reduced forms $(a,b,c)$ of discriminant $-3$. By Theorem 3.19, $0<a\le \sqrt{-d∕3}=1$, thus $a=1$. Since $d=-3=b^2-4\mathit{ac}$, $b$ is odd, and $-|a|<b\le |a|$, so we obtain $b=1$, and $c=(3+b^2)∕(4a)=1$. This shows that the only reduced form of discriminant $-3$ is $f(x,y)=x^2+\mathit{xy}+y^2$, which is primitive. Therefore any form with discriminant $-3$ is properly equivalent to $f(x,y)=x^2+\mathit{xy}+y^2$ (Theorem 3.18), and $H(-3)=h(-3)=1$.

(b)

Let $n$ be any positive integer. By Theorems 3.13 and 3.17, $n$ is properly represented by $f$ if and only if $-3\equiv u^2(\mathit{mod}4n)$ for some integer $u$.

Since $-3$ is not a square modulo $8$, $n$ is odd, so the decomposition of $n$ in prime factors is of the form $n=3^{\alpha }\underset{p\in A}{\prod <!--\; FUNCTION\; APPLICATION\; -->}{p}^{\beta }(p)(\alpha \ge 0,\beta (p)>0)$, where the primes $p\in A$ are odd. Note that $-3\equiv 9=3^2(\mathit{mod}12)$, but $-3\equiv 33(\mathit{mod}36)$ is not a square modulo $36$ (the squares modulo $36$ are $0,1,4,9,13,16,25,28$). If $\alpha \ge 2$, then $-3\equiv u^2(\mathit{mod}36)$. This is a contradiction, so $\alpha =0$ or $\alpha =1$.

If $p\in A$ is an odd prime divisor of $n$, then $-3\equiv u^2(\mathit{mod}p)$, thus $\left(\frac{-3}{p}\right)=1$. Moreover, by the Law of Quadratic Reciprocity,

$$\begin{array}{llll}\hfill \left(\frac{-3}{p}\right)& =\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)& \hfill & \\ \hfill & ={(-1)}^{\frac{p-1}{2}}{(-1)}^{\frac{3-1}{2}\cdot \frac{p-1}{2}}\left(\frac{p}{3}\right)& \hfill & \\ \hfill & =\left(\frac{p}{3}\right).& \hfill & \end{array}$$

Therefore $\left(\frac{p}{3}\right)=1$, thus $p\equiv 1(\mathit{mod}3)$. We have proven that if a positive integer $n$ is properly represented by $f$, then $n=3^{\alpha }\underset{p\in A}{\prod <!--\; FUNCTION\; APPLICATION\; -->}{p}^{\beta (p)}(\beta (p)>0)$, where $\alpha =0$ or $\alpha =1$, and all the primes $p\in A$ are of the form $3k+1$.

Conversely, suppose that $n=3^{\alpha }\underset{p\in A}{\prod <!--\; FUNCTION\; APPLICATION\; -->}{p}^{\beta (p)}(\beta (p)>0)$, where $\alpha =0$ or $\alpha =1$, and all the primes $p\in A$ are of the form $3k+1$.

For every $p\in A$, $\left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)=1$, thus there is some integer $u_p\not\equiv 0(\mathit{mod}p)$ such that $-3\equiv u_p^2(\mathit{mod}p)$. Put $g(x)=x^2+4\in \mathbb{Z}[x]$. Then $g(x)\equiv 0(\mathit{mod}p)$ has a solution $u_p$, such that $g^{\prime }(u_p)=2u_p\not\equiv 0(\mathit{mod}p)$. By the Hensel’s Lemma (Theorem 2.23), this solution lifts to a unique solution $v_p$ modulo $p^{\beta (p)}$, so that $-3\equiv v_p^2(\mathit{mod}{p}^{\beta (p)})$. Moreover, since $-3\equiv 0(\mathit{mod}3)$ is a square modulo $3$, the congruence $x^2\equiv -3(\mathit{mod}{3}^a)$ has a solution $v_3$. By the Chinese Remainder Theorem, there is some integer $v$ such that $v\equiv 1(\mathit{mod}4),v\equiv v_p(mod{p}^{\beta }(p))(p\in A),v\equiv v_3(mod{3}^{\alpha })$. Then $v^2\equiv -3(\mathit{mod}{p}^{\beta (p)})(p\in A),v^2\equiv -3(mod{3}^{\alpha })$, so $v^2\equiv -3(\mathit{mod}n)$, and $v^2\equiv 1\equiv -3(\mathit{mod}4)$, thus $-3\equiv v^2(\mathit{mod}4n)$. This proves that $n$ is properly represented by $f(x,y)=x^2+\mathit{xy}+y^2$.

A positive integer $n$ is properly represented by $f$ if and only if $n$ is of the form $3^{\alpha }\underset{p\in A}{\prod <!--\; FUNCTION\; APPLICATION\; -->}{p}^{\beta (p)}(\beta (p)>0)$, where $\alpha =0$ or $\alpha =1$, and all the primes $p\in A$ are of the form $3k+1$.

(c)

Suppose now that $n$ is of this form, so that $r_f(n)>0$. By Theorem 3.26, since $a=b=c$, $w(f)=6$, and by Theorem 3.27, $$\begin{array}{lll}\hfill r_f(n)=6H_f(n).& & \hfill \text{(1)}\end{array}$$

Here $H_f(n)$ is the number of integers $h$, $0\le h<2n$ such that $h^2\equiv -3(\mathit{mod}4n)$ (the condition $n{x}^2+\mathit{hxy}+\frac{h^2-d}{4n}\stackrel{+}{\sim }{x}^2+\mathit{xy}+y^2$ is always satisfied by part (a), since the discriminant of $n{x}^2+\mathit{hxy}+\frac{h^2-d}{4n}$ is $d=-3$). Thus $H_f(n)=N_{-3}(n)$, where $N_{-3}(n)$ denotes the number of integers $h$ for which $h^2\equiv -3(\mathit{mod}4n)$ and $0\le h<2n$ (see p. 175).

Since $h$ is a solution of the congruence $u^2\equiv -3(\mathit{mod}4n)$ if and only if $h+2n$ is a solution, it follows that $N_{-3}(n)$ is precisely one-half the total number of solutions of the congruence $u^2\equiv -3(\mathit{mod}4n)$. To summarize:

$$\begin{array}{lll}\hfill H_f(n)=\frac{1}{2}\mathrm{Card}\{u\in [[0,4n[[\mid u^2\equiv -3(\mathit{mod}4n)\}.& & \hfill \end{array}$$

As in Theorem 2.20, put $N(4n)=\mathrm{Card}\{u\in [[0,4n[[\mid u^2\equiv -3(\mathit{mod}4n)\}$, so $N(4n)$ is the number of solutions of the congruence $x^2\equiv -3(\mathit{mod}4n)$, and

$$\begin{array}{lll}\hfill H_f(n)=\frac{1}{2}N(4n).& & \hfill \text{(2)}\end{array}$$

By Theorem 2.20,

$$\begin{array}{lll}\hfill N(4n)=N(4)N(3^{\alpha })\underset{p\in A}{\prod }N(p^{\beta (p)}).& & \hfill \end{array}$$

If $p\in A$, $p\equiv 1(\mathit{mod}3)$, so $\left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)=1$, thus $N(p)=2$, and by Hensel’s Lemma, $N(p^{\beta (p)})=2$. Moreover $N(3)$ is the number of solutions of $x^2\equiv -3\equiv 0(\mathit{mod}3)$, thus $N(3)=1$. The number of solutions of $x^2\equiv -3\equiv 1(\mathit{mod}4)$ is $N(4)=2$. Then

$$\begin{array}{lll}\hfill N(4n)=2\cdot 2^{|A|}.& & \hfill \text{(3)}\end{array}$$

If $s=|A|$ is the number of distinct primes $p\equiv 1(\mathit{mod}3)$ that divide $n$, then equations (1), (2) and (3) give

$$r_f(n)=6\cdot 2^s.$$