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?

  • 1
    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
up vote 8 down vote accepted

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.

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.