# Every prime occurs as the least quadratic nonresidue

It is not difficult to check that the least quadratic nonresidue modulo prime $$p$$ cannot be a composite number, see, for example: Quadratic nonresidues mod p.

It is quite natural to ask the opposite question: Is every prime the least quadratic non-residue modulo some $$p$$? In the other words, if we are given a prime $$q$$, is there $$p$$ such that $$q$$ is a quadratic nonresidue modulo $$p$$ and, at the same time, all numbers $$1,2,\dots,q-1$$ are quadratic residues modulo $$p$$?

I think I have a proof which I outlined in my answer below. However, the proof uses Dirichlet's theorem on arithmetic progressions, which is rather non-elementary result. I was wondering whether there is a more straightforward solution.

I will also include link to the sequence A000229 in OEIS, which is described as: "a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m."

The approach taken in this proof is similar to the proof of Theorem 3 in Section 5.2 of Ireland, Rosen: A Classical Introduction to Modern Number Theory. This theorem states that for every non-square integer $$a$$ there are infinitely many primes $$p$$ such that $$a$$ is a quadratic non-residue modulo $$p$$.

$$\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}$$Let $$q=p_k$$ be the $$k$$-th prime, we also consider all smaller primes $$p_1=2. We want to find $$p$$ such that $$\jaco 2p=\jaco{p_2}p = \dots = \jaco{p_{k-1}}p = 1 \qquad\text{a}\qquad \jaco{p_k}p=-1. \tag{*}$$ If there is such $$p$$, then

• $$p_k$$ is a quadratic non-residue modulo $$p$$;
• all smaller primes are quadratic residues modulo $$p$$.

Since the smallest quadratic non-residue must be prime, we get that $$p_k$$ the smallest quadratic non-residue modulo $$p$$.

To get a prime which fulfills $$(*)$$, we consider the system of congruences \begin{align*} p &\equiv 1\pmod8\\ p &\equiv 1\pmod{p_2}\\ &\vdots\\ p &\equiv 1\pmod{p_{k-1}}\\ p &\equiv s\pmod{p_k} \end{align*} where $$s$$ a is some quadratic non-residue modulo $$p_k$$.

First, this system of congruences is equivalent to $$p\equiv a \pmod{8p_2\cdots p_k}$$ for some $$a$$, i.e., the solutions form an arithmetic progression. Moreover, it is easy to see that $$\gcd(a,8p_2\cdots p_k)$$, since $$a$$ fulfills all congruences listed above. So we get from Dirichlet's theorem that there is a prime number $$p$$ which fulfills this system of congruences.

For any such prime we have $$\jaco2p=1,$$ since $$p\equiv 1\pmod 8$$. At the same time, using law of quadratic reciprocity together with $$p\equiv1\pmod4$$ we get $$\jaco{p_i}p=\jaco{p}{p_i}=\jaco1{p_i}=1.$$

Similarly, we have $$\jaco{p_k}p=\jaco{p}{p_k}=\jaco s{p_k}=-1.$$

• Very pretty. I'd be surprised if there were a proof that didn't use Dirichlet's theorem since quadratic reciprocity really is about those arithmetic progressions. Can you prove that this theorem implies Dirichlet's theorem? Then an alternative proof here would be really interesting. – Ethan Bolker Oct 7 '19 at 13:42