AN AMAZING IDENTITY OF GAUSS AND JENKINS’ LEMMA

Abstract

We prove several finite product-sum identities involving the q-binomial coefficient, one of which is used to prove an amazing identity of Gauss. We then use this identity to evaluate certain quadratic Gauss sums and, together with known properties of quadratic Gauss sums, we prove the quadratic reciprocity law for the Jacobi symbol. We end our article with a new proof of Jenkins’ lemma, a lemma analogous to Gauss’ lemma. This article aims to show that Gauss’ amazing identity and the properties of quadratic Gauss sums are sufficient to establish the quadratic reciprocity law for the Jacobi symbol.

1 Introduction

We begin with a short discussion on finite sum-product identities involving the q-binomial coefficient. We prove four such identities in Section 2, two of which are due to Gauss and are evaluations of special values of the Rogers–Szegö polynomials. The other two identities, (2.4) and (2.5), are possibly new.

In Section 3, we prove an amazing identity of Gauss (3.3) using (2.4).

In Section 4, we evaluate certain quadratic Gauss sums using identity (3.3). This proof is not new and we are essentially filling in the details of the proof given by Jenkins [6].

Next, in Section 5, we reproduce a proof of another identity on quadratic Gauss sums (5.1) which can be found in several classical textbooks. We chose to reproduce this proof and the proof of (3.3) to make this article as self-contained as possible. These two results then lead to a new proof of the quadratic reciprocity law for the Jacobi symbol.

Jenkins [6] gave a different proof of the quadratic reciprocity law for the Jacobi symbol using a formula for the Jacobi symbol. We will refer to Jenkins’ formula, which is an analogue of Gauss’ lemma, as Jenkins’ lemma. In Section 6, we give a new proof of Jenkins’ lemma using identities (3.3) and (5.1).

2 The q-binomial coefficient

Let q be a complex variable. Let $(a;q)_0=1$ and

$$ \begin{align*}(a;q)_n=\prod_{k=1}^n (1-aq^{k-1}), \quad n\in \mathbf Z^+.\end{align*} $$

The q-binomial coefficient is given by

$$ \begin{align*}\bigg[\begin{matrix} n \\ k\end{matrix}\bigg]_q =\begin{cases} \dfrac{(q;q)_n}{(q;q)_k(q;q)_{n-k}} &\text{if } n, k \text{ are integers}, 0\leq k\leq n,\\ \qquad 0 &\text{otherwise.}\end{cases}\end{align*} $$

The Rogers–Szegö polynomial is defined by

$$ \begin{align*}h_n(x,q) =\sum_{j=0}^n \bigg[\begin{matrix} n \\ \,j\end{matrix}\bigg]_q x^{{\kern1.5pt}j}.\end{align*} $$

We note that as $q\to 1$ , $h_n(x,q)\to (1+x)^n$ . However, $h_n(x,q)$ does not seem to have representations in terms of products except for a few special cases such as the two evaluations

(2.1) $$ \begin{align} h_{2n}(-1,q) =\sum_{j=0}^{2n} \bigg[\begin{matrix} 2n \\ \,j\end{matrix}\bigg]_q (-1)^{\,j} =(q;q^2)_n\end{align} $$

and

(2.2) $$ \begin{align} h_n(q,q^2) =\sum_{j=0}^n \bigg[\begin{matrix} n \\ \,j\end{matrix}\bigg]_{q^2} q^{{\kern1.5pt}j} =(-q;q)_n,\end{align} $$

which were both discovered by Gauss.

Identities (2.1) and (2.2) were proved by Gauss [3, Sections 6–9] using recurrence relations. It turns out that these identities can also be established using Euler’s identity [4, Theorem 349],

(2.3) $$ \begin{align} \sum_{j=0}^\infty \dfrac{x^{{\kern1.5pt}j}}{(q;q)_j} = \dfrac{1}{(x;q)_\infty}, \end{align} $$

where

$$ \begin{align*}|q|<1 \quad\text{and}\quad (a;q)_\infty =\prod_{k=1}^\infty (1-aq^{k-1}). \end{align*} $$

Using (2.3), we find that

$$ \begin{align*}\bigg(\sum_{k=0}^\infty \dfrac{(-x)^k}{(q;q)_k} \bigg)\bigg(\sum_{\ell=0}^\infty \dfrac{x^\ell}{(q;q)_\ell} \bigg) =\dfrac{1}{(-x;q)_\infty}\dfrac{1}{(x;q)_\infty} = \dfrac{1}{(x^2;q^2)_\infty} =\sum_{n=0}^\infty \dfrac{x^{2n}}{(q^2;q^2)_n}.\end{align*} $$

