If $r$ and $n$ are two integers such that $\gcd(r, n) = 1$ and $r < n$, how do I prove the existence of a prime $p$ such that $p \equiv r \bmod n$?
I have found that Dirichlet's theorem on arithmetic progressions ensures that an infinity of these primes exist. However, I can't exactly use it nor do I have the tools to prove it.
So is there a way with simpler math to prove the existence of such a prime?
What you are asking for is logically impossible unless you happen to know that $r$ is prime.
Suppose you had a theorem that establishes the existence of "just one" prime $p = kn+r$. Since $r$ is not prime, surely $k \ge 1$. Now apply your theorem to the pair $(r,mn)$ where $m$ is any integer greater than $k$ and relatively prime to $r$. This new prime will be strictly greater than $p$ and still congruent to $r$ mod $n$. Continuing in this fashion will give an infinite number of primes from "just one".