Exercise 2196Number theory › PrimesM1Added 3 Nov 2026

Primes in arithmetic progressions

#Dirichlet theorem#arithmetic progression#primes

Statement

State Dirichlet's theorem on primes in arithmetic progressions and illustrate it for $a=3$ , $b=4$ .

Hint

For $\gcd(a,b)=1$ , the progression $a, a+b, a+2b,\ldots$ contains infinitely many primes.

Show solutionHide solution

Theorem (Dirichlet). If $\gcd(a,b)=1$ , then the arithmetic progression $a+nb$ ( $n\ge0$ ) contains infinitely many primes.

Example. $a=3$ , $b=4$ : primes of the form $4k+3$ : $3,7,11,19,23,31,43,47,\ldots$ Infinitely many.

Contrast. $a=0$ , $b=2$ : no primes beyond $2$ (all even).

Conclusion. Coprimality of $a$ and $b$ is necessary; Dirichlet's theorem shows it is also sufficient.