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

-