3
$\begingroup$

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.

$\endgroup$

5 Answers 5

18
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ 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$. $\endgroup$
    – GH from MO
    Jan 17, 2011 at 14:48
  • $\begingroup$ :-) . $\endgroup$ Jan 17, 2011 at 15:10
  • 7
    $\begingroup$ 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!" $\endgroup$
    – Jeff Strom
    Jan 18, 2011 at 3:56
  • 1
    $\begingroup$ @Jeff: LOL. I am not sure Grothendieck went to such depths though. $\endgroup$
    – GH from MO
    Jan 18, 2011 at 8:56
10
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Nice . $\endgroup$ Jan 17, 2011 at 16:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jan 17, 2011 at 22:37
  • $\begingroup$ I made my previous comment into an official MO question. I hope it survives. $\endgroup$
    – GH from MO
    Jan 18, 2011 at 9:27
  • $\begingroup$ Well, it survived! $\endgroup$ Jan 21, 2011 at 10:29
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ That's interesting, I haven't heard about this! $\endgroup$
    – GH from MO
    Jan 18, 2011 at 9:00
0
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ 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$. $\endgroup$ Jan 18, 2011 at 2:53

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.