pode ter infinitos primos somente quando a e q são coprime, ou seja, seu maior divisor comum é um. Se essa condição necessária for satisfeita, o teorema de Dirichlet sobre progressões aritméticas afirma que a progressão contém infinitos primos. A figura abaixo ilustra isso com q = 9: os números são "contornados" assim que um múltiplo de 9 é passado. Os primos são destacados em vermelho. As linhas (= progressões) iniciadas com a = 3, 6 ou 9 contêm no máximo um número primo. Em todas as outras linhas (a = 1, 2, 4, 5, 7 e 8), existem infinitos números primos. Além disso, os números primos são distribuídos igualmente entre essas linhas no longo prazo - a densidade de todos os números primos congruentes a um módulo 9 é 1/6.
Se a e q são coprime, qual teorema sustenta que uma progressão aritmética possui um número infinito de primos?
Dirichlet