There was [this question](https://mathoverflow.net/questions/52318/) for which my response was unusally popular, so I dare to ask the following:


(1) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic residues mod $p$?


(2) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic nonresidues mod $p$?


As for (1) I can prove $\gg\log p/\log\log p$ by an elementary argument. Indeed, put $p':=(-1)^{(p-1)/2}p$ and observe, by quadratic reciprocity, that a prime $\ell\neq p$ divides some value $x^2-p'$ for $x\in\mathbb{Z}$ if and only if $\ell$ is a quadratic residue mod $p$. Now consider $|x^2-p'|$ for $0 < x < \sqrt{p}$: these are integers in $(0,p)$ or $(p,2p)$ depending on $p$ mod $4$. At any rate, these numbers are built up from the $k$ primes enumerated under (1), and their number is $\gg\sqrt{p}$. As each of the $k$ prime exponents is $\ll\log p$, we conclude $\sqrt{p}\ll(\log p)^k$ and my claim follows.


**Added 1.** As Anonymous pointed out, we should restrict to odd $0 < x < \sqrt{p}$, and talk about the odd part of $|x^2-p'|$. In addition, using the upper bound part of (7.16) on p. 203 of Montgomery-Vaughan: Multiplicative Number Theory (proof on pp. 204-208), we can see $k>(\log p)^{2-o(1)}$ for the number of primes under (1). 


**Added 2.** Regarding (2), Lucia pointed out that $\gg p^\delta$ follows with a decent $\delta>0$ from a result of Bourgain and Lindenstrauss. I found this response very satisfactory, and I accepted it officially. Still, I would welcome any further developments regarding the above questions (1) and (2).


**Added 3.** The recent [preprint](https://arxiv.org/abs/1508.05035) of Paul Pollack contains several nice new results and valuable historic references regarding the above two questions. An even more recent [preprint](https://arxiv.org/abs/1711.01706) by him and Kübra Benli settles (1) in the sense that there are $\gg p^{1/9}$ prime quadratic residues $\ell<p$.



Given a prime $p$ how many primes $\ell<p$ of a given quadratic character mod $p$?
GH from MO and Anonymous have commented above on (modest) lower bounds for the first problem. Let me mention here that a version of problem 2 (of producing many non-residues) appeared in work of [Bourgain and Lindenstrauss](http://www.ma.huji.ac.il/~elon/Publications/pos_entropy.pdf) in connection with the QUE conjecture. In particular, from Theorem 5.1 of their paper it follows that there is a positive constant $\delta$ such that at least $p^{\delta}$ of the primes $\ell$ below $p$ are quadratic non-residues $\pmod p$. The proof is based on the fundamental lemma of sieve theory together with cancelation in character sums. 


Added: To elaborate, Theorem 5.1 of Bourgain and Lindenstrauss's paper shows that if $N=p^{\beta}$ with $\beta \ge 1/4+\epsilon$ then there exists $\alpha>0$ such that ($\ell$ runs over primes below)
$$ 
\sum\_{N^{\alpha} <\ell < N; (\frac{\ell}{p}) = -1} \frac{1}{\ell} \ge \frac 12 -\epsilon. 
$$ 
In particular the number of primes $\ell$ with $(\frac{\ell}{p}) =-1$ is trivially at least $(1/2-\epsilon)N^{\alpha}$. Now use this with $N=p$, and we deduce the result mentioned above. I didn't check the details, but I think one can get a pretty decent value of $\delta$ above -- maybe even as big as $3/8$ (the level of distribution is like $p^{\frac 34}$ and the sifting limit should be $1/2$).


