Prove that there are infinitely many prime numbers $p$ such that $\left(\frac{a}{p}\right)=1$ for fixed $a$.

Question

I already proved this is true for all prime numbers and clearly see how this is true for all perfect squares, I'm just having trouble expanding it to any prime factorization. If we let $a$ have prime factorization $a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$, then since the Legendre Symbol is multiplicative, we know that: $$ \left(\frac{a}{p}\right)=\left(\frac{p_1}{p}\right)^{a_1}\left(\frac{p_2}{p}\right)^{a_2}...\left(\frac{p_n}{p}\right)^{a_n} $$ I don't, however, understand where to go from here.

Answer 1

Through quadratic reciprocity and Dirichlet's theorem we have a straightforward proof: for any $a\in\mathbb{N}^+$ there is some prime $p$ such that $p\equiv{1}\pmod{4}$ and $p\equiv 1\pmod{a}$. For such a prime $$ \left(\frac{a}{p}\right)=\left(\frac{p}{a}\right)=\left(\frac{1}{a}\right)=1.$$

Yet another overkill: by Chebotarev's density theorem the polynomial $x^2-a$ has a root in $\mathbb{F}_p$ for approximately half the primes $p$. In particular an $a\in\mathbb{N}^+$ that is a quadratic non-residue for every sufficiently large prime $p$ cannot exist.