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.
Best Answer
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.