No era esta pregunta para que mi respuesta fue unusally popular, por lo que me atrevo a preguntar lo siguiente:
(1) Dado un primer $p>2$, ¿cuántos números primos $\ell < p$ no existen residuos cuadráticos mod $p$?
(2) Dado un primer $p>2$, ¿cuántos números primos $\ell < p$ no existen cuadrática nonresidues mod $p$?
Como para (1) puedo probarlo $\gg\log p/\log\log p$ elemental argumento. De hecho, poner $p':=(-1)^{(p-1)/2}p$ y observar, por la reciprocidad cuadrática, que un primer $\ell\neq p$ divide algún valor $x^2-p'$ para $x\in\mathbb{Z}$ si y sólo si $\ell$ es una ecuación cuadrática de residuos de mod $p$. Ahora considere el $|x^2-p'|$ para $0 < x < \sqrt{p}$: estos son los números enteros en $(0,p)$ o $(p,2p)$ dependiendo $p$ mod $4$. En cualquier caso, estos números se construyen a partir de la $k$ primos enumerados en (1), y su número es $\gg\sqrt{p}$. Como cada una de las $k$ primer exponentes es $\ll\log p$, llegamos a la conclusión de $\sqrt{p}\ll(\log p)^k$ y mi reclamo de la siguiente manera.
Añadido 1. Como Anónimo señaló, se debe restringir a impar $0 < x < \sqrt{p}$, y hablar de la extraña parte de $|x^2-p'|$. Además, el uso de la cota superior de la parte de (7.16) en la p. 203 de Montgomery-Vaughan: Multiplicativo de la Teoría de números (prueba en las páginas 204-208), podemos ver $k>(\log p)^{2-o(1)}$ para el número de números primos menores (1).
Agregó 2. Con respecto a (2), Lucía señaló que $\gg p^\delta$ sigue con una decente $\delta>0$ a partir de un resultado de Bourgain y Lindenstrauss. He encontrado esta respuesta muy satisfactoria, y he aceptado oficialmente. Aún así, me daría la bienvenida a cualquier novedad con respecto a las preguntas anteriores (1) y (2).
Añadido 3. La reciente preprint de Pablo Pollack contiene varios buenos resultados nuevos y valiosos referencias históricas respecto a los dos anteriores preguntas. Aún más reciente preprint por él y Kübra Benli se asienta (1) en el sentido de que no se $\gg p^{1/9}$ primer residuos cuadráticos $\ell<p$.
