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$.

  • $\begingroup$ Well, those are some days I'm not getting back. $\endgroup$ – Darth Geek Dec 23 '15 at 21:21
  • $\begingroup$ It does feel initially much weaker. $\endgroup$ – André Nicolas Dec 23 '15 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.