Smallest quadratic nonresidue

Definition

Let $p$ be a prime number. The smallest quadratic nonresidue modulo $p$ is the smallest positive integer $q$ such that the congruence class of $q$ modulo $p$ is not a square; in other words, $q$ is the smallest quadratic nonresidue modulo $p$.

The smallest quadratic nonresidue modulo a prime is always a prime.

Facts and conjectures

• Extended Riemann hypothesis: This states that the smallest quadratic nonresidue modulo $p$ is less than $3(\log p{)}^2/2$. This is a conjecture, and has not been proved.

Facts

• Smallest quadratic nonresidue is less than squareroot plus one: This states that the smallest quadratic nonresidue modulo $p$ is less than $\sqrt{p}+1$. This has been proved.
• Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes: In particular, this implies that the smallest quadratic nonresidue takes small values for arbitrarily large primes.