Krdytkyu

Q: Is every element of $mathbb Z/pmathbb Z$ represented by a prime number? More generally, let $m, n in mathbb Z$ be coprime. Is there a prime number congruent to $m$ modulo $n$?

the affirmative answer is given by Dirichlet's theorem.

A: Yes, in fact there are infinitely many such primes.

I don't want to prove Dirichlet's theorem. Is it obvious that there always exists at least one such prime?

I don't want to prove Dirichlet's theorem. Is it obvious that there always exists at least one such prime?

It is not obvious, and in fact the claim "if $gcd(m, n) = 1$ then there is at least one prime congruent to $m bmod n$" is equivalent to the claim "if $gcd(m, n) = 1$ then there are infinitely many primes congruent to $m bmod n$."

The implication $Leftarrow$ is obvious. To prove the implication $Rightarrow$, suppose we want to prove that there are infinitely many primes congruent to $m bmod n$. We can do this by using the existence of

• at least one prime congruent to $m bmod n$
  


• at least one prime congruent to $m + n bmod 2n$
  


• at least one prime congruent to $m + 2n bmod 3n$
  

etc. This produces a sequence $p_k$ of primes congruent to $m + kn bmod (k+1)n$, which gives a sequence of primes congruent to $m bmod n$ where $p_k to infty$ and so the sequence $p_k$ contains infinitely many primes.

It is possible to prove some cases without Diriclet's Theorem for $ax+b$ with $a$ and $b$ coprime. Without going into too much deatail for the proofs, they are:

any integer $a$ and $b=1, -1$

$a=2, 3, 4, 6, 8, 12, 24$ and $b$ is coprime to $a$

If you are given forms $ax+b$ and $ax+c$, say, it is also possible to prove that there are infintely many primes of the form $ax+b$ OR $ax+c$ (but does not prove the form individually). This happens exactly when $b^4=1pmod a$ and $b^3=cpmod a$.

This answer is inspired by Qiaochu's idea, with a small correction mentioned in the comments there. Call the statement below ${bf P}(q)$:

If $(m,n) = 1$ then there exist $q$ distinct primes congruent to $m text{mod } n$.

The goal is to show that ${bf P}(1) implies {bf P}(infty)$ by repeatedly applying ${bf P}(1)$ to higher and higher multiples of $n$, with different lifts of $m$.

To makes this work, one must find numbers of the form $m + ell$ for which $n, |, ell$ and which are coprime to some large multiple of $n$. This will be done using the following (obvious) fact:

Let $m$ and $n$ be coprime, let $ell geq 1$, and let $N$ be a multiple of $n$ which is also coprime to $m$. Then $m+ell$ is coprime to $N$ if $text{rad}(N), |, ell$.

In particular, the numbers $m_i := m + n^i$ are coprime to $n^{k+1}$ for each $i in [1,k]$. Applying ${bf P}(1)$ to each $m_i$, one finds $k$ distinct primes congruent to $m$ mod $n$, deducing ${bf P}(k)$.

${bf P}(1) implies {bf P}(k)$ for any $k in mathbb N$, so ${bf P}(infty)$ follows.