Dirichlet's Theorem on arithmetic progressions is often stated as something like:
Every arithmetic progression where the first term and the difference are coprime contains an infinite amount of primes.
But can be rewritten as:
If $(a,m) = 1$ then there are infinite primes $p$ such that $p\equiv a\pmod m$.
I'm trying (fruitlessly) to come up with an elementary proof of its weak version.
If $(a,m) = 1$ then there is at least one prime $p$ such that $p\equiv a\pmod m$.
Note that if this is stated in terms of arithmetic progressions then it would not be a weak version (once you find one prime, consider the sequence with difference $m$ and first term $p + m$).
Any ideas?
Let $a$ be a non-prime, and suppose we know that there is a prime $p$ congruent to $a$ modulo $n$ for every $n$ relatively prime to $a$. Then for every positive integer $k$, there is a prime congruent to $a$ modulo $m^k$. From this it follows that there are infinitely many primes congruent to $a$ modulo $m$.
So for non-primes $a$, the weak version is equivalent to Dirichlet's Theorem. For primes $a$ the weak version is trivial. But from the assumption that for all $n$ relatively prime to $a$, there is a prime other than $a$ congruent to $a$ modulo $n$, we can again derive Dirichlet's Theorem. And if we are allowed to let $a$ vary, we can find a non-prime $a'$ of the form $a+qm$, and again conclude that there are infinitely many primes congruent to $a$ modulo $m$.