Quadratic congruences (Table of contents)

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