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?

up vote 4 down vote accepted

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

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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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