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

Given an integer $n$ and let $1\leq m\leq n$ be such that $n$ and $m$ are coprimes define $$ \mathcal{N_{n,m}}:=\text{the set of primes $p$ such that $p\equiv{m}\hspace{0.1cm}\mathrm{mod}(n)$}. $$ Let $\mathcal{P}$ be the set of all primes. I seem to recall that the following result is true: $$ \varphi(n)^{-1}=\lim_{k\to\infty}{\frac{|\mathcal{N_{n,m}}\cap\{1,2,\ldots,k\}|}{|\mathcal{P}\cap\{1,2,\ldots,k\}|}}. $$ where $\varphi$ is the Euler's function.

My question is two fold:

  • Does anyone have a reference for the previous fact? I was unsuccesful finding it.
  • Are there finer results along these lines? Second order results?


share|cite|improve this question
This is due to Dirichlet. See… – wood Apr 6 '11 at 12:59
@wood: Clearly not, it implies the PNT. – Charles Apr 6 '11 at 14:29
@Charles, in principle one could prove that the primes in one residue class are $1/\phi(n)$ of all the primes without knowing the asymptotics of either counting function, thus, without PNT, no? I agree that Dirichlet did not do this. – Gerry Myerson Apr 7 '11 at 0:07
up vote 10 down vote accepted

A good way to find the result you mentioned is to search for Dirichlet's (prime number) theorem; while Dirichlet only proved the infinitude of the set in question, nowadays one will frequently find the more precise assertion you mentioned when this result is discussed.

A more common way to state it is that the number of primes congruent to $m$ modulo $n$ smaller than $x$ is asymptotically equal to $\varphi(n)^{-1} x/log (x) $ (assuming coprimeness as you did), which in combination with the prime number theorem implies what you are looking for.

There are a variety of results related to finer aspects of this problem; key words e.g. Bombieri-Vinogradov Theorem or Siegel-Walfiz Theorem.

See for example the wikipedia article on Dirichlet's theorem here which also links to the keywords I mentioned for a quick overview.

Other than that as Gerry Myerson said any typical book on Analytic Number Theory will contain something on this subject (how much depends of course on the book).

share|cite|improve this answer
The $x/\log x$ result can't be Dirichlet's, as it would imply the prime number theorem, which came about 60 years after Dirichlet's work. – Gerry Myerson Apr 6 '11 at 13:19
+1 for the pointer to Siegel-Walfisz. – Gerry Myerson Apr 6 '11 at 13:21
I don't have the reputation to comment but what about the second question? Are there more precise results? – Val Apr 6 '11 at 13:27
@Gerry Myerson, of course you are right I was imprecise (and will change this). And, sorry for the wrong spelling of your name. – user9072 Apr 6 '11 at 13:31
Yes, see 2nd paragraph of unknown (google)'s answer for keywords. – Gerry Myerson Apr 6 '11 at 13:31

It's just the prime number theorem for primes in arithmetic progression, no? Should be in any analytic number theory text that does the prime number theorem.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.