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


2005-2017 IMOmath.com | imomath"at"gmail.com | Math rendered by MathJax
Home | Olympiads | Book | Training | IMO Results | Forum | Links | About | Contact us