An arithmetic progression is a sequence of the form ak + b where a and b are fixed and k runs 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 3k + 7:
Can you guess what would happen if we considered the corresponding progression –3k + 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 progession ak + b
are the integers in the congruence class of b
modulo a. 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 b to the possible remainders on division by a. Given an integer a, there are a congruence 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 modulo a?"
The applet below looks at the first M primes and counts how many are in each different congruence class modulo a. 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 4Address 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? |