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.

$\endgroup$
3
  • 21
    $\begingroup$ On the other hand, 16 is an 8th power modulo every prime! $\endgroup$ 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$ 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
    Sep 2, 2013 at 2:10

4 Answers 4

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

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

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

$\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$ Jul 5, 2013 at 4:39
  • $\begingroup$ Where is the assumption? I can't see it. Thanks. $\endgroup$
    – brando
    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$ 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
    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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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