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

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.

• Natural is to use analytic methods. In fact, an $L$-function is natural for studying primes, e.g., the Riemann zeta function. – Dietrich Burde Mar 20 '17 at 23:24
• Selberg published an "elementary" proof, but I doubt that will meet your requirements. – Robert Israel Mar 20 '17 at 23:27
• Reinvent L-functions. There are a few special cases you can handle using tricks involving polynomials but already for primes congruent to $2 \bmod 5$ I think there is no hope. – Qiaochu Yuan Mar 20 '17 at 23:29
• The best way to think to it is the proof you learnt : $L(s,\chi) = \prod_p (1-\chi(p)p^{-s})^{-1}$. For $Re(s) > 1/2$ : $\log L(s,\chi) = \sum_p \chi(p) p^{-s}+ O(1)$ so that $\sum_{\chi \bmod b} \chi(a)\log L(s,\chi) = \phi(b) \sum_{p \equiv a \bmod b} p^{-s} + O(1)$, and it reduces to show the last series diverges for some $Re(s) > 1/2$. – reuns Mar 20 '17 at 23:30
• What is the precise meaning of $\log L(s,\chi) = \sum_p \chi(p)p^{-s} + O(1)$? I'm familiar with big O notation for functions of a real domain, but not complex. – D_S Mar 21 '17 at 5:18

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?

• That can be proved in a more direct way too, avoiding an argument by contradiction. Suppose $(a,m) = 1$ and we have primes $p_1, \ldots, p_r \equiv a \bmod m$. We may assume $1 \leq a \leq m-1$. (The case $m=1$ is trivial.) There is $k \geq 1$ such that $m^k > p_i$ for $i = 1,\ldots,r$. The congruence $p \equiv a + m^k \bmod m^{k+1}$ has a prime solution by WD, and from $0 < a + m^k < m^{k+1}$ we have $p \geq a+m^k > p_i$ for all $i$, so $p$ is not any of the $p_i$ and obviously $p \equiv a \bmod m$. – KCd Mar 29 at 7:04