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

Dirichlet's theorem states that for any coprime $k$ and $m$ there exists infinitely many primes $p$ such that $p \equiv k \pmod m$.

Some special cases of this theorem are easy to prove without any analytic methods. Those cases include, for example, $m=4, k=1$ and $m=4, k=3$.

Both cases could be proved by considering first $t$ prime numbers $p_i \equiv k \pmod m$ and constructing a new number which is proved to have prime divisor $p \equiv k \pmod m$ that is not equal to any $p_i$.

For case $m=4, k=1$ we can consider number $(p_1 p_2 \cdots p_t)^2 + 1$. And for case $m=4, k=3$ number $4p_1 p_2 \cdots p_t + 3$.

Those constructions could also be applied to some other special cases as well.

Are there any other special cases for which there exists a simple non-analytic proof which don't use any of those two constructions?

share|cite|improve this question
This question of mine and the answer by Bjorn Poonen deals with many special cases -… – François G. Dorais Jul 20 '10 at 12:16
Here is the similar question -… – Nurdin Takenov Jul 20 '10 at 12:19
I also had a related question – Wadim Zudilin Jul 20 '10 at 12:40
Please explain what do you mean by "a simple non-analytic proof". If one of the two mentioned above, then $m$ should involve only 2s and 3s in its prime factorisation. – Wadim Zudilin Jul 20 '10 at 12:45
Actually I want proof that is niether of two mentioned in the question. By "a simple non-analytic proof" I mean a proof that doesn't use any of classical analysis. – falagar Jul 20 '10 at 13:06
up vote 15 down vote accepted

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

share|cite|improve this answer
Daniel, I am trying to decide whether your approach is "elementary enough" (of course, the cyclotomic polynomials do not belong to "classical analysis" but analytic proofs for $p\equiv1\pmod m$ are simpler as well; the latter ones, in some sense, generalise the above elementary trick for $3\pmod4$). Thanks for the closed- and open-access links. – Wadim Zudilin Jul 20 '10 at 13:59
Hmm...the proof that infinitely many primes divide the image of a polynomial on the integers is essentially Euclidean, which is why I consider this to be elementary; of course I find the analytic proofs in this case preferable as well. You may also enjoy the analytic proof for $p\equiv 1 \bmod 4$ I give in the note as well, which uses some very cute trickery based on representations via sums of squares. – Daniel Litt Jul 20 '10 at 14:04
I have enjoyed! But I have already used my vote... :-( – Wadim Zudilin Jul 20 '10 at 14:14
You mean b=24, not b less than or equal to 24. – paul Monsky Jul 21 '10 at 0:01
You're right, fixed. – Daniel Litt Jul 21 '10 at 13:18

As Daniel has pointed out, there is an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv1$ (mod $n$). There is an also an elementary proof that for each $n$ there are infinitely many primes $p$ with $p\equiv-1$ (mod $n$). This can be found in Nagell's Introduction to Number Theory section 50 in the second edition.

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.