Let $a$ be a positive integer which is not a square, i.e. $a\neq n^2$ for all $n=1,2,3,\ldots$.
Show that there exists an odd prime $p$ such that $\left(\frac{a}{p}\right)=-1.$
Hint: You may use "Dirichlet's theorem on Primes in Arithmetic Progressions" which says; Let $m,r$ be positive integers such that $(m,r)=1.$ Then there are infinitely many primes among the integers $mk+r$, $k=1,2,3,\ldots$.
What I have done is that suppose that there isn't an odd prime which makes Legendre symbol -1 for given a, When p is much lager than a, it can't be 1... well I don't know how to prove such p is a prime.
If $2$ is the only prime that divide $a$ with an odd multiplicity it is enough to consider a prime $p\equiv \pm 3\pmod{8}$ that does not divide $a$.
Assume that $q_1 < q_2 <\ldots < q_k$ are the primes that divide $a$ with an odd multiplicity.
Let $\eta_k$ be the least non-quadratic residue $\!\!\pmod{q_k}$: prove that $\eta_k$ is a prime.
Now take a prime $p\equiv 1\pmod{8},p\equiv 1\pmod{q_1},p\equiv{1}\pmod{q_2},\ldots ,p\equiv 1\pmod{q_{k-1}}$, $p\equiv\eta_k\pmod{q_k}$. You are allowed to do that since by the Chinese theorem the previous constraints are equivalent to $p\equiv N\pmod{2^m\prod q_i}$ and Dirichlet's theorem applies. Then:
$$\left(\frac{a}{p}\right) = \prod_{j=1}^{k}\left(\frac{q_j}{p}\right) = \prod_{j=1}^{k-1}\left(\frac{p}{q_j}\right)\cdot\left(\frac{\eta_k}{q_k}\right)=\color{red}{-1}$$ by quadratic reciprocity and the multiplicative property of the Legendre symbol.