# 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?

• Maybe I get somethiing wrong, but the existence of such prime is obviously equivalent to the Dirichlet's theorem – Sasha May 30 '15 at 20:27

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.