Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Is there a proof in the spirit of Euclid to prove Dirichlet's theorem on primes in arithmetic progression? (By the spirit of Euclid, I mean assuming finite number of primes we try to construct another number which has a prime factor which falls in the same equivalence class as the other primes but the number is not divisible by any of the primes we considered in the initial list.)

I am aware of the proof using $L$ functions but I am curious to know if Euclid's "simple" idea can be extended to all other cases as well. I tried googling but am unable to find a proof other than the ones relying on $L$ functions. If it is not possible, to what cases can Euclid's idea be extended to?

Any other proofs are welcome as well.

share|cite|improve this question
You'll want to look at Keith Conrad's expository paper, "Euclidean proofs of Dirichlet's theorem", found at the following page: – Jonas Meyer Nov 22 '10 at 8:26
@Jonas: Thanks Jonas. – user17762 Nov 22 '10 at 8:43
up vote 10 down vote accepted

As Jonas says, Keith Conrad's paper will tell you that the answer is essentially no. He defines a certain notion of "Euclidean" proof coming from writing down a polynomial with certain properties and gives two classic results which say that these proofs exist for primes in arithmetic progression $a \bmod n$ if and only if $a^2 \equiv 1 \bmod n$.

The first case these proofs can't handle is primes congruent to $2 \bmod 5$ (equivalently, primes congruent to $3 \bmod 5$). The basic problem is that there is no way to force a positive integer to have factors congruent to $2 \bmod 5$ and not congruent to $3 \bmod 5$ (or the other way around) solely by controlling its residue class $\bmod 5$. In more sophisticated language, $2$ and $3$ lie in all the same subgroups of $(\mathbb{Z}/5\mathbb{Z})^{\ast}$.

share|cite|improve this answer
Thanks Qiaochu for short and concise answer. – user17762 Nov 22 '10 at 8:47

A couple more references:

Ram Murty and Nithum Thain, Prime numbers in certain arithmetic progressions,

Paul Pollack, Hypothesis H and an impossiblity theorem of Ram Murty.

share|cite|improve this answer

There are similar proofs for primes of the forms $4n+1$ and $4n+3$.

Suppose $p_1,\ldots,p_k$ are all primes of the form $4n+1$. Consider $$P = (p_1 \cdots p_k)^2 + 2^2.$$ Since $P$ is a sum of two squares but not a square (or twice a square) itself, it must have a prime factor $q$ of the type $4n+1$ (by Fermat's theorem on numbers representable as sums of two squares). Since $P \mod p_i = 4 \mod p_i \neq 0$, $q$ is a new prime of the form $4n+1$.

Suppose $p_1,\ldots,p_k$ are all primes of the form $4n+3$. Consider $P = p_1 \cdots p_k + C$, where $C$ is chosen to be either $2$ or $4$ so that $P$ itself is of the form $4n+3$. Since primes of the form $4n+1$ never multiply to a number of the form $4n+3$, $P$ must have a prime number $q$ of the type $4n+3$. As before, $q$ must be new.

share|cite|improve this answer
Thanks. Yup you could use similar arguments and quadratic residue arguments for primes in $(\mathbb{Z} / \mathbb{3Z})^{*}$ and $(\mathbb{Z} / \mathbb{8Z})^{*}$ – user17762 Nov 22 '10 at 9:11

Your Answer


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