elementary proof that infinite primes quadratic residue modulo $p$

$p \gt 2$ is a prime, then there are infinite primes $q$ such that $q$ is a quadratic residue modulo $p$.

With Dirichlet's theorem on arithmetic progressions, the problem is easy! How about Without the use of the theorem? Can one find an elementary proof?

p.s. there are several elementary ways(without Dirichlet) to show that there are infinite primes $q$ such that $q$ is a quadratic non-residue modulo $p$

Proof 1 The least $q>0$ quadratic non-residue modulo $p$ is a prime . Consider

$$a_0=q, a_1=q+p,a_2=q+pa_1,a_3=q+pa_1a_2,\dotsc, a_n=q+pa_1a_2\dotsb a_{n-1},\dotsc $$ then $(a_i,a_j)=1$

Proof 2 Only $\dfrac{p-1}2$ quadratic non-residues modulo $p$, so there is a integer $a$ such that $(\dfrac{a^2+1}p)=-1$.

In not, only finite $q_1,q_2,\dotsc, q_n$. then there exists $k\in\Bbb Z$ such that $kq_1q_2\dotsb q_n \equiv a \pmod p$. Consider

$$ (kq_1q_2\dotsb q_n)^2 +1$$

Solution 1:

Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$

Lemma: $$ (-p|q) = (q|p). $$

Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$

Let $$ F_1 = 4 + p, $$ $$ F_2 = 4 F_1^2 + p, $$ $$ F_3 = 4 F_1^2 F_2^2 + p, $$ $$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$ $$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$ and so on.

These are all of the form $a^2 + p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 1 \pmod 4} $$

Lemma: $$ (p|q) = (q|p). $$

Lemma: If $$ a^2 - p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$

FIND an even square $$ W = 4^k = \left( 2^k \right)^2 $$ such that $$ \color{magenta}{ W > p.} $$

Let $$ F_1 = W - p, $$ $$ F_2 = W F_1^2 - p, $$ $$ F_3 = W F_1^2 F_2^2 - p, $$ $$ F_4 = W F_1^2 F_2^2 F_3^2 - p, $$ $$ F_5 = W F_1^2 F_2^2 F_3^2 F_4^2 - p, $$ and so on. As $p \equiv 1 \pmod 4$ and $W \equiv 0 \pmod 4,$ we know $W - p \equiv 3 \pmod 4 $ and so $W-p \geq 3. $ So the $F_j$ are larger than $1$ and strictly increasing.

These are all of the form $a^2 - p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$

Solution 2:

By quadratic reciprocity, $(p/q) = (-1)^{(p-1)/2}(-1)^{(q-1)/2}(q/p)$.

Let $\chi$ be the Dirichlet character of conductor $4p$ given by $n \mapsto (-1)^{(n-1)/2}(n/p)$.

Then the function $q \mapsto (q/p)$ is nothing but $q \mapsto (-1)^{(p-1)/2}\chi(q)$, almost a Dirichlet character (it is a Dirichlet character if $p \equiv 1 \mod 4$ and minus a Dirichlet character if $p \equiv 3 \mod 4$).

The character $\chi$ determines the splitting of primes in the quadratic field $K=\mathbf Q(\sqrt{p^*})$, where $p^* = (-1)^{(p-1)/2}p$. More precisely, the Dedekind zeta function $\zeta_K(s)$ factors as $$\zeta_K(s) = \zeta(s)L(\chi,s).$$ An easy estimate shows that the Dedekind zeta function of any number field has a simple pole at $s=1$. Since $\zeta(s)$ has a simple pole there, it must be the case that $L(\chi,1)\neq 0, \infty$, in other words the series

$$0<\left|\sum_{n=1}^\infty \frac{\chi(n)}{n}\right| <\infty.$$

By the divergence of the harmonic series this implies that there are infinitely many $n$ with $\chi(n)=1$ and infinitely many $n$ with $\chi(n)=-1$ (and that they are evenly distributed enough so that the series converges). Using the Euler product, we see also that there are infinitely many primes with $\chi(q)=1$ and infinitely many primes with $\chi(q)=-1$.

Remark: This is basically a proof of a very primitive version of Cebotarev's theorem in this very specific case.