2 proofs of Dirichlet's theorem

In An Introduction to the Theory of Numbers by G.H. Hardy and E.M. Wright (Oxford 1938, 5th ed. 1979, pp13,14), we are told that Dirichlet's theorem is "too difficult for insertion in this book."

The claim:

If a ∈ Z⁺ and a and b relatively prime, then there are infinitely many primes of the form an + b.

First proof:

To begin with, we note that if a and b are not relatively prime, then either a = kb or b = jan. That is an + b = kbn + b = b(kn + 1), which is composite. Likewise, if an + b = an + jan, then an(j + 1) is composite.

So let us make a = 2 and b = 1. We now have 2n + 1, which for n ∈ Z, gets all odd numbers. Euclid's theorem shows there is an infinitude of odd primes, with the only non-odd prime being 2. Hence the infinitude of primes intersects the set of odd numbers. Hence the claim is satisfied.

---

Second proof

This is essentially a generalization of the first proof.

To start, we let a = 3 and b = 1. This gives the pattern

3(1) + 1 = 4
3(2) + 1 = 7
3(3) + 1 = 10

Now we let b = 2, for

3(1) + 2 = 5
3(2) + 2 = 8
3(3) + 2 = 11

3(1) + 3 = 6
3(2) + 3 = 9
3(3) + 3 = 12

By this method, we obtain all the integers > a. And, in general, for any integer a, we obtain all integers by following the above algorithm, whereby one has a sequences of integers.

This shows that any integer can be made to satisfy the form an + b. Hence there is an infinitude of primes with this form.