Question: Let $p$ be a sufficiently large prime satisfying $p \equiv 1 \mod 4$, let $y = \frac{\log^2 p}{\log \log p}$, and let $F$ be a large constant (say, $1000$). Can we choose another prime $q \in [e^y, e^{Fy}]$ such that $q \equiv 1 \mod 4$, and such that the Legendre symbol of $q$ and $p$ satisfies $( \frac{q}{p}) = -1$?
I ran across this problem while thinking about the Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak. I suspect that showing that such a prime $q$ exists is an easy problem, but since my background in number theory is very weak, I'm a bit lost.
One approach that I tried was to choose a quadratic non-residue $a$ modulo $p$, and then use the Chinese Remainder Theorem to find a unique $N < 4p$ such that $q \equiv a \mod p, q \equiv 1 \mod 4 \iff q \equiv N \mod 4p$. Then I tried to use results about the density of primes in the arithmetic progression $N, N+4p, N+8p, \dots$ to estimate the number of primes in the interval. However, the error terms are too big to show that any suitable prime $q$ exists in the interval.
The reason this approach doesn't work is because the arithmetic progression $N, N+4p, N+8p, \dots$ is very sparse, and it misses a lot of acceptable values for $q$. Indeed, I only considered one quadratic non-residue $a$ to get this progression, but I really could have chosen any of $(p-1)/2$ quadratic non-residues. I'd like to consider all possible quadratic non-residues at once, but using the CRT approach would then give me $(p-1)/2$ arithmetic progressions, and I can't find any results about the density of primes belonging to one of multiple arithmetic progressions.
Is there a better approach to this problem, or is there any theorem that gives an easy answer to this question? I would appreciate any suggestions. Thank you.