There exists a prime congruent to $m$ mod $p$

Solution 1:

I don't want to prove Dirichlet's theorem. Is it obvious that there always exists at least one such prime?

It is not obvious, and in fact the claim "if $\gcd(m, n) = 1$ then there is at least one prime congruent to $m \bmod n$" is equivalent to the claim "if $\gcd(m, n) = 1$ then there are infinitely many primes congruent to $m \bmod n$."

The implication $\Leftarrow$ is obvious. To prove the implication $\Rightarrow$, suppose we want to prove that there are infinitely many primes congruent to $m \bmod n$. We can do this by using the existence of

• at least one prime congruent to $m \bmod n$
• at least one prime congruent to $m + n \bmod 2n$
• at least one prime congruent to $m + 2n \bmod 3n$

etc. This produces a sequence $p_k$ of primes congruent to $m + kn \bmod (k+1)n$, which gives a sequence of primes congruent to $m \bmod n$ where $p_k \to \infty$ and so the sequence $p_k$ contains infinitely many primes.