Dirichlet's theorem on primes in arithmetic progression 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.
 A: A couple more references:
Ram Murty and Nithum Thain,
Prime numbers in certain arithmetic progressions,
Paul Pollack, 
Hypothesis H and an impossiblity theorem of Ram Murty.
A: 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}$.  
A: There are similar proofs for primes of the forms $4n+1$ and $4n+3$.
Suppose $p_1,\ldots,p_k$ are all primes of the form $4n+1$. Consider $$P = (p_1 \cdots p_k)^2 + 2^2.$$ Since $P$ is a sum of two squares but not a square (or twice a square) itself, it must have a prime factor $q$ of the type $4n+1$ (by Fermat's theorem on numbers representable as sums of two squares). Since $P \mod p_i = 4 \mod p_i \neq 0$, $q$ is a new prime of the form $4n+1$.
Suppose $p_1,\ldots,p_k$ are all primes of the form $4n+3$. Consider $P = p_1 \cdots p_k + C$, where $C$ is chosen to be either $2$ or $4$ so that $P$ itself is of the form $4n+3$. Since primes of the form $4n+1$ never multiply to a number of the form $4n+3$, $P$ must have a prime number $q$ of the type $4n+3$. As before, $q$ must be new.
