23
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 21
    $\begingroup$ On the other hand, 16 is an 8th power modulo every prime! $\endgroup$
    – Laurent Berger
    Commented Jul 5, 2013 at 6:51
  • 6
    $\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
    Commented Jul 8, 2013 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
    Commented Sep 2, 2013 at 2:10

4 Answers 4

Reset to default
28
$\begingroup$

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

Improve this answer
$\endgroup$
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\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
    Commented Sep 2, 2013 at 3:48
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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
    Commented Jul 5, 2013 at 4:39
  • $\begingroup$ Where is the assumption? I can't see it. Thanks. $\endgroup$
    – brando
    Commented Jul 5, 2013 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
    Commented Jul 5, 2013 at 22:36
  • $\begingroup$ Ah right, what I had in my head was $(q|p)=-1$, not $q=-1\mod p$. $\endgroup$
    – brando
    Commented Jul 7, 2013 at 18:30
4
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .