There exists a prime congruent to $m$ mod $p$ 
Q: Is every element of $\mathbb Z/p\mathbb Z$ represented by a prime number? More generally, let $m, n \in \mathbb Z$ be coprime. Is there a prime number congruent to $m$ modulo $n$?

the affirmative answer is given by Dirichlet's theorem.
 A: Yes, in fact there are infinitely many such primes.

I don't want to prove Dirichlet's theorem. Is it obvious that there always exists at least one such prime?
A: 
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. 
A: It is possible to prove some cases without Diriclet's Theorem for $ax+b$ with $a$ and $b$ coprime. Without going into too much deatail for the proofs, they are:
any integer $a$ and $b=1, -1$
$a=2, 3, 4, 6, 8, 12, 24$ and $b$ is coprime to $a$
If you are given forms $ax+b$ and $ax+c$, say, it is also possible to prove that there are infintely many primes of the form $ax+b$ OR $ax+c$ (but does not prove the form individually). This happens exactly when $b^4=1\pmod a$ and $b^3=c\pmod a$.
A: This answer is inspired by Qiaochu's idea, with a small correction mentioned in the comments there. Call the statement below ${\bf P}(q)$:

If $(m,n) = 1$ then there exist $q$ distinct primes congruent to $m\ \text{mod } n$.

The goal is to show that ${\bf P}(1) \implies {\bf P}(\infty)$ by repeatedly applying ${\bf P}(1)$ to higher and higher multiples of $n$, with different lifts of $m$.

To makes this work, one must find numbers of the form $m + \ell$ for which $n\, |\, \ell$ and which are coprime to some large multiple of $n$. This will be done using the following (obvious) fact:

Let $m$ and $n$ be coprime, let $\ell \geq 1$, and let $N$ be a multiple of $n$ which is also coprime to $m$. Then $m+\ell$ is coprime to $N$ if $\text{rad}(N)\, |\, \ell$.

In particular, the numbers $m_i := m + n^i$ are coprime to $n^{k+1}$ for each $i \in [1,k]$. Applying ${\bf P}(1)$ to each $m_i$, one finds $k$ distinct primes congruent to $m$ mod $n$, deducing ${\bf P}(k)$.
${\bf P}(1) \implies {\bf P}(k)$ for any $k \in \mathbb N$, so ${\bf P}(\infty)$ follows.
