Arithmetic progression

Consider

Each number is obtained by adding 6 to the previous one.

Or consider

Here the repeated step is 10\.

A sequence formed by repeatedly adding the same fixed amount is called an \\arithmetic progression\\. That fixed amount is called its \\common difference\\.

If the progression begins at $a$ and its common difference is $d$, its terms are

or, more compactly,

Arithmetic progressions and residue classes are closely connected. A progression with common difference d stays in a single residue class modulo d; with n \= 0, 1, 2, ... it traces that class in one direction from its starting point.

For example, $5,11,17,23,\ldots$ is an arithmetic progression with common difference 6\. At the same time, every term is congruent to 5 modulo 6\. Travelling along this progression therefore means repeatedly visiting the same residue class.

This connection becomes important for primes. We can ask whether the progression $5,11,17,23,29,\ldots$ keeps containing primes indefinitely, or whether there could eventually be a last prime in that lane.

Some progressions have an obvious obstruction. In

every term is divisible by 6\. Such a progression cannot contain infinitely many primes.

More generally, if the starting value and the common difference share a factor greater than 1, that shared factor is inherited by every term of the progression.

This leads to the condition in Dirichlet's theorem on primes in arithmetic progressions. If $q>0$ and

then the progression

contains infinitely many prime numbers.

($\gcd(a,q)=1$ means that the starting value $a$ and the step size $q$ have no positive common divisor larger than 1\. In other words, they are coprime. The separate glossary entries on greatest common divisor and coprime unpack this condition from first principles.)

This is a striking leap. A simple repeating sequence leads to a theorem saying not merely that we have found many primes in one arithmetic lane, but that the lane can never run out of them.

See also: modular arithmetic, residue class, coprime, greatest common divisor, prime number, distribution of primes.