Given a prime $p$, find all quadratic residues modulo $p$. We randomly select a number $n$ among these quadratic residues modulo $p$. What is the probability of $n$ being a prime as $p$ goes to infinity?

I use A132213 and A000224 to estimate the answer. The answer might be approximately 12%. However, I am wondering if there is a standard proof.

  • $\begingroup$ Given the prime number theorem, you can be sure that the answer is not a fixed value. $\endgroup$ – Joffan Jan 21 '17 at 16:12
  • $\begingroup$ The number of quadratic residues in $\{1,2,\ldots,p-1\}$ mod $p$ is $(p-1)/2$. The number of these which are primes is $O(\dfrac{p}{\log p})$. So surely the probability as $p$ goes to infinity is just zero? $\endgroup$ – Aravind Jan 22 '17 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.