It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} \}$ must lie in certain arithmetic progressions, with a finite number of exceptions. This is because any nonconstant polynomial must have infinitely many distinct prime divisors, which one can prove in a manner imitating Euclid's proof of the infinitude of the primes. For example, taking $p(x) = \Phi_n(x)$, we can prove Dirichlet's theorem for primes congruent to $1 \bmod n$. It is known (see, for example, this paper of K. Conrad) that this is possible precisely for the primes congruent to $a \bmod n$ where $a^2 \equiv 1 \bmod n$.

However, the result about polynomials having infinitely many prime divisors has the following generalization: any sequence $a_n$ of integers which is eventually monotonically increasing and which grows slower than $O(2^{\sqrt[k]{n}})$ for every positive integer $k$ has infinitely many distinct prime divisors. In particular, any sequence of polynomial growth (not necessarily a polynomial itself) has this property.

Question 1: Given an arithmetic progression $a \bmod n, (a, n) = 1$ such that $a^2 \not \equiv 1 \bmod n$, is it ever still possible to efficiently construct a monotonically increasing sequence of positive integers satisfying the above growth condition such that, with finitely many exceptions, the prime divisors of any element of the sequence are congruent to $a \bmod n$? ("Efficiently" rules out answers like "the positive integers divisible by primes congruent to $a \bmod n$," since I do not think it is possible to write down this sequence efficiently. On the other hand, evaluating a polynomial is very efficient.) The idea is that such a sequence immediately gives a proof of Dirichlet's theorem for primes congruent to $a \bmod n$ generalizing the Euclid-style proofs.

Question 2: If the above is not possible, are there any known techniques for proving Dirichlet's theorem or at least some of the special cases not covered above without resorting to the usual analytic machinery? For example, Selberg published an "elementary" proof in 1949, but it relies on the "elementary" proof of the prime number theorem, which to me is "finitary analytic machinery." What is the absolute minimum amount of analysis necessary to produce a proof? (Edit: In response to a suggestion in the comments, one way to describe the kind of answer I'm looking for is that it would generalize to a proof of Chebotarev's density theorem that shows very clearly where the distinction between the number field and function field cases is; aside from some "essential" analytic argument there should be no difference between the two.)

This question is inspired at least in part by the following observation: Dirichlet's theorem is equivalent to the seemingly weaker statement that for every progression $a \bmod n, (a, n) = 1$ there exists at least one prime congruent to $a \bmod n$. The reason is that if there exists some such prime $a_1$, then letting $n_1$ be the smallest multiple of $n$ greater than $a_1$, there exists a prime congruent to $a_1 + n \bmod n_1$, and so forth.

  • 3
    $\begingroup$ On the other hand, you could ask for a purely algebraic proof of the Cebotarev density theorem, e.g. a proof which does not (in some sense) distinguish between the number field and function field cases. As with so many things in mathematics, Bjorn Poonen would be a good person to ask about this. $\endgroup$ Mar 1, 2010 at 3:21
  • 1
    $\begingroup$ Selberg's proof just rubs me the wrong way; unlike the Galois-theoretic proof of FTA I linked to above, I do not get a good sense of where the "essence" of the analytic argument lies. I guess a good way to quantify "essence" is, as you say, to ask for a uniform proof of the Chebotarev density theorem. $\endgroup$ Mar 1, 2010 at 3:34
  • 3
    $\begingroup$ Can you give us an example illustrating your question 1? To fix ideas, let's consider the progression 2 mod 5, for which the Euclid-style proofs do not exist. What is a sequence a_n which solves your question 1 in this example? Since you're asking whether one can always find an efficiently constructed sequence, I'd first like to see you produce just one that is not in the spirit of the Euclid proofs. $\endgroup$
    – KConrad
    Mar 1, 2010 at 3:55
  • 1
    $\begingroup$ I was under the impression that Selberg's proof could be formalized in first-order arithmetic. (Using real numbers here and there doesn't immediately disqualify you. For example, you can often replace them with rationals modulo buffering with a few extra epsilons.) $\endgroup$ Mar 1, 2010 at 14:55
  • 11
    $\begingroup$ Using only Selberg's symmetry formula and elementary divisor sum manipulations, one can show that the primes mod q are either equidistributed in the coprime classes, or equidistributed in half of coprime residues corresponding to where some quadratic character $\chi$ equals 1. This is the best one can do without importing somewhere a proof that $L(1,\chi) \neq 0$, which seems to require some nontrivial machinery at some point. This is discussed in this paper of Granville: ams.org/mathscinet-getitem?mr=1220462 $\endgroup$
    – Terry Tao
    Nov 28, 2011 at 4:59

4 Answers 4


The question whether there are infinitely many primes in some coprime residue class mod m is stronger than asking whether there are infinitely many primes with given inertia index in the field of mth roots of unity, which is a special case of Chebotarev's density. The possibility of elementary proofs of the latter was discussed, as you know, over here.

It seems that Dirichlet's technique is perfectly natural for this kind of questions. Before he started using Euler's ideas on zeta functions, he played around with Legendre's approach (Legendre had tried to prove the result in his 2nd edition of his Théorie des nombres since he had used special cases in his "proof" of the quadratic reciprocity law), but without success.

