Primes of the Form $ax+b$

Next we turn to primes of the form $ax+b$ , where $a$ and $b$ are fixed integers with $a>1$ and $x$ varies over the natural numbers $\mathbb {N}$ . We assume that $\gcd(a,b)=1$ , because otherwise there is no hope that $ax+b$ is prime infinitely often. For example, $2x+2=2(x+1)$ is only prime if $x=0$ , and is not prime for any $x\in\mathbb {N}$ .

Proposition 1.2   There are infinitely many primes of the form $4x-1$ .

Why might this be true? We list numbers of the form $4x-1$ and underline those that are prime:

$$\underline{3}, \underline{7}, \underline{11}, 15, \underl... ... 27, \underline{31}, 35, 39, \underline{43}, \underline{47}, \ldots$$

Not only is it plausible that underlined numbers will continue to appear indefinitely, it is something we can easily prove:

Proof. Suppose $p_1, p_2, \ldots, p_n$ are distinct primes of the form $4x-1$ . Consider the number

$$N = 4p_1 p_2 \cdots p_n - 1.$$

Then $p_i \nmid N$ for any $i$ . Moreover, not every prime $p\mid N$ is of the form $4x+1$ ; if they all were, then $N$ would be of the form $4x+1$ . Thus there is a $p\mid N$ that is of the form $4x-1$ . Since $p\not= p_i$ for any $i$ , we have found a new prime of the form $4x-1$ . We can repeat this process indefinitely, so the set of primes of the form $4x-1$ cannot be finite. $\qedsymbol$

Note that this proof does not work if $4x-1$ is replaced by $4x+1$ , since a product of primes of the form $4x-1$ can be of the form $4x+1$ .

Example 1.2   Set $p_1=3$ , $p_2=7$ . Then

$$N = 4\cdot 3 \cdot 7 - 1 = \underline{83}$$

is a prime of the form $4x-1$ . Next

$$N = 4\cdot 3 \cdot 7\cdot 83 - 1 = \underline{6971},$$

which is again a prime of the form $4x-1$ . Again:

$$N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 - 1 = 48601811 = 61 \cdot \underline{796751}.$$

This time $61$ is a prime, but it is of the form $4x+1 = 4\cdot 15+1$ . However, $796751$ is prime and $796751 = 4\cdot 199188 - 1$ . We are unstoppable:

$$N = 4\cdot 3 \cdot 7\cdot 83\cdot 6971 \cdot 796751 - 1 = \underline{5591}\cdot 6926049421.$$

This time the small prime, $5591$ , is of the form $4x-1$ and the large one is of the form $4x+1$ .

Theorem 1.2 (Dirichlet)   Let $a$ and $b$ be integers with $\gcd(a,b)=1$ . Then there are infinitely many primes of the form $ax+b$ .

Proofs of this theorem typically use tools from advanced number theory, and are beyond the scope of this book (see e.g., [#!frohlichtaylor!#, §VIII.4]).