Intro to Dirichlet's Theorem

Dirichlet's theorem in prime number theory concerns prime numbers in arithmetic progressions $a,a+m,a+2m,\ldots$. (Here, $a$ and $m>1$ are integers.)

Which arithmetic sequences do you think contain infinitely many prime numbers?

Dirichlet's theorem asserts that the progression $a,a+m,a+2m,\dots$ contains infinitely many primes if and only if $a$ and $m$ are coprime.

Infinitude of Primes: Special Case $4n-1$

We have seen some proofs of infinitude of primes. Another important theorem related to infinitude of primes is Dirichlet's theorem. This states that for two co-prime integers $a$ and $n$, there are infinitely many $k$ such that $ak+n$ is a prime. And the proof is really hard. But here we discuss some special cases of this theorem which can be proven easily. Mostly using the idea Euclid used in his proof.

Theorem There are infinitely many primes of the form $4k-1$.

Proof For the sake of contradiction, assume the primes are $p_1,\ldots, p_n$. Consider the number $N=4p_1\cdots p_n-1$. If we divide this number by $4$, we get remainder $-1$, or $3$. Therefore, it must have a prime factor which is of the form $4k-1$. Otherwise, if all prime factors are of the form $4k+1$, their product will be $4K+1$ type too (check it!). Now, notice that, any prime factor $p$ of $N$ is co-prime to all primes of $p_1,\ldots,p_n$. Because if $p$ was one of them, $p$ would divide $1$, a contradiction! But this gives us a new prime $p$ which is of the form $4k-1$.

In the question, the last two options tried to connect Dirichlet's theorem with the number of primes in the progression. Try to prove the following statement, which may seem surprising at first.

If every arithmetic progression $a,a+m,a+2m,\ldots$ (where $a$ and $m>1$ are coprime integers) contains at least one prime number, then these progressions all contain infinitely many primes as well.

Theorem There are infinitely many primes of the form $4k+1$.

Try to prove it yourself. We will post the proof later.

Warning There is a catch in this proof. And the exercise is a followup of this post.