The congruence has a solution Sentence:
If $a \in \mathbb{Z}$, then the congruence $x^2=a \pmod p, \forall p \in P$ has a solution $\Leftrightarrow$ $a=\square$ in $\mathbb{Z}$.
If $a=\square$, then $\exists d \in \mathbb{Z}$ such that $a=d^2$.
Then, $\left ( \frac{a}{b}\right )=\left ( \frac{d^2}{b}\right)=1$, so the congruence $x^2=a \pmod p$ has a solution $\forall p \in P$.
But how can we show the other direction?
 A: Use the law of quadratic reciprocity.  Below is a sketch of a proof; I've left many of the details for you to fill in.
Let's start with the most straightforward case, in which $a$ is positive and $a = 1 \pmod 4$.  We're given that $x^2 = a \pmod p$ is solvable for all primes $p$, so the Legendre symbol $\left(\frac a p\right)$ has value $1$ for all odd primes $p$ not dividing $a$.  It's convenient to use Jacobi's generalisation of the Legendre symbol, and I'll do that for the rest of the answer.  By quadratic reciprocity (and making use of our assumption that $a = 1 \pmod 4$), we have $$\left(\frac p a\right) = 1$$
for all odd primes $p$ not dividing $a$.  Since the Jacobi symbol is multiplicative, this implies that $$\left(\frac n a \right) = 1$$ for all positive odd integers $n$ that are relatively prime to $a$. But this is impossible unless $a$ is a square:  suppose that $a$ is not a square - then there's some prime $q$ that appears in the prime-power factorization of $a$ with an odd exponent.  By the Chinese Remainder Theorem, we can find a positive odd integer $n$ such that $n$ is a quadratic nonresidue modulo $q$ and a quadratic residue modulo all other primes $p$ dividing $a$.  Then $\left(\frac n a\right) = -1$, a contradiction.
The other cases are fairly similar: if $a$ is positive and $a = 3 \pmod 4$, then again by quadratic reciprocity and multiplicativity of the Jacobi symbol we can deduce that $$\left( \frac n a \right) = (-1)^{(n - 1) / 2}$$
for all positive odd integers $n$ relatively prime to $a$.  But there's an easy contradiction here, since the left-hand side is invariant under replacing $n$ with $n + 2a$, while the right-hand side changes in sign.  If $a$ is odd and negative then you can pull out the factor of $-1$ using $\left( \frac {-1}n\right) = (-1)^{(n-1)/2}$ and then apply reciprocity to $\left(\frac{-a}n\right)$.  You can again deal with the cases $a = 1\pmod 4$ and $a = 3 \pmod 4$ separately, and obtain a contradiction in each case.  Finally, if $a$ is even then you can remove powers of $4$ to reduce either to the odd case that we've already dealt with, or the case where $a$ is even but not divisible by $4$.  In that case, we can pull out a factor of $2$ in much the same way that we did with $-1$ above, and again obtain a contradiction in each case.

Addendum: if you're not restricted to elementary number theory, then Chebotarev's density theorem gives a much quicker proof: if $a$ is a non-square, then the density theorem applied to the quadratic field $\mathbb Q(\sqrt a)$ tells you that the set of primes for which $x^2 = a \pmod p$ is solvable has density $1/2$.  That is, roughly speaking, $x^2 = a \pmod p$ is solvable for only "half" of the primes, so there are infinitely many primes for which the congruence is not solvable.
