Does there exist a non-square number which is the quadratic residue of every prime? I want to know whether there exist a non-square number $n$ which is the quadratic residue of every prime.
I know it is very elementary, and I think those kind of number are not exist, but I don't know
how to prove.
 A: Let $a$ be any non-square. Then write $a=p^nm$ for some odd $n$ and prime $p$ which does not divide $m$. By Dirichlet's Theorem on primes in arithmetic progressions and the Chinese Remainder Theorem we can find a prime  $q$ which is $1\mod 4$, $(q|p)=-1$, and $1\mod l$ for each prime $l$ dividing $m$. Then by quadratic reciprocity, $(a|q)=(p|q)^n(m|q)=(q|p)^n=-1$ (where $(\cdot|l)$ is the Legendre symbol modulo $l$).
A: A Chebotarev-free argument is given by our own @Pete L Clark here:
https://math.stackexchange.com/questions/6976/proving-that-an-integer-is-the-n-th-power
A: This is actually an elementary consequence of quadratic reciprocity,
generalizing the familiar proof à la Euclid that that are infinitely many
primes of the form $4k+3$ 
(i.e. primes of which $-1$ is not a quadratic residue).
We want to show that there exists $p$ such that $(n/p) = -1$.
[As stated Paul's question asks only for $(n/p) \neq +1$, but this is
trivial (if $n = -1$, take $p=3$; else let $p$ be a factor of $n$), 
so we'll exclude the finitely many prime factors $p$ of $n$.]
By QR there exists a nontrivial homomorphism 
$\chi: ({\bf Z} / 4n{\bf Z})^* \rightarrow \lbrace 1, -1 \rbrace$
such that $(n/p) = \chi(p)$ for all primes $p \nmid 2n$.
Let $a$ be any positive integer coprime to $4n$ such that $\chi(a) = -1$.
Then we have a prime factorization $a = \prod_j p_j$,
and $\prod_j \chi(p_j) = \chi(a) = -1$.
Therefore $\chi(p_j) = -1$ for some $j$, QED.
As in Euclid we can iterate this argument to construct
infinitely many distinct $p$ for which $(n/p) = -1$.
A: This follows from the Chebotarev density theorem, or from the earlier and easier Frobenius density theorem.  The polynomial $f(x):=x^2-n$ is irreducible in $\mathbb{Q}[x]$, so these density theorems imply that the mod $p$ reduction of $f(x)$ is irreducible for infinitely many primes $p$ (in fact: for half of all primes $p$).
It would be interesting to know a proof that didn't rely on these density theorems.
