An arithmetic progression is a sequence of the form

ak+bwhereaandbare fixed andkruns through integer values. The goal of this section is to discover whatever we can about primes in arithmetic progessions.Let's start by looking at some terms of the arithmetic progression 3

k+ 7:

Can you guess what would happen if we considered the corresponding progression –3

k+ 7?

It was exactly the same, except for the ordering. It is not hard to see why this will happen in general, so we will restrict to positive values for

a. Next observe that the integers in the progessionak+bare the integers in the congruence class ofbmoduloa. For example, the numbers of the form 3k+ 7 are the integers congruent to 7 modulo 3. We could get the same set by taking integers of the form 3k+ 1 because 7 1 (mod 3).

Keep in mind that we are seeing only part of an infinite sequence of numbers; adjust the bounds on the sequences to convince yourself that we are seeing the same set.

We can now safely restrict the values of

bto the possible remainders on division bya. Given an integera, there areacongruence classes and each integer is in one of those congruence classes. Our questions about primes in arithmetic progressions can be thought of in terms of "how do the primes divide themselves among the different congruence classes moduloa?"The applet below looks at the first

Mprimes and counts how many are in each different congruence class moduloa. As a first example, let's try it on the congruence classes modulo 5 and the first 100 primes.

The number of primes that are congruent to 1 is listed first, the number congruent to 2 is listed second, and so on. So, the computation tells us that 24 of the first 100 primes are congruent to 1 modulo 5. The last entry says that only one of the first 100 primes is congruent to 5 modulo 5.

## Research Question 4

Address the three questions given in the introduction of this chapter for numbers of the form

ak+b:1. Under what conditions is an integer of this form always prime?

2. Under what conditions is an integer of this form always composite?

3. Are there infinitely many primes of this form?

Section 6.1 | Section 6.2 | Section 6.3 | Section 6.4

Copyright © 2001 by W. H. Freeman and Company