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.

  • 20
    $\begingroup$ On the other hand, 16 is an 8th power modulo every prime! $\endgroup$ – Laurent Berger Jul 5 '13 at 6:51
  • 4
    $\begingroup$ Following on @LaurentBerger's remark, we can observe that for $\alpha$ an algebraic integer generating an abelian but not-cyclic extension of $\mathbb Q$, the minimal polynomial of $\alpha$ over $\mathbb Q$ is reducible modulo every prime. The simplest case is $x^4+1$. $\endgroup$ – paul garrett Jul 8 '13 at 2:10
  • $\begingroup$ This is an instance of the Hasse-Minkowski principle, which, as pointed out in the answers, is a souped-up version of quadratic reciprocity (cf. Hilbert symbols). en.wikipedia.org/wiki/Hasse%E2%80%93Minkowski_theorem $\endgroup$ – Ian Agol Sep 2 '13 at 2:10

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$.


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.

  • 2
    $\begingroup$ Mike: See Ireland & Rosen's book, Chapter 5, Section 2, Theorem 3. They prove a nonsquare integer $a$ is a quadratic nonresidue modulo infinitely many primes, but without making any density statement. $\endgroup$ – KConrad Sep 2 '13 at 3:48

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$).

  • 1
    $\begingroup$ In the last step you implicitly assumed that $p\equiv 3\pmod{4}$. So your argument proves the result for non-squares which have a prime factor congruent to $3\pmod{4}$. $\endgroup$ – Michael Zieve Jul 5 '13 at 4:39
  • $\begingroup$ Where is the assumption? I can't see it. Thanks. $\endgroup$ – brando Jul 5 '13 at 13:06
  • $\begingroup$ In the last step you say $(q|p)^n=-1$, which is only true when $(q|p)=-1$. Since $q\equiv -1\pmod{p}$, this means that $(-1|p)=-1$, so $p\equiv 3\pmod{4}$. Although now that I write this, I see that you could have replaced your condition $q\equiv -1\pmod{p}$ with the condition that $q$ is a nonsquare mod $p$, and then your proof would work whenever $a$ has an odd prime factor. And of course for the remaining values of $a$ one can explicitly describe a prime modulus in which $a$ is a nonsquare. $\endgroup$ – Michael Zieve Jul 5 '13 at 22:36
  • $\begingroup$ Ah right, what I had in my head was $(q|p)=-1$, not $q=-1\mod p$. $\endgroup$ – brando Jul 7 '13 at 18:30

A Chebotarev-free argument is given by our own @Pete L Clark here:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.