Infinitely many primes $q$ such that $p$ is a quadratic residue modulo $q$

Question

For primes $p,q\equiv 1\pmod 4$, I want to know if there are infinitely many $q$ such that $p$ is a quadratic residue modulo $q$?

This question is important to me for understanding whether the statement that "for every pair or primes $p,q \equiv 1\pmod 4$ such that $p$ is a quadratic residue modulo $q$, there exists a $(p+1)$-regular Cayley graph of $\mathrm{PSL}(2, \mathbb{Z}/q\mathbb{Z})$ with $q(q^2-1)/2$ vertices such that its second-largest eigenvalue is at most $2\sqrt{p}$" implies the existence of a family of $(p+1)$-regular graphs with this property (i.e. an infinite family of expanders).

The above statement in quotes is by Lubotzky-Phillips-Sarnak.

Answer 1

Since $p\equiv 1\pmod{4}$, by Quadratic Reciprocity we know that $$\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right).$$ So $p$ is a quadratic residue modulo $q$ if and only if $q$ is a quadratic residue modulo $p$.

In particular, you can consider the arithmetic progression $1+(4p)k$; by Dirichlet's Theorem on Primes in Arithmetic Progressions, the sequence contains infinitely many primes $q$, each of which is congruent to $1$ modulo $4$, and to $1$ modulo $p$, and therefore $q$ is a quadratic residue modulo $p$ of the form $4t+1$, as desired.

More generally, let $a$ be any quadratic residue modulo $p$. By the Chinese Remainder Theorem, there exists a unique $b$ modulo $4p$ such that $x\equiv b\pmod{4p}$ if and only if $x\equiv a\pmod{p}$ and $x\equiv 1\pmod{4}$.

Now consider the arithmetic progression $b$, $b+4p$, $b+2(4p)$, $b+3(4p),\ldots$.

By Dirichlet's Theorem the progression contains infinitely many primes. Any such prime $q$ will be congruent to $b$ modulo $4p$, and therefore $q\equiv 1\pmod{4}$ and $q\equiv a\pmod{p}$, hence a quadratic residue.

Similar arguments show that you can find infinitely many primes $q$ such that $q\equiv 3\pmod{4}$ and $p$ is a quadratic residue modulo $q$; and likewise if you start with $p\equiv 3\pmod{4}$, there are both infinitely many primes $q$ with $q\equiv 1\pmod{4}$ and $\left(\frac{p}{q}\right)=1$, and infinitely many primes $q$ with $q\equiv 3\pmod{4}$ and $\left(\frac{p}{q}\right) = 1$.

Also infinitely many for which $p$ is not a quadratic residue, in each of the four cases.

Answer 2

Here's a solution which does not require invoking quadratic reciprocity.

Consider the polynomial $f(x)=x^2-p$. A theorem of Schur states that, for every nonconstant integer polynomial $f$, there exist infinitely many primes that divide values of $f$. This implies that there are infinitely many $q$ which divide $x^2-p$ for some integer $x$; $p$ is a quadratic residue modulo such primes.

---

A quick proof of Schur's theorem goes as follows: suppose only finitely many primes $q_1,\dots,q_n$ divide values of $f$. Take some large $N$, and consider the number of values of $f$ which lie in the interval $[1,N]$. There are at least $cN^{1/\deg f}$ such values, for some small constant $c$. However, there are at most $$(\log_{q_1}(N)+1)(\log_{q_2}(N)+1)\cdots(\log_{q_n}(N)+1)\leq (\log_2(N)+1)^n$$ integers in $[1,N]$ whose prime divisors are only contained within the set $\{q_1,\dots,q_n\}$ (the exponent of $q_i$ in this prime factorization of such a number is at most $\log_{q_i}(N)+1$). So, we must have $$(\log_2(N)+1)^n\leq cN^{1/\deg f}.$$ But this is false for large enough $N$.