Comparing the coefficients of $x^{2n}$ ,

$$ \begin{align*}\sum_{j=0}^{2n} \dfrac{(-1)^{\,j}}{(q;q)_j}\dfrac{1}{(q;q)_{2n-j}} = \dfrac{(q;q^2)_n}{(q;q)_{2n}},\end{align*} $$

which is equivalent to (2.1).

Similarly, by (2.3),

$$ \begin{align*}\bigg(\sum_{k=0}^\infty \dfrac{(qx)^k}{(q^2;q^2)_k} \bigg)\bigg(\sum_{\ell=0}^\infty \dfrac{x^\ell}{(q^2;q^2)_\ell} \bigg) &=\dfrac{1}{(xq;q^2)_\infty}\dfrac{1}{(x;q^2)_\infty} = \dfrac{1}{(x;q)_\infty} \\ &=\sum_{n=0}^\infty \dfrac{x^n}{(q;q)_n} =\sum_{n=0}^\infty \dfrac{(-q;q)_n}{(q^2;q^2)_n}x^n.\end{align*} $$

Comparing the coefficients of $x^n$ ,

$$ \begin{align*}\sum_{j=0}^n \dfrac{q^{{\kern1.5pt}j}}{(q^2;q^2)_j}\dfrac{1}{(q^2;q^2)_{n-j}} = \dfrac{(-q;q)_n}{(q^2;q^2)_n},\end{align*} $$

which is equivalent to (2.2).

There is a ‘companion’ of (2.3) [4, Theorem 348] given by

$$ \begin{align*} \sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)/2}x^{{\kern1.5pt}j}}{(q;q)_j} = \prod_{k=1}^\infty (1+xq^{k-1}). \end{align*} $$

Since

$$ \begin{align*} \bigg(\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)/2}(-x)^{\,j}}{(q;q)_j}\bigg) \bigg(\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)/2}x^{{\kern1.5pt}j}}{(q;q)_j}\bigg) &= \prod_{k=1}^\infty (1-xq^{k-1})(1+xq^{k-1})\\ &=\prod_{k=1}^\infty (1-x^2q^{2k-2}) =\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)}(-x^2)^{\,j}}{(q^2;q^2)_j},\end{align*} $$

we find, by comparing the coefficients of $x^{2n}$ , that

(2.4) $$ \begin{align} \sum_{j=0}^{2n}\bigg[\begin{matrix} 2n \\ j \end{matrix}\bigg]_q (-1)^{n-j}q^{(n-j)^2}=(q;q^2)_n. \end{align} $$

Similarly, since

$$ \begin{align*}\bigg(\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)}(qx)^{\,j}}{(q^2;q^2)_j}\bigg)\bigg(\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)}x^{{\kern1.5pt}j}}{(q^2;q^2)_j}\bigg) &=\prod_{k=1}^\infty (1+xq^{2k-2})(1+xq^{2k-1})\\ &=\prod_{k=1}^\infty (1+xq^{k-1}) =\sum_{j=0}^\infty \dfrac{q^{{\kern1.5pt}j(\,j-1)/2}x^{{\kern1.5pt}j}}{(q;q)_j},\end{align*} $$

we find, by comparing the coefficients of $x^n$ , that

(2.5) $$ \begin{align} \sum_{j=0}^n\bigg[\begin{matrix} n \\ j \end{matrix}\bigg]_{q^2} q^{(n-2j+1)(n-2j)/2}=(-q;q)_n. \end{align} $$

3 Cyclotomic units and an identity of Gauss

It is known that if $(t,m)=1$ , then $e^{2\pi i t/m}$ is a primitive mth root of unity. We will use $\zeta _m$ to denote any primitive mth root of unity. It is often mentioned that as $q\to 1$ ,

$$ \begin{align*}\bigg[\begin{matrix} n \\ k\end{matrix}\bigg]_q \to \begin{pmatrix} n \\ k\end{pmatrix},\end{align*} $$

the usual binomial coefficient. It is, however, more interesting to note that if we let $q=\zeta _{n+1}$ , then

(3.1) $$ \begin{align} \bigg[\begin{matrix} n \\ k\end{matrix}\bigg]_{\zeta_{n+1}} = \prod_{j=1}^k \dfrac{1-\zeta_{n+1}^{n-j+1}}{1-\zeta_{n+1}^j} =\prod_{j=1}^k \dfrac{1-\zeta_{n+1}^{-j}}{1-\zeta_{n+1}^j}= \dfrac{(-1)^k}{\zeta_{n+1}^{k(k+1)/2}}.\end{align} $$

