# Using elementary methods to prove infinitely many primes mod n

I was reading an elementary number theory text looking to enhance my knowledge and I came across the relatively simple task of proving there existed infinitely many primes of the form $$4k-1$$ (of course, without Dirichlet). My very elementary proof is as follows:

Assume there exist only $$n$$ finitely many such primes: then let $$m=4(p_1p_2\cdots p_n)-1$$. This is a (odd) number of the form $$4k-1$$ and thus must have factors of form $$4k-1$$, for otherwise the number would be of the form $$4k+1$$.

Is there such a simple generalization of this proof? I can see that this proof does not work for some, such as the $$4k+1$$ case found here. For instance, please provide a similar proof that there exists infinitely many primes of the form $$15k+4$$ (randomly chosen numbers). Thanks.

This question has been asked many times. These are called Euclidean proofs of special cases of Dirichlet's theorem on primes in arithmetic progressions. Keith Conrad has a nice article on it, which includes a complete characterization of when such a proof exists. Thanks to the characterization, since $$4^2\equiv 1\pmod{15},$$ there exists such a proof in the case that you requested, though I don't know what explicit polynomial would be used.
By the way, a Euclidean proof does exist in the $$1\pmod 4$$ case. You can use the polynomial $$n^2+1,$$ but you need to include $$2$$ in the product of the presumed finite list of prime to get the contradiction.
EDIT: I found a polynomial for $$15k+4$$ with proof in pages 92-94 of Problems in Algebraic Number Theory. It is $$n^4-n^3+2n^2+n+1.$$ The brother of one of the authors recommended the book to me years ago, but it never suited me... finally found use for it.
• @JJM See my edited post. It includes a reference to a polynomial for $15k+4.$ Jul 4, 2020 at 16:55