Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T00:14:22Z http://mathoverflow.net/feeds/question/52318 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? Tommaso Centeleghe 2011-01-17T14:11:37Z 2011-01-18T06:38:36Z <p>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.</p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52319#52319 Answer by GH for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? GH 2011-01-17T14:15:10Z 2011-01-17T14:15:10Z <p>Of course. Take a quadratic nonresidue $1\leq n\leq p-1$, then some prime divisor $\ell$ of $n$ will be a quadratic nonresidue.</p> <p>See <a href="http://mathoverflow.net/questions/52211/effective-chebotarev-density/52237#52237" rel="nofollow">this MO question</a> for what is known about number fields.</p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52327#52327 Answer by Andrei Moroianu for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? Andrei Moroianu 2011-01-17T15:49:58Z 2011-01-17T15:49:58Z <p>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$).</p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52351#52351 Answer by Will Jagy for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? Will Jagy 2011-01-17T22:10:29Z 2011-01-17T22:10:29Z <p>Slightly different in emphasis, the smallest quadratic nonresidue is in fact prime, as the product of residues is another residue.</p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52368#52368 Answer by arithboy for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? arithboy 2011-01-18T01:21:36Z 2011-01-18T01:21:36Z <p>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$.</p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52385#52385 Answer by Péter Komjáth for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? Péter Komjáth 2011-01-18T06:38:36Z 2011-01-18T06:38:36Z <p>Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root <code>$q&lt;p$</code> for $p$ which is prime. </p>