This observation is due to Gauss [3, Section 12]. Using (3.1), Gauss deduced the following result from (2.1).

Theorem 3.1. Let n be a positive integer and $(t,2n+1)=1$ . Then,

(3.2) $$ \begin{align} \phantom{\hspace{-36pt}}\sum_{j=0}^{2n} e^{2\pi i tj^2/(2n+1)} &= \prod_{k=1}^n (\zeta_{2n+1}^{2k-1}-\zeta_{2n+1}^{-(2k-1)}) \end{align} $$

(3.3) $$ \begin{align} &\qquad\qquad\quad\, =(2i)^{n}\prod_{k=1}^{n} \sin \bigg(\dfrac{2t(2k-1)\pi}{(2n+1)}\bigg). \end{align} $$

Instead of deducing (3.3) from (2.1) as Gauss did, we will now derive (3.3) from (2.4).

Proof. Let $q=\zeta _{2n+1}$ . From (2.4) and (3.1),

(3.4) $$ \begin{align} (-1)^n\sum_{j=0}^{2n} \dfrac{\zeta_{2n+1}^{(n-j)^2}}{\zeta_{2n+1}^{j(\,j+1)/2}} = \prod_{k=1}^n (1-\zeta_{2n+1}^{2k-1}).\end{align} $$

Now if $\zeta _{2n+1}$ is a primitive $(2n+1)$ th root of unity, then $\zeta _{2n+1}^{2}$ is also a primitive ${(2n+1)}$ th root of unity. Therefore, we find from (3.4), after multiplying both sides by $(-1)^n$ , that

$$ \begin{align*}\sum_{j=0}^{2n} \dfrac{\zeta_{2n+1}^{2(n-j)^2}}{\zeta_{2n+1}^{j(\,j+1)}} = \prod_{k=1}^n (\zeta_{2n+1}^{2(2k-1)}-1).\end{align*} $$

This implies that

$$ \begin{align*}\zeta_{2n+1}^{-1-3-\cdots - 2n-1}\sum_{j=0}^{2n}\zeta_{2n+1}^{2n^2+j^2-4nj-j} = \prod_{k=1}^n (\zeta_{2n+1}^{2k-1}-\zeta_{2n+1}^{-(2k-1)}).\end{align*} $$

Using the identity $1+3+\cdots +(2n-1)=n^2$ and the fact that $\zeta _{2n+1}^{-4nj-j}=\zeta _{2n+1}^{-2nj}$ , we deduce that

$$ \begin{align*} \sum_{j=0}^{2n} \zeta_{2n+1}^{(n-j)^2} = \prod_{k=1}^n (\zeta_{2n+1}^{2k-1}-\zeta_{2n+1}^{-(2k-1)}).\end{align*} $$

Observing that

$$ \begin{align*}\sum_{j=0}^{2n} \zeta_{2n+1}^{(n-j)^2}=\sum_{j=0}^{2n} \zeta_{2n+1}^{j^2}\end{align*} $$

since the set of least nonnegative residues of $n-j$ modulo $2n$ for $0\leq j\leq 2n$ is $\{0,1,2,\ldots , 2n\}$ , we deduce (3.2). Letting $\zeta _{2n+1}=e^{2\pi i t/(2n+1)}$ with $(t,2n+1)=1$ and rewriting the right-hand side of (3.2) using $\displaystyle \sin x ={(e^{ix}-e^{-ix})}/{2i}$ completes the proof of (3.3).

In a similar manner, from (2.2) and (3.1), we derive an analogue of (3.3), namely,

(3.5) $$ \begin{align} \sum_{j=0}^{n-1} (-1)^{{\kern1.5pt}j}e^{\pi i j^2/n} = e^{-\pi i(n-1)/4} 2^{n-1}\prod_{k=1}^{n-1} \cos \dfrac{k\pi}{n}.\end{align} $$

4 The quadratic Gauss sum

Definition 4.1. Let s and t be positive integers. Define

$$ \begin{align*}g(s,t)=\sum_{j=0}^{t-1} e^{2\pi i s j^2/t}.\end{align*} $$

The function $g(s,t)$ is sometimes referred to as the quadratic Gauss sum (see [1, page 177, Problem 16], [2, page 12]). It turns out that one can evaluate $g(1,m)$ for any odd positive integer m.

