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:

$\displaystyle \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

$\displaystyle 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

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

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

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

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

$\displaystyle 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:

$\displaystyle 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]).

William 2007-06-01