## Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 5 Answers

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.

-

1
Thanks. I feel slightly embarrassed.. – Tommaso Centeleghe Jan 17 2011 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 Jan 17 2011 at 14:48
:-) . – Tommaso Centeleghe Jan 17 2011 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 2011 at 3:56
@Jeff: LOL. I am not sure Grothendieck went to such depths though. – GH Jan 18 2011 at 8:56

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-
Nice . – Tommaso Centeleghe Jan 17 2011 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 Jan 17 2011 at 22:37
I made my previous comment into an official MO question. I hope it survives. – GH Jan 18 2011 at 9:27
Well, it survived! – Andrei Moroianu Jan 21 2011 at 10:29
@Andrei: Thanks for your support! – GH Jan 21 2011 at 13:32

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

-

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

-

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 2011 at 2:53

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 38, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9426203370094299, "perplexity_flag": "middle"}