Another Watered Down Version of Dirichlet's Theorem Dirichlet's theorem states that given integers $a,b$ with $(a,b)=1$, there are infinitely many primes $p$ such that $p \equiv a \pmod b$. Much has been made of special cases of this theorem that are easy to prove without analysis, but suppose one only needed to know that _there exists_ such a prime (i.e. replace "infinitely many" with "one"). Can anyone think of a relatively straightforward way to prove this?

Suppose that we know that for **every** $a$ and $b$ such that $a$ and $b$ are relatively prime, **there exists** a prime $p$ such that $p\equiv a\pmod{b}$.

We will show that one can then use this to conclude that for every such $a$ and $b$, there are infinitely many primes $p$ such that $p\equiv a\pmod {b}$. That says that _existence_ of a prime is the difficult part.

Assume first that $a$ is not prime. There are primes $p$ congruent to $a$ modulo $b^N$ for any positive integer $N$. Such a prime is congruent to $a$ modulo $b$, and is $\ge a+b^N$. If $b\gt 1$, that process produces infinitely many primes congruent to $a$ modulo $b$.

If $a$ is prime, there is a $k$ such that $a+kb$ is not prime. Note that $a+kb$ and $b$ are relatively prime. Now we can use the argument of the previous paragraph.