MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Has it been proved or disproved that for any fixed $a\geq 1$ there are infinitelly many primes $p_n\equiv a\pmod{n}$?
I believe i have proved that for every $a\geq1$ there are infinitelly many natural numbers $m$ with $m\equiv a\pmod{\pi(m)}$ where $\pi(m)$ is the prime counting function and i was wondering if this can be also true for a smallest subset of $\mathbb{N}$ (the primes).

OEIS does not tell much.
Any reference would be appreciated.
Thank you for viewing.

share|cite|improve this question
How did you prove that $m\equiv a\pmod{\pi(m)}$ has infinitely many solutions $m$ for any fixed $a$? – Michael Zieve Oct 31 '13 at 23:54
@Michael Zieve using the fact that $\pi(m)=\omicron(m)$ and that $\pi(m+1) -\pi(m)=0$ or $1$. If you divide $m-a$ with $\pi(m)$ the residue must be sometimes zero because if not, $\frac{m-a}{\pi(m)}$ will be always too small.In fact i believe that this same argument could be applied not only to a fixed $a$ but to any slowly increasing sequence $a(m)$ of natural numbers as well.But this is just hypothetical. – Konstantinos Gaitanas Nov 1 '13 at 0:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.