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

This question already has an answer here:

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.

## marked as duplicate by lulu, Watson, JavaMan, Lord Shark the Unknown, user10354138Dec 12 '18 at 6:22

• I didn't think so but why not? – joseph Dec 10 '18 at 13:30
• Thanks for sharing that link @lulu. Can someone explain the first idea a little more? I got lost with how the author came up with $\frac{f(k f(0) p_1 ... p_n))}{f(0)}$ and how it proves the proposition – joseph Dec 10 '18 at 13:40
• Actually, provided $a$ is not a multiple of $p$ you can extract any square factors of $a$ before you start so that you can assume that $a_i=1$. – Mark Bennet Dec 10 '18 at 13:43
• @mjoseph If $f(0)=0$ then the claim is trivial so suppose $f(0)\neq 0$. Write $f(x)=g(x)+f(0)$, note that $x\,|\,g(x)$. Thus $g(kf(0)p_1\cdots p_n)$ is divisible by $f(0)p_1\cdots p_n$. say that $g(kf(0)p_1\cdots p_n)=m\times f(0)p_1\cdots p_n$. Dividing by $f(0)$ we get that $\frac {f(kf(0)p_1\cdots p_n)}{f(0)}=m\times p_1\cdots p_n+1$ which is obviously prime to each of the $p_i$. Thus any prime which divides it has to be a new prime to add to the list. – lulu Dec 10 '18 at 13:50

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.