Another attempt at giving an "elementary" proof was made by Italo Zignago:

His proof was, however, incorrect.

BTW, question 1 goes back to the correspondence of Euler and Goldbach; they tried (in vain) to find a sequence of numbers divisible only by primes of the form $4n+3$. Eventually, Euler convinced himself that quadratic forms $x^2 + my^2$ won't do.


For more on Murty's result that the usual elementary approach is doomed to failure look at Paul Pollack's paper Hypothesis H and an impossibility theorem of Ram Murty (Wayback Machine). There he shows that a commonly believed conjecture implies a generalization of Murty's result to a broader type of Euclidean proof.


I was struggling to find an elementary proof of Dirichlet's theorem using another interesting technique. I came finally to a proof from an entirely different direction but as I found out Erdos came first before many years. The proof is not well known (I never understood why no one mentions it!) and it uses Chebyshev type estimates. Here is the proof: http://kam.mff.cuni.cz/~klazar/ln_antcII.pdf (Wayback Machine) I hope this will be helpful!

We are looking for prime numbers of the form $a+nm$, $(a,m)=1,n=1,2,\dots$.

The general plan is: $n!$ divides the product of $n$ consecutive terms of the arithmetic progression $a+m,a+2m,\dots,a+nm$ with $(a,m)=1$ (if we disregard the factor of $n!$ which includes divisors of $m$)

For example, consider the progression $1+3m$:

$4\cdot7\cdot10\cdot13\cdot16\cdot19\cdot22$ is divided by $7!/3^2$ (The factor that we "disregard" is $3^2$)

It is easy to prove in analog with Legendre's Lemma on binomial coefficients, that the highest power of a prime $p$ which divides $\frac{(a+m)\cdot(a+2m)\cdots(a+nm)}{n!}$ does not exceed $a+nm$.

The problem is that such a prime $p$ could not be of the form that is wanted. For example turning back to $\frac{4\cdot7\cdot10\cdot13\cdot16\cdot19\cdot22}{7!/3^2}$ we find 11 as a divisor which is a prime of the form $2+3m$.

We wish to simplify the unwanted primes from the "big" fraction which Erdos calls $Pn(a,m)$. In order to do this we divide $Pn(a,m)$ with a fraction of the same kind but from another progression $a'+nm$ with $(a',m)=(a,m)=1$.

(The "other" progression for $1+3m$ is $2+3m$ since 1 and 2 are the only numbers coprime to 3 and less than 3).

But we find that in $Pn(a,m)$ every prime of the form $a'+km$ which is greater than $n$ exists exactly once, so (and here is the big idea) dividing $Pn(a,m)$ with $P(n/h)(a',m)$ ($h$ is the number with the property $a'h=a \pmod m$ ) every prime of the form $a'+km$ which is greater than $n$ cancels.

Continuing like this you can cancel every unuseful prime that exceeds $n$ and have only "small" unuseful primes whose product is significantly smaller than $Pn(a,m)$.

With this, you prove that primes of the form $a+nm$ have a product which tends to infinity and so they are infinite.

I hope this is helpful.

(note) We use $h$ because the smallest term of the progression $a+nm$ that is divided by a prime $p$ of the form $a'+km$ is the term $a+km=h\cdot p$.

  • $\begingroup$ The notes you link to talk of Erdos's "partial proof". Could you please explain whether Erdos's proof is elementary or not? $\endgroup$
    – Yemon Choi
    Aug 22, 2013 at 16:48
  • $\begingroup$ @Yemon Choi I made some edit i hope this looks much more convincing now. $\endgroup$ Aug 22, 2013 at 18:28
  • 10
    $\begingroup$ @Yemon Choi: Erdos's argument is completely elementary, but it doesn't prove Dirichlet's theorem for all $m$: It works only when $\sum_{p < m, p \nmid m}\frac{1}{p} < 1$. Elementary estimates show that this condition is satisfied for only finitely many $m$, and Pieter Moree showed in 1993 that the largest of these is $m=840$. There's a full and readable exposition of Erdos's proof in HN Shapiro's wonderful book Introduction to the theory of numbers (recently reprinted by Dover). Let me also mention that closely related arguments were given by A.S. Bang, G. Ricci, and D. Roux. $\endgroup$ Aug 22, 2013 at 21:45

I like the approach of looking for a sequence of integers with prime divisors that are guaranteed to be in a certain arithmetic progression. One can try taking the iterates of a polynomial, starting with an integer. For example use $x^2-2x+2$ starting with 3, and you get the sequence 3,5,17,.. and you can show that any prime divisor of the kth term is $\equiv 1 \mod 2^k$ (not what was requested but a good start). I have no idea how to generalize this to get any new example, like $2 \mod 5$, but I find it intriguing. One might also try to iterate using $x^2+c$ (or any rational function) and look at the prime factors of the numerator. The Galois theory of such iterates perhaps suggests one won't escape the limitations of the "Euclidean proofs"


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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