MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question is in the title, and I do not really have anything to add. Nevertheless I had to write something here in order to be able to ask the question. Thanks.

share|cite|improve this question
up vote 17 down vote accepted

Of course. Take a quadratic nonresidue $1\leq n\leq p-1$, then some prime divisor $\ell$ of $n$ will be a quadratic nonresidue.

See this MO question for what is known about number fields.

share|cite|improve this answer
Thanks. I feel slightly embarrassed.. – Tommaso Centeleghe Jan 17 '11 at 14:23
Come on. There is this story about Grothendieck. He lectured like "take a prime $p$". Then someone asked from the audience: can $p$ be an arbitrary prime? He responded, sure, like $57$. – GH from MO Jan 17 '11 at 14:48
:-) . – Tommaso Centeleghe Jan 17 '11 at 15:10
That puts me in great company! When I was an undergraduate, I had a habit of factoring numbers that I saw as I walked around. When I passed room 57, I thought to myself "That's interesting, 57 is prime and divisible by 3!" – Jeff Strom Jan 18 '11 at 3:56
@Jeff: LOL. I am not sure Grothendieck went to such depths though. – GH from MO Jan 18 '11 at 8:56

It is actually quite easy to prove that if $p>3$, then there are at least $2$ primes less than $p$ which are quadratic non-residues. Indeed, assume there were only one, say $q$. Then every $n$ between $1$ and $p-1$ which is not multiple of $q$ is a quadratic residue. Since you have at most $(p-1)/q$ multiples of $q$, and exactly $(p-1)/2$ quadratic residues, this implies $q=2$ and moreover $p=3$ (since otherwise you would get too many quadratic residues: every odd number between $1$ and $p-1$, together with $4$).

share|cite|improve this answer
Nice . – Tommaso Centeleghe Jan 17 '11 at 16:41
I wonder what lower bound can we prove for the number of quadratic nonresidue primes $1\leq\ell\leq p-1$. For the number of quadratic residue primes $1\leq\ell\leq p-1$ I can prove $\gg\log p/\log\log p$ by an elementary argument involving quadratic reciprocity. – GH from MO Jan 17 '11 at 22:37
I made my previous comment into an official MO question. I hope it survives. – GH from MO Jan 18 '11 at 9:27
Well, it survived! – Andrei Moroianu Jan 21 '11 at 10:29
@Andrei: Thanks for your support! – GH from MO Jan 21 '11 at 13:32

Slightly different in emphasis, the smallest quadratic nonresidue is in fact prime, as the product of residues is another residue.

share|cite|improve this answer

Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root $q<p$ for $p$ which is prime.

share|cite|improve this answer
That's interesting, I haven't heard about this! – GH from MO Jan 18 '11 at 9:00

I think the answer is obvious. Since $$\sum_{1\leq n\leq p-1}\left(\frac{n}{p}\right)=0$$, there must exist a positive integer $n\leq p-1$, such that $(\frac{n}{p})=-1$, or else the summation above must be equal to $p-1$. Of course, maybe $n$ is not a prime, however there always be a prime factor $\ell$ of $n$ such that $(\frac{\ell}{p})=-1$.

share|cite|improve this answer
This answer is the same as GH's, only using an unnecessarily complicated argument as to why there is a quadratic nonresidue $1\leq n\leq p-1$. – Zev Chonoles Jan 18 '11 at 2:53

Your Answer


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.