---

Source. The odd-exponent step in the Notes of proof claim 133. The source states the bound; this page supplies its elementary proof.

Statement. Let $q$ be an odd prime and let $r$ be the least positive quadratic nonresidue modulo $q$. Then

$$r(r-1)<q, \qquad r<\sqrt q+1, \qquad r\le\lceil\sqrt q\rceil.$$

Complete proof. A nonresidue exists because squaring on $\mathbf F_q^*$ has kernel $\{1,-1\}$, so its image has only $(q-1)/2$ elements. In particular $2\le r<q$.

Set $m=\lceil q/r\rceil$. We have $1<m<q$, since $2\le r<q$. Since the prime $q$ is not divisible by $1<r<q$, the integer

$$u=mr-q$$

satisfies $0<u<r$. Minimality of $r$ says that $u$ is a quadratic residue. Modulo $q$ we have $mr=u$. Since $r$ is a nonresidue, multiplicativity of the quadratic character shows that $m$ is a nonresidue. The minimality of $r$ therefore also gives $m\ge r$.

The definition of $m$ gives $(m-1)r<q$, and hence

$$r(r-1)\le(m-1)r<q.$$

If $r\le\sqrt q$, the middle conclusion is immediate. If $r>\sqrt q$, the last display gives $r-1<q/r<\sqrt q$. Thus in either case $r<\sqrt q+1$. Since $q$ is not a square, the integer $r$ is at most $\lceil\sqrt q\rceil$.

Dependencies. The elementary structure of the squares in $\mathbf F_q^*$ and multiplicativity of the quadratic character.

Bears on. The odd-exponent small-prime case in the partial threshold theorem.