Theorem 4.2. Let m be an odd positive integer. Then,

(4.1) $$ \begin{align} g(1,m)=\sum_{j=0}^{m-1} e^{2\pi i j^2/m} & =\begin{cases} \sqrt{m} \quad &\text{if }m\equiv 1\pmod{4}, \\ i\sqrt{m}\quad &\text{if } m\equiv 3\pmod{4}.\end{cases} \\ &= i^{((m-1)/2)^2}\sqrt{m}.\notag\end{align} $$

Proofs of (4.1) can be found in many books. See [1, Ch. 9, Section 10] or [2, Lemma 1.2.1]. We will give a proof of Theorem 4.2 using (3.3). This proof is sketched in Jenkins’ article [6].

We need the following lemma.

Lemma 4.3. Let m be an odd positive integer. Then,

$$ \begin{align*} \frac{\sin{mx}}{\sin x}=(2i)^{m-1}\prod_{j=1}^{m-1}\sin\bigg(x-\dfrac{2\pi j}{m}\bigg). \end{align*} $$

Lemma 4.3 is a consequence of the identity

$$ \begin{align*}x^m-1=(x-1)\prod_{j=1}^{m-1} (x-\zeta_m^{2j}),\end{align*} $$

where we observed that $\{\zeta _m^j \mid 1\leq j\leq (m-1)\}=\{\zeta _m^{2j} \mid 1\leq j\leq (m-1)\}$ since m is an odd positive integer and $\zeta _m^2$ is also a primitive mth root of unity.

Proof of Theorem 4.2

Letting $x\to 0$ in Lemma 4.3, we deduce that

$$ \begin{align*} (-1)^{m-1}(2i)^{m-1}\prod_{j=1}^{m-1}\sin\bigg(\dfrac{2\pi j}{m}\bigg)=m. \end{align*} $$

This implies that

(4.2) $$ \begin{align}\bigg|(2i)^{m-1}\prod_{j=1}^{m-1} \sin\bigg(\dfrac{2\pi j}{m}\bigg)\bigg|=m. \end{align} $$

Next, write

$$ \begin{align*}\prod_{j=1}^{m-1} \sin\bigg(\dfrac{2\pi j}{m}\bigg) &= \prod_{j=1}^{(m-1)/2} \sin\bigg(\dfrac{2\pi (2j-1)}{m}\bigg) \sin\bigg(\dfrac{2\pi (2j)}{m}\bigg) \\ &= (-1)^{(m-1)/2}\prod_{j=1}^{(m-1)/2} \sin\bigg(\dfrac{2\pi (2j-1)}{m}\bigg) \sin\bigg(\dfrac{2\pi (m-2j)}{m}\bigg)\\ & =(-1)^{(m-1)/2}\prod_{j=1}^{(m-1)/2} \sin^2\bigg(\dfrac{2\pi (2j-1)}{m}\bigg), \end{align*} $$

where we have used $\sin y=-\sin (2\pi -y)$ in the second equality. By (4.2),

$$ \begin{align*}\bigg|(2i)^{(m-1)}\prod_{j=1}^{(m-1)/2} \sin^2\bigg(\dfrac{2\pi (2j-1)}{m}\bigg)\bigg|=m, \end{align*} $$

which implies that

$$ \begin{align*}(2i)^{(m-1)/2} \prod_{j=1}^{(m-1)/2} \sin\bigg(\dfrac{2\pi(2j-1)}{m}\bigg) = u_m\sqrt{m},\end{align*} $$

where $u_m$ is some power of i. By comparing both sides and using the fact that

$$ \begin{align*}\sin (2\pi (2j-1)/m) <0\quad\text{if } j>m/4+1/2,\end{align*} $$

we deduce immediately that if $m=8k+1$ , then

$$ \begin{align*}u_m= i^{4k} (-1)^{2k}=1.\end{align*} $$

Similarly, if $m=8k+3, 8k+5$ and $8k+7$ , then $u_m=i,1$ and i, respectively. Therefore,

(4.3) $$ \begin{align} (2i)^{(m-1)/2} \prod_{j=1}^{(m-1)/2} \sin\bigg(\dfrac{2\pi(2j-1)}{m}\bigg) = i^{((m-1)/2)^2}\sqrt{m}. \end{align} $$

Substituting (4.3) into (3.3) with $t=1$ and $m=2n+1$ completes the proof of Theorem 4.2.

Trigonometric identities related to (4.3) can also be found in [9, Section 51].

Corollary 4.4. Let a and b be two positive odd integers. Then,

(4.4) $$ \begin{align} \dfrac{g(1,ab)}{g(1,a)g(1,b)} = (-1)^{(a-1)(b-1)/4}. \end{align} $$

Proof. From (4.1), we deduce that

$$ \begin{align*}\dfrac{g(1,ab)}{g(1,a)g(1,b)} = i^{((ab-1)/2)^2-((a-1)/2)^2-((b-1)/2)^2}.\end{align*} $$

Since

$$ \begin{align*}\dfrac{a-1}{2}+\dfrac{b-1}{2}\equiv \dfrac{ab-1}{2}\pmod{2}, \end{align*} $$

it follows that

$$ \begin{align*}\bigg(\dfrac{a-1}{2}\bigg)^2+\bigg(\dfrac{b-1}{2}\bigg)^2+\dfrac{(a-1)(b-1)}{2}-\bigg(\dfrac{ab-1}{2}\bigg)^2 \equiv 0\pmod{4},\end{align*} $$

and this completes the proof of (4.4).

Note that in (4.1), we evaluate the Gauss sum for odd positive integers. We end this section by giving an analogue of (4.1) for even positive integers, but with the corresponding Gauss sum ‘weighted’ by $(-1)^{\,j}$ . Letting $x\rightarrow -1$ in the identity

$$ \begin{align*}\dfrac{x^{2n}-1}{x^2-1} =\prod_{\substack{j=1 \\ j\neq n,2n}}^{2n} (x-\zeta_{2n}^j),\end{align*} $$

gives

(4.5) $$ \begin{align} 2^{n-1}\prod_{j=1}^{n-1} \cos\dfrac{\pi j}{2n} =\sqrt{n}. \end{align} $$

Using (4.5) and (3.5), we deduce the following analogue of (4.1).

Theorem 4.5. If n is any positive integer, then

$$ \begin{align*} \sum_{j=0}^{n-1} (-1)^{\,j} e^{\pi i j^2/n} =e^{-\pi i (n-1)/4}\sqrt{n}.\end{align*} $$

5 The Jacobi symbol and the quadratic Gauss sum

Definition 5.1. Let p be an odd prime. The Legendre symbol $\big(\frac{a}{p}\big)_L$ is defined by

$$ \begin{align*} \displaystyle\bigg(\dfrac{a}{p}\bigg)_L=\begin{cases} 0 & \text{if }(a,p)\neq 1, \\ 1 & \text{if }x^2\equiv a\pmod{p} \text{ is solvable,} \\ -1 & \text{otherwise.}\end{cases}\end{align*} $$

Definition 5.2. The Jacobi symbol $\big(\frac{a}{b}\big)_J$ is defined for an odd positive integer b by

$$ \begin{align*}\displaystyle\bigg(\dfrac{a}{b}\bigg)_J =\begin{cases} 1 \quad &\text{if }b=1,\\ {\displaystyle \prod_{j=1}^k \bigg(\dfrac{a}{p_j}\bigg)_L^{\alpha_j}} \quad &\text{if } \displaystyle b=\prod_{j=1}^k p_j^{\alpha_j}.\end{cases}\end{align*} $$

We will write $\big(\frac{\cdot}{b}\big)$ to represent $\big(\frac{\cdot}{b}\big)_J$ . Our aim is to prove the following theorem.

Theorem 5.3. Let m be any positive odd integer and a be an integer such that ${(a,m)=1}$ . Then,

(5.1) $$ \begin{align} g(a,m)=\bigg(\dfrac{a}{m}\bigg) g(1,m).\end{align} $$

Theorem 5.3 and its proof can be found in [2, Theorem 1.5.2]. The proof uses (4.1) and an automorphism $\sigma _m$ of the cyclotomic field $\mathbf Q(\zeta _k)$ which sends $\zeta _k$ to $\zeta _k^m.$ The proof we present here follows closely the proof given in Hua’s book [5, Section 7.5] and Lang’s book [8, Ch. 4, Section 3]. We will prove two lemmas before proving Theorem 5.3.

Let a and b be two relatively prime positive integers. The Chinese remainder theorem implies that if an arithmetic function $f(\,j)$ satisfies $f(\,j+ab)=f(\,j)$ , then

$$ \begin{align*}\sum_{j=0}^{ab-1} f(\,j)=\sum_{h=0}^{a-1}\sum_{k=0}^{b-1} f(ak+bh).\end{align*} $$

