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.
Best Answer
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}$.