Quadratic residue

modulo

An integer for which the congruence

is solvable. If the above congruence is unsolvable, then is called a quadratic non-residue modulo . Euler's criterion: Let be prime. Then an integer coprime with is a quadratic residue modulo if and only if

and is a quadratic non-residue modulo if and only if

References

[1]	I.M. Vinogradov, "Elements of number theory" , Dover, reprint (1954) (Translated from Russian)

Comments

An amusing unsolved problem is the following: Let be a prime with (). Let be the sum of all quadratic non-residues between 0 and , and the sum of all quadratic residues. It is known that . Give an elementary proof.

References

[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XIII