Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
14  
On the other hand, 16 is an 8th power modulo every prime! –  Laurent Berger Jul 5 '13 at 6:51
2  
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$. –  paul garrett Jul 8 '13 at 2:10
    
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 –  Ian Agol Sep 2 '13 at 2:10
add comment

4 Answers

up vote 14 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  KConrad Sep 2 '13 at 3:48
add comment

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

http://math.stackexchange.com/questions/6976/proving-that-an-integer-is-the-n-th-power

share|improve this answer
add comment

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

share|improve this answer
1  
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}$. –  Michael Zieve Jul 5 '13 at 4:39
    
Where is the assumption? I can't see it. Thanks. –  brando Jul 5 '13 at 13:06
    
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. –  Michael Zieve Jul 5 '13 at 22:36
    
Ah right, what I had in my head was $(q|p)=-1$, not $q=-1\mod p$. –  brando Jul 7 '13 at 18:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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