Now, since for any positive integer c, the function $e^{2\pi i cj^2/ab}$ is a function of j with period $ab$ , we find that

$$ \begin{align*}g(c,ab)& = \sum_{j=0}^{ab-1} e^{2\pi i cj^2/(ab)} =\sum_{h=0}^{a-1}\sum_{k=0}^{b-1} e^{2\pi i c(ak+bh)^2/(ab)}\\ &=\sum_{h=0}^{a-1} e^{2\pi i cbh^2/a}\sum_{k=0}^{b-1}e^{2\pi i cak^2/b}=g(cb,a)g(ca,b).\end{align*} $$

This yields the first lemma.

Lemma 5.4. Let $a, b$ and c be positive integers with $(a,b)=1$ . Then,

$$ \begin{align*} g(ca,b)g(cb,a) =g(c,ab). \end{align*} $$

Our next task is to establish the second lemma, which is a special case of Theorem 5.3.

Lemma 5.5. Let a be any integer, $\alpha $ be any positive integer and p be an odd prime with $(a,p)=1$ . Then,

(5.2) $$ \begin{align} g(a,p^\alpha) =\bigg(\dfrac{a}{p^\alpha}\bigg) g(1,p^\alpha).\end{align} $$

Proof. For $\alpha =1$ , we observe that if $(\,j,p)=1$ , then

$$ \begin{align*}\dfrac{1}{2}\bigg(1+\bigg(\dfrac{j}{p}\bigg)\bigg) = \begin{cases} 1 \quad &\text{if } x^2\equiv j\pmod{p} \text{ is solvable,}\\ 0 \quad &\text{otherwise.}\end{cases}\end{align*} $$

Note that we may then write

(5.3) $$ \begin{align}g(a,p) &= \sum_{j=0}^{p-1} e^{2\pi i a j^2/p} = 1+ 2\sum_{j=1}^{(p-1)/2} e^{2\pi i a j^2/p} \notag\\ &=1+2\sum_{\ell=1}^{p-1} \dfrac{1}{2}\bigg(1+\bigg(\dfrac{\ell}{p}\bigg)\bigg) e^{2\pi i a\ell/p}\notag\\ &=1+\sum_{\ell=1}^{p-1} e^{2\pi i a\ell/p} + \sum_{\ell=1}^{p-1}\bigg(\dfrac{\ell}{p}\bigg) e^{2\pi i a\ell/p}.\end{align} $$

Now, since

(5.4) $$ \begin{align} 1+\sum_{\ell=1}^{p-1} e^{2\pi i a\ell/p} = 0\end{align} $$

and

(5.5) $$ \begin{align}\sum_{\ell=1}^{p-1}\bigg(\dfrac{\ell}{p}\bigg) e^{2\pi i a\ell/p}= \sum_{\ell=1}^{p-1}\bigg(\dfrac{a^2\ell}{p}\bigg) e^{2\pi i a\ell/p}= \bigg(\dfrac{a}{p}\bigg) \sum_{\ell=1}^{p-1}\bigg(\dfrac{a\ell}{p}\bigg) e^{2\pi i a\ell/p},\end{align} $$

we conclude from (5.3), (5.4) and (5.5) that

$$ \begin{align*}g(a,p)=\bigg(\dfrac{a}{p}\bigg)g(1,p)\end{align*} $$

and (5.2) is true for $\alpha =1$ . We will next show that (5.2) is true for $\alpha =2$ . We will first show that

$$ \begin{align*} g(a,p^\alpha) = p g(a,p^{\alpha-2}). \end{align*} $$

This follows from the fact that the set of integers $\{0,1,\ldots , p^{\alpha }-1\}$ can be written as $\{s+tp^{\alpha -1} \mid 0\leq s\leq p^{\alpha -1}-1, 0\leq t\leq p-1\}.$ Therefore,

$$ \begin{align*} g(a,p^\alpha) &= \sum_{s=0}^{p^{\alpha-1}-1}\sum_{t=0}^{p-1} e^{2\pi i a (s+tp^{\alpha-1})^2/p^{\alpha}}\\ &=\sum_{s=0}^{p^{\alpha-1}-1} e^{2\pi i a s^2/p^\alpha}\sum_{t=0}^{p-1}e^{4 \pi i a st/p} \\ &=p \sum_{\substack{s=0 \\ p|s}}^{p^{\alpha-1}-1} e^{2\pi i a s^2/p^\alpha} = p g(a,p^{\alpha-2}). \end{align*} $$

