Special cases of Dirichlet's theorem

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?

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

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.

• 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.

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$.
• 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... – RP_ Mar 16 '17 at 1:17
• Since all the $p_i$ are prime to $n$ you can use the Chinese Remainder Theorem to produce $g$. – Jeff Strom Mar 16 '17 at 1:46