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.\]
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].\]
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'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\).
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\).
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.\]
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.