# Proving there are infinite primes of some form $a+nd$

I know by Dirichlet's theorem on arithmetic progressions that there are infinitely many primes of any type $a+nd$, where $a$ and $d$ are positive co-prime integers.

I come across many questions like - prove that there are infinitely many primes of form $4k+1, 6k+1, 6k+5, 8k+1,$ etc. where they use either quaratic residues or take some form of a number formed by the finite (assumed) set of primes of that form and then reach a contradiction.

I want to know how to tackle any such problem requiring to prove it for a certain form, it seems very non-trivial to me to begin.

• There are informative answers at this MO-question. – Dietrich Burde Nov 5 '17 at 12:25
• @DietrichBurde I don't want the proof of Dirichlet's theorem, I want how should we go about proving it for a certain form like $7k+3$ for eg. – john doe Nov 5 '17 at 12:28
• You can use the "Euclidean proof" as in $4k+1$ etc. , if and only if Murty's criterion is met, see my answer. So the answer is, that you must use more analytic arguments involving $L$-series for cases like $7k+3$. Of course, all cases follow from Dirichlet's Theorem anyway. – Dietrich Burde Nov 5 '17 at 12:29

A Euclidean proof, as for $4k+1,6k+1,6k+5,8k+1$ etc. is not always possible. In fact, we have the following Theorem:
Theorem 1. (Murty) A “Euclidean proof” exists for the arithmetic progression $l \bmod k$ if and only if $l^2 \equiv 1 \bmod k$.