# 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.$

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].$

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$$.

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$$.

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.$