Some sums of Legendre’s symbols

Finding the number of solutions of a certain conguence is often reduced to counting the values of \( x\in\{0,1,\dots,p-1\} \) for which a given polynomial \( f(x) \) with integer coefficients is a quadratic residue modulo an odd prime \( p \). The answer is obviously directly connected to the value of the sum \[ \sum_{x=0}^{p-1}\left(\frac{f(x)}p\right).\] In this part we are interested in sums of this type.

For a linear polynomial \( f \), the considered sum is easily evaluated:

Theorem 17

For arbitrary integers \( a,b \) and a prime \( p\nmid a \), \[ \sum_{x=0}^{p-1}\left(\frac{ax+b}p\right)=0.\]

Show proof.

Since \( p\nmid a \), the numbers \( ax+b \), \( x=0,1,\dots, p-1 \) form a complete system of residues modulo \( p \). Exactly \( \frac{p-1}2 \) of them are quadratic residues, exactly \( \frac{p-1}2 \) are quadratic nonresidues, and one is divisible by \( p \). It follows that \[ \sum_{x=0}^{p-1}\left(\frac{ax+b}p\right)=\frac{p-1}2\cdot1+ \frac{p-1}2\cdot(-1)+0=0.\]

To evaluate the desired sum for quadratic polynomials \( f \), we shall use the following proposition.

Theorem 18

Let \( f(x)^{p^{\prime} }=a_0+a_1x+\dots+ a_{kp^{\prime} }x^{kp^{\prime} } \), where \( k \) is the degree of polynomial \( f \). We have \[ \sum_{x=0}^{p-1}\left(\frac{f(x)}p\right)\equiv-(a_{p-1}+ a_{2(p-1)}+\dots+a_{k^{\prime} (p-1)})\;\mbox{(mod }p),\quad\mbox{where } k^{\prime} =\left[\frac{k}2\right].\]

Show proof.

Define \( S_n=\sum_{x=0}^{p-1}x^n \) (\( n\in\mathbb{N} \)) and \( S_0=p \). It can be shown that \( S_n\equiv-1 \) (mod \( p \)) for \( n> 0 \) and \( p-1\mid n \), and \( S_n\equiv0 \) (mod \( p \)) otherwise. Now Euler\( \prime \)s Criterion gives us \[ \sum_{x=0}^{p-1}\left(\frac{f(x)}p\right)\equiv\sum_{x=0}^{p-1} f(x)^{p^{\prime} }=\sum_{i=0}^{kp\prime }a_iS_i\equiv-(a_{p-1}+a_{2(p-1)}+ \dots+a_{k^{\prime} {p-1}})\;\mbox{(mod }p).\]

Theorem 19

For any integers \( a,b,c \) and a prime \( p\nmid a \), the sum \[ \sum_{x=0}^{p-1}\left(\frac{ax^2+bx+c}p\right)\] equals \( -\left(\frac ap\right) \) if \( p\nmid b^2-4ac \), and \( (p-1)\left(\frac ap\right) \) if \( p\mid b^2-4ac \).

Show proof.

We have \[ \left(\frac{4a}p\right) \sum_{x=0}^{p-1}\left(\frac{ax^2+bx+c}p\right)= \sum_{x=0}^{p-1}\left(\frac{(2ax+b)^2-D}p\right),\] where \( D=b^2-4ac \). Since numbers \( ax+b \), \( x=0,1,\dots,p-1 \) comprise a complete system of residues modulo \( p \), we obtain \[ \left(\frac ap\right) \sum_{x=0}^{p-1}\left(\frac{ax^2+bx+c}p\right)=\sum_{x=0}^{p-1} \left(\frac{x^2-D}p\right)=S.\] Theorem 18 gives us \( S\equiv-1 \) (mod \( p \)), which together with \( |S|\leq p \) yields \( S=-1 \) or \( S=p-1 \).

Suppose that \( S=p-1 \). Then \( p-1 \) of the numbers \( \left(\frac{x^2-D}p \right) \) are equal to \( 1 \), and exactly one, say for \( x=x_0 \), is equal to 0, i.e. \( p\mid x_0^2-D \). Since this implies \( p\mid(-x_0)^2-D= x_0^2-p \) also, we must have \( x_0=0 \) and consequently \( p\mid D \). Conversely, if \( p\mid D \), we have \( S=p-1 \); otherwise \( S=-1 \), which finishes the proof.

Problem 9

The number of solutions \( (x,y) \) of congruence \[ x^2-y^2=D\;\;\mbox{(mod }p),\] where \( D\not\equiv 0 \) (mod \( p \)) is given, equals \( p-1 \).

Show solution.

This is an immediate consequence of the fact that, for fixed \( x \), the number of solutions \( y \) of the congruence \( y^2\equiv x^2-D \) (mod \( p \)) equals \( \left(\frac{x^2-D}p\right)+1 \).

Evaluating the sums of Legendre’s symbols for polynomials \( f(x) \) of degree greater than 2 is significantly more difficult. In what follows we investigate the case of cubic polynomials \( f \) of a certain type.

For an integer \( a \), define \[ K(a)=\sum_{x=0}^ {p-1}\left(\frac{x(x^2+a)}p\right).\]

Assume that \( p\nmid a \). We easily deduce that for each \( t\in\mathbb{Z} \), \[ K(at^2)=\left(\frac tp\right) \sum_{x=0}^{p-1}\left(\frac{\frac xt((\frac xt)^2+a)}p\right)= \left(\frac tp\right)K(a).\] Therefore \( |K(a)| \) depends only on whether \( a \) is a quadratic residue modulo \( p \) or not.

Now we give one non-standard proof of the fact that every prime \( p\equiv1 \) (mod 4) is a sum of two squares.

Theorem 20 (Jacobstal’s identity)

Let \( a \) and \( b \) be a quadratic residue and nonresidue modulo a prime number \( p \) of the form \( 4k+1 \). Then \( |K(a)| \) and \( |K(b)| \) are even positive integers that satisfy \[ \left(\frac12|K(a)|\right)^2+\left(\frac12|K(b)| \right)^2=p.\]

Show proof.

The previous consideration gives us \( p^{\prime} (K(a)^2+K(b)^2)=\sum_{n=1}^{p-1}K(n)^2=\sum_{n=0}^{p-1}K(n)^2 \), since \( K(0)=0 \). Let us determine \( \sum_{n=0}^{p-1}K(n)^2 \). For each \( n \) we have \[ K(n)^2=\sum_{x=0}^{p-1}\sum_{y=0}^{p-1} \left(\frac{xy(x^2+n)(y^2+n)}p\right),\] which implies \[ \sum_{n=0}^{p-1}K(n)^2=\sum_{x=0}^{p-1}\sum_{y=0}^{p-1} \left(\frac{xy}p\right)\sum_{n=0}^{p-1} \left(\frac{(n+x^2)(n+y^2)}p\right).\] Note that by the theorem 19, \( \sum_{n=0}^{p-1}\left(\frac{(n+x^2)(n+y^2)}p\right) \) equals \( p-1 \) if \( x=\pm y \), and \( -1 \) otherwise. Upon substituting these values the above equality becomes \[ \sum_{n=0}^{p-1}K(n)^2=p(2p-2)-\sum_{x=0}^{p-1}\sum_{y=0}^{p-1} \left(\frac{xy}p\right)=4pp^{\prime} .\] We conclude that \( K(a)^2+K(b)^2=4p \). Furthermore, since \( K(a)^2+K(b)^2 \) is divisible by 4, both \( K(a) \) and \( K(b) \) must be even, and the statement follows.