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

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|improve this question
add comment

5 Answers

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|improve this answer
1  
Thanks. I feel slightly embarrassed.. –  Tommaso Centeleghe Jan 17 '11 at 14:23
5  
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
5  
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
add comment

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|improve this answer
    
Nice . –  Tommaso Centeleghe Jan 17 '11 at 16:41
2  
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
add comment

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

share|improve this answer
add comment

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

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

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|improve this answer
3  
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
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.