Distribution of Residues Modulo p

Abstract

The distribution of quadratic residues and non-residues modulo p has been of intrigue to the number theorists of the last several decades. Although Gauss’ celebrated Quadratic Reciprocity Law gives a beautiful criterion to decide whether a given number is a quadratic residue modulo p or not, it is still an open problem to find a small upper bound on the least quadratic non-residue mod p as a function of p, at least when p ≡ 1 (mod 8). This is because for any given natural number N one can construct many primes p ≡ 1 (mod 8) having the first N positive integers as quadratic residue (see, for example, Theorem 3 below).