There are infinitely many primes that are one modulo any modulus

Statement

Let $D$ be a natural number. Then, there are infinitely many primes $p$ such that $p\equiv 1(\mathrm{mod}D)$.

Related facts

Stronger facts

• Dirichlet's theorem on primes in arithmetic progressions: This generalizes the result to any congruence class relatively prime to the modulus.
• Chebotarev density theorem

Weaker facts

• Infinitude of primes

Applications

This fact has applications in group theory, number theory, and many other areas. The main useful fact is that if $D|p-1$, the multiplicative group of the prime field of order $p$ has a cyclic subgroup of order $D$.

• Every finite group admits a sufficiently large prime field

Facts used

1. Congruence condition on prime divisor of cyclotomic polynomial evaluated at an integer
2. Set of prime divisors of values of nonconstant polynomial with integer coefficients is infinite

Proof

Consider the cyclotomic polynomial ${\mathrm{\Phi }}_D$. By fact (1), we have that for any integer $a$, all prime divisors of ${\mathrm{\Phi }}_D(a)$ either divide $D$ or are $1$ modulo $D$. The number of primes that divide $D$ is finite, whereas by fact (2), the total set of prime divisors dividing ${\mathrm{\Phi }}_D(a)$, as $a$ varies over positive integers, is infinite. Thus, the number of primes that is $1$ modulo $D$ is infinite.