Does there always exist a prime $q\equiv3\mod 4$ that divides $p+a^2$ with $p\equiv1$ mod 4

Question

Let $p$ be a prime such that $p\equiv1\mod4$. Is it true that there will always exist a prime $q$ that satisfies $q\vert(p+a^2)$ and $q\equiv3\mod4$, for some integer $a$?

I have tried proceeding by contradiction, assuming that for every prime $q$ such that $q\vert(p+a^2)$ it must satisfy $q\equiv1\mod4$, however I have not been able to find a contradiction. Is this even true, and is it a much more complicated proof than I think? It seems to me like it must be true as there are infinitely many primes congruent to 3 modulo 4.

Answer 1

If $q\equiv -1 \pmod 4$, By quadratic reciprocity we have $$\left(\frac {-p}q\right)=\left(\frac {-1}q\right)\times\left(\frac qp\right)=-\left(\frac qp\right)$$

So choose any quadratic non-residue $n$ $\pmod p$ and let $q$ be a prime satisfying $$q\equiv n\pmod p\quad \&\quad q\equiv -1\pmod 4$$ (infinitely many such $q$ exist by Dirichlet's Theorem). It follows that $q$ is of the form you want.