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?

  • $\begingroup$ This question of mine and the answer by Bjorn Poonen deals with many special cases - mathoverflow.net/questions/15220/… $\endgroup$ – François G. Dorais Jul 20 '10 at 12:16
  • 1
    $\begingroup$ Here is the similar question - mathoverflow.net/questions/16735/… $\endgroup$ – Nurdin Takenov Jul 20 '10 at 12:19
  • $\begingroup$ I also had a related question mathoverflow.net/questions/25956. $\endgroup$ – Wadim Zudilin Jul 20 '10 at 12:40
  • $\begingroup$ 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. $\endgroup$ – Wadim Zudilin Jul 20 '10 at 12:45
  • $\begingroup$ 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. $\endgroup$ – falagar Jul 20 '10 at 13:06

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.

  • $\begingroup$ 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. $\endgroup$ – Wadim Zudilin Jul 20 '10 at 13:59
  • $\begingroup$ 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. $\endgroup$ – Daniel Litt Jul 20 '10 at 14:04
  • $\begingroup$ I have enjoyed! But I have already used my vote... :-( $\endgroup$ – Wadim Zudilin Jul 20 '10 at 14:14
  • $\begingroup$ You mean b=24, not b less than or equal to 24. $\endgroup$ – paul Monsky Jul 21 '10 at 0:01
  • $\begingroup$ You're right, fixed. $\endgroup$ – 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.


I found this generalization of the "$3 \pmod{4}$" version while teaching number theory a few years ago.

Let $G$ be a proper subgroup of $(\mathbb{Z}/n)^\times$. Then there are infinitely many primes $p$ such that $[p]\in (\mathbb{Z}/n)^\times$ and $[p]\not\in G$.

Proof: Suppose as usual that there are finitely many, $p_1, p_2, \ldots, p_r$, and find a number $g$ such that $(p_i,g) = 1$ for all $i$ and $[g]\not\in G$. Then the number $N = np_1 p_2 \cdots p_r + g$ has a prime factorization $N = q_1q_2 \cdots q_s$ satisfying

  • $q_i \neq p_j$ for all $i$ and $j$ and
  • since $[N]=[g]\not\in G$, $[q_i]\not\in G$ for at least on $i$.
  • $\begingroup$ I have no doubt it is correct, but I find it hard to follow. Why is it obvious that the conditions on $g$ can be fulfilled? In particular it is not immediately clear to me that one condition does not exclude the other... $\endgroup$ – RP_ Mar 16 '17 at 1:17
  • $\begingroup$ Since all the $p_i$ are prime to $n$ you can use the Chinese Remainder Theorem to produce $g$. $\endgroup$ – Jeff Strom Mar 16 '17 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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