If we follow the above argument with $\alpha =2$ , we conclude that $g(a,p^2)= p$ , which means that $g(a,p^2)$ is independent of a and we may write

$$ \begin{align*}g(a,p^2) =\bigg(\dfrac{a}{p^2}\bigg)g(1,p^2),\end{align*} $$

which is (5.2) for $\alpha =2$ .

Suppose (5.2) is true for all $1\leq k<\alpha $ . Then,

$$ \begin{align*} g(a,p^\alpha)=pg(a,p^{\alpha-2}) = p \bigg(\dfrac{a}{p^{\alpha-2}}\bigg)g(1,p^{\alpha-2}) =\bigg(\dfrac{a}{p^{\alpha}}\bigg)g(1,p^\alpha).\\[-45pt] \end{align*} $$

We are now ready to prove Theorem 5.3.

Proof of Theorem 5.3

Let $m=p_1^{\alpha _1} p_2^{\alpha _2}\cdots p_k^{\alpha _k}.$ We prove the theorem by induction on k. Write $m=m'p_k^{\alpha _k}.$ Then, by Lemma 5.4,

$$ \begin{align*} g(a,m) &= g(a,m' p_k^{\alpha_k}) =g(am', p_k^{\alpha_k})g(ap_k^{\alpha_k},m') \\ &=\bigg(\dfrac{am'}{p_k^{\alpha_k}}\bigg) g(1, p_k^{\alpha_k}) \bigg(\dfrac{ap_k^{\alpha_k}}{m'}\bigg)g(1,m')\\ &=\bigg(\dfrac{a}{m'p_k^{\alpha_k}}\bigg) \bigg(\dfrac{m'}{p_k^{\alpha_k}}\bigg)g(1,p_k^{\alpha_k})\bigg(\dfrac{p_k^{\alpha_k}}{m'}\bigg)g(1,m')\\ &=\bigg(\dfrac{a}{m}\bigg) g(m',p_k^{\alpha_k})g(p_k^{\alpha_k},m')=\bigg(\dfrac{a}{m}\bigg)g(1,m).\\[-42pt] \end{align*} $$

We are now ready to prove the main part of the quadratic reciprocity law for the Jacobi symbol.

Theorem 5.6. Let a and b be two positive odd integers with $(a,b)=1$ . Then,

$$ \begin{align*}\bigg(\dfrac{a}{b}\bigg)\bigg(\dfrac{b}{a}\bigg)=(-1)^{(a-1)(b-1)/4}.\end{align*} $$

Proof. Note that by Theorem 5.3, Lemma 5.4 and Corollary 4.4,

$$ \begin{align*} \bigg(\dfrac{a}{b}\bigg)\bigg(\dfrac{b}{a}\bigg) = \dfrac{g(a,b)g(b,a)}{g(1,b)g(1,a)} = \dfrac{g(1,ab)}{g(1,b)g(1,a)} =(-1)^{(a-1)(b-1)/4}.\\[-42pt] \end{align*} $$

Remark 5.7. Theorem 5.6 and all the identities for the quadratic Gauss sum leading up to (5.1) are known results that appear at different places in [5, 8]. We have seen here that these topics are connected via Gauss’ amazing identity (3.3).

6 Jenkins’ lemma

The proof of Theorem 5.6 given in the previous section is inspired by Jenkins [6]. Jenkins’ proof involves (3.3), (4.1) but not (5.1). Instead, Jenkins uses a lemma analogous to a generalisation of Gauss’ lemma. We now state Jenkins’ lemma.

Definition 6.1. For positive integers N and a, let $r_N(a)$ denote the least nonnegative residue of a modulo N.

Lemma 6.2. Let m be an odd positive integer and a be any integer with $(a,m)\,{=}\,1$ . Let $S=\{2j-1 \mid 1\leq j\leq (m-1)/2\}$ . Let $T=\{r_m(a(2j-1)) \mid 1\leq j\leq (m-1)/2\}$ and $\nu (a,m)$ be the number of integers in T but not in S. Then,

$$ \begin{align*}\bigg(\dfrac{a}{m}\bigg) =(-1)^{\nu(a,m)}.\end{align*} $$

We observe that $\nu (a,m)$ counts the number of even integers in T. We now give a proof of Lemma 6.2 as a corollary of (3.3) and (5.1).

Proof. From (3.3), we deduce that

(6.1) $$ \begin{align} g(a,m) &=(2i)^{(m-1)/2} \prod_{j=1}^{(m-1)/2} \sin(2\pi a(2j-1)/m) \notag \\[-1.5pt] &=(-1)^{\nu(a,m)} (2i)^{(m-1)/2} \prod_{j=1}^{(m-1)/2} \sin(2\pi (2j-1)/m) \\[-1.5pt] &=(-1)^{\nu(a,m)}g(1,m),\notag \end{align} $$

where we use that the fact that a ‘minus’ sign is introduced when $r_m(a(2j-1))$ is even, which explains the appearance of $(-1)^{\nu (a,m)}$ on the right-hand side of (6.1). The proof is completed by using (5.1).

The proof of Lemma 6.2 in the case when $m=p$ is an odd prime is easier and similar to the proof of Gauss’ lemma, which states that if $S'=\{\,j \mid 1\leq j\leq (p-1)/2\}$ , $T'=\{r_p(aj) \mid 1\leq j\leq (p-1)/2\}$ and $\nu '(a,p)$ is the number of integers in $T'$ that are not in $S'$ , then

$$ \begin{align*}\bigg(\dfrac{a}{p}\bigg)_L =(-1)^{\nu'(a,p)}.\end{align*} $$

For completion, we will state this special case and give a direct proof.

Lemma 6.3. Let p be an odd prime and a be any integer with $(a,p)=1$ . Let

$$ \begin{align*}S=\{2j-1 \mid 1\leq j\leq (p-1)/2\}, \quad T=\{r_p(a(2j-1)) \mid 1\leq j\leq (p-1)/2\}\end{align*} $$

and $\nu (a,p)$ be the number of integers in T but not in S. Then,

$$ \begin{align*}\bigg(\dfrac{a}{p}\bigg)_L =(-1)^{\nu(a,p)}.\end{align*} $$

Proof. Let $\nu =\nu (a,p)$ ,

$$ \begin{align*}E=\{t \mid t\in T \text{ is even}\}=\{e_1,e_2,\ldots , e_\nu\}\end{align*} $$

and

$$ \begin{align*}O=\{t \mid t\in T\cap S\}=\{o_1,o_2,\ldots , o_{(p-1)/2-\nu}\}.\end{align*} $$

Let $O'=\{p-e \mid e\in E\}.$ We claim that $O\cup O'=S.$ First note that all integers in O are distinct. For if $as\equiv as'\pmod {p}$ with $s,s'\in S$ , then $s=s'$ . Similarly, all integers in E are distinct. Next, suppose $o=p-e\in O\cap O'$ for some $o\in O$ and $e\in E$ . Suppose $o=as $ and $e=as'$ for some $s,s'\in S.$ Then, $as\equiv p-as'\pmod {p}$ , which implies that $s+s'\equiv 0\pmod {p}$ . This implies that $s+s'=0$ since $s,s'$ are odd positive integers less than $p-2$ . However, these are both impossible because $s+s'>0$ . Thus, $O\cup O'=S$ and therefore,

$$ \begin{align*}1\cdot 3 \cdots (p-2) \equiv a^{(p-1)/2} (-1)^{\nu(a,p)} (1 \cdot 3 \cdots (p-2) ) \pmod{p},\end{align*} $$

which implies that

$$ \begin{align*}a^{(p-1)/2} \equiv (-1)^{\nu(a,p)}\pmod{p}\end{align*} $$

and the proof is completed using Euler’s criterion [1, Theorem 9.2].

Remark 6.4. The generalisation of Lemma 6.3 is an analogue of the Gauss–Schering lemma [10], which is a generalisation of Gauss’ lemma with the prime p replaced by any odd positive integer m and the Legendre symbol replaced by the Jacobi symbol. Kuroki and Katayama [7] showed that if we replace S and $S'$ by any set $S^*$ such that $S^*\subset \{\,j \mid 1\leq j\leq (m-1)\}$ with $|S^*|=(m-1)/2$ and define $T^*=\{r_m(as) \mid s\in S^*\}$ , then

$$ \begin{align*}\bigg(\dfrac{a}{m}\bigg) =(-1)^{\nu^*(a,m)},\end{align*} $$

where $\nu ^*(a,m)$ is the number of integers in $T^*$ but not in $S^*$ .

Remark 6.5. We observe that (5.1) follows from Jenkins’ lemma and (6.1), namely,

$$ \begin{align*}g(a,m)=(-1)^{\nu(a,m)}g(1,m)=\bigg(\dfrac{a}{m}\bigg) g(1,m).\end{align*} $$

In other words, if we know Jenkins’ lemma (see [6] for a proof), then we have a new proof of (5.1).