Dirichlet's theorem on primes in arithmetic progressions: how to arrive at the result naturally?

Question

I've seen the following theorem proved several times in several different ways:

Let $a, b$ be relatively prime. There are infinitely many prime numbers in the sequence $a,a+b,a+2b, ...$

The most difficult part of the argument comes down to showing that if $\chi$ is a nontrivial Dirichlet character, then $L(s,\chi)$ does not vanish at $s = 1$.

I have understood the individual details of the arguments. But I have never felt like I really understand why the result is true.

Suppose you temporarily forgot what you knew about $L$-functions, Dirichlet density, Fourier analysis etc. You know basic number theory and complex analysis. How would you go about thinking about this problem in such a way as to naturally arrive at the result? If necessary, you can rediscover L-functions as part of the process, but please justify your discovery with intuition.

Answer 1

I don't know if this is what you're looking for, but I wager you'll find it interesting anyway. Consider the statements:

(Strong Dirichlet) For each $m>0$ and each $a$ relatively prime to $m$, there exist infinitely many primes $p \equiv a \pmod m$.

(Weak Dirichlet) For each $m>0$ and each $a$ relatively prime to $m$, there exists at least one prime $p \equiv a \pmod m$.

While the statement WD might look a lot weaker at first glance, we have the very elementary

Theorem. Strong Dirichlet is equivalent to Weak Dirichlet.

Proof. It is clear that SD implies WD.

Suppose on the other hand that WD holds, but not SD. We will derive a contradiction, which will show that WD implies SD.

If WD holds, but not SD, then there exists an $M$ and an $A$ such that $(M, A)=1$ and there are finitely many primes $p \equiv A \pmod M$; let $S$ be the set of these primes. Let $q>M$ be a prime large enough such that there exists a congruence class $B\not\equiv 0 \pmod q$ different from all elements of $S \pmod q$. Then, the simultaneous congruences

$$p \equiv A \pmod M$$ $$p \equiv B \pmod q$$

have no solution $p$ prime: the first imposes that $p \in S$, and the second rules it out. By the Chinese Remainder Theorem, these equations are equivalent to an equation of the form

$$p \equiv C \pmod{qM}$$

with $(C, qM)=1$, which has no solution; but this contradicts our assumption WD. Therefore WD implies SD.

So, modulo this elementary argument, it's just as hard to prove that there are infinitely many primes $p \equiv a \pmod m$ for any $(a,m)=1$ than it is to prove that there is always at least one such prime.

Is it easier to believe WD than SD? Personally I don't think so - what's left to believe anyways once you've internalised Dirichlet's proof?