Back to the on-screen lesson ·
Which progressions hold infinitely many primes, how evenly they share them, and where this course's methods run out.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether an arithmetic progression can contain more than one prime, count how many progressions modulo a given number can contain primes, state Dirichlet's theorem and its strong form about even distribution, prove the case of three modulo four by adapting Euclid's argument, and say why that adaptation does not generalise.
Lesson 6 sorted the integers by their remainder on division by $n$, into $n$ classes. Lesson 12 counted how many of those classes are coprime to $n$: $\varphi(n)$ of them.
Lesson 25 counted the primes below a bound. Put the two together and the question is unavoidable: how are the primes distributed among those classes? Most classes obviously cannot hold more than one prime, since every member shares a factor with the modulus. The remaining $\varphi(n)$ are where the primes must live, and whether each gets its share is the last question of this course.
An arithmetic progression is $a, a + q, a + 2q, \ldots$ — the integers congruent to $a$ modulo $q$. Here $q$ is the modulus and $a$ the starting residue.
A residue $a$ is admissible when $\gcd(a, q) = 1$. There are $\varphi(q)$ admissible residues modulo $q$.
The natural density of a set of primes is the proportion of primes it contains, in the limit. Dirichlet's theorem in its strong form says each admissible class has density $1/\varphi(q)$.
A Dirichlet character modulo $q$ is a multiplicative function on the residues, extending the Legendre symbol of unit 4. The proof of the theorem is built out of them.
The necessary condition. If $d = \gcd(a, q) > 1$ then $d$ divides every term $a + kq$, so no term above $d$ can be prime. Such a progression holds at most one prime.
Dirichlet's theorem (1837). If $\gcd(a, q) = 1$ then the progression $a, a+q, a+2q, \ldots$ contains infinitely many primes.
So the obvious obstruction is the only obstruction. There is no progression that avoids the primes for a subtler arithmetic reason — which is a much stronger statement than it looks, since it rules out every conceivable alternative mechanism at once.
The strong form. The primes are shared out evenly: $$\pi(x; q, a) \sim \frac{1}{\varphi(q)}\cdot\frac{x}{\ln x}.$$ Each of the $\varphi(q)$ admissible classes gets the same share in the limit. Modulo $4$ the primes split evenly between $4k+1$ and $4k+3$; modulo $10$ they split evenly between last digits $1, 3, 7, 9$.
Special cases are elementary; the theorem is not. For $q = 4$, $a = 3$: take a finite list of such primes, form $N = 4q_1\cdots q_k - 1$, note $N \equiv 3 \pmod 4$, and observe that a product of primes all $\equiv 1$ must be $\equiv 1$ — so some factor is $\equiv 3$, and it is off the list. The same trick works for $6k+5$ and $8k+5$.
It breaks for $a = 1$. There is no way to force a prime factor into the class of $1$, because a product of numbers $\equiv 3$ can be $\equiv 1$. Dirichlet's proof instead attaches an infinite series to each character modulo $q$ and shows those series do not vanish at a particular point — which is analysis, not arithmetic, and is where this course's methods run out.
What is still unknown. Whether every admissible progression contains infinitely many twin primes; how early the first prime in a progression must appear (Linnik's bound is far beyond anything observed); and whether the error term in the strong form is as small as the generalised Riemann hypothesis predicts.
Another way: steps
Another way: example
Modulo $10$: $\varphi(10) = 4$, so the admissible last digits are $1, 3, 7, 9$ and each holds about a quarter of the primes. Up to $10^{6}$ there are $78\,498$ primes, so about $19\,600$ ending in each — the true counts are $19\,617$, $19\,665$, $19\,621$ and $19\,593$. Even, to within a quarter of a per cent.
Dirichlet's theorem is the natural end of this course because it is the first statement here whose proof the course's methods cannot reach — and seeing exactly where they fail is worth more than another elementary result would be.
What the elementary method does. Euclid's construction forces a prime into a class by building a number whose residue is known. For $4k + 3$ this works: a product of numbers $\equiv 1 \pmod 4$ is $\equiv 1$, so a number $\equiv 3$ must have a factor $\equiv 3$.
Where it fails. For $4k + 1$ there is no such forcing. A product of numbers $\equiv 3 \pmod 4$ can be $\equiv 1$ — $3 \cdot 7 = 21 \equiv 1$ — so knowing $N \equiv 1$ tells you nothing about its factors. (This particular case can be rescued with the first supplement of unit 4, using $N = (2q_1\cdots q_k)^{2} + 1$ and the fact that $-1$ is a square only modulo primes $\equiv 1 \pmod 4$. But the rescue is special, and there is no version of it for general $q$.)
What Dirichlet did instead. He attached to each character $\chi$ modulo $q$ the series $$L(s, \chi) = \sum_{n \ge 1}\frac{\chi(n)}{n^{s}},$$ which factors over the primes exactly as Euler's product did. Combining these over all $\varphi(q)$ characters isolates a single residue class, and the theorem reduces to showing $L(1, \chi) \ne 0$ for every non-trivial character. That non-vanishing is the whole difficulty, and it is an analytic fact with no arithmetic proof.
That is the boundary. Elementary number theory reasons about divisibility, congruences and factorisation, and this course has been an account of what those alone can settle — which is a very great deal: the whole of units 1 to 4, Pell's equation, the two-square theorem, RSA. Analytic number theory brings limits, series and complex functions to bear on the same objects, and it is what the last two lessons have had to quote rather than prove.
The Riemann hypothesis sits on that side. It is a statement about the zeros of a complex function, and it is about the primes: it says the error in the prime number theorem is as small as it could possibly be. The generalised version says the same for every progression. Whether those are true is the largest open question in the subject, and the road to it starts exactly here.
Thinking a progression with a common factor holds no primes. It holds at most one — the shared factor itself, when it happens to be prime and to appear. The progression $3, 9, 15, \ldots$ contains $3$ and nothing else.
Expecting the theorem to say where the first prime is. It is pure existence. Linnik's theorem supplies a bound, and it is far larger than anything ever observed.
Reading even distribution as exact equality. The classes get equal shares in the limit. At finite bounds there are biases — the class of $3$ modulo $4$ leads the class of $1$ for almost every bound anyone has checked, a phenomenon called Chebyshev's bias, and the lead reverses infinitely often.
Assuming the elementary proof generalises. It handles $4k+3$, $6k+5$, $8k+5$ and a handful more, and there is no elementary proof for general $q$. The special cases are special.
Confusing this with primes in a polynomial. Whether $n^{2} + 1$ is prime infinitely often is open. Dirichlet's theorem is about linear progressions, and degree two is a different and unsolved problem.
Modulo $10$ the admissible residues are those coprime to $10$: $1, 3, 7, 9$. So $\varphi(10) = 4$ classes can hold primes.
The other six last digits are ruled out by a shared factor.
The classes $0, 2, 4, 5, 6, 8$ hold at most one prime each — and only $2$ and $5$ actually do.
At most one, and usually none.
Dirichlet's theorem says the four admissible classes each hold infinitely many, and the strong form says each holds about a quarter. Up to a million the counts are $19\,617$, $19\,665$, $19\,621$, $19\,593$ — even to within a quarter of a per cent.
Evenly, and not exactly.
For $4k + 3$: take a finite list of such primes and form $N = 4q_1\cdots q_k - 1 \equiv 3 \pmod 4$. A product of primes all $\equiv 1$ would be $\equiv 1$, so some factor is $\equiv 3$, and it divides neither the product nor $1$.
Euclid's argument plus one observation about residues.
For $4k + 1$ the same attempt fails: knowing $N \equiv 1 \pmod 4$ forces nothing about its factors, since $3 \cdot 7 = 21 \equiv 1$.
The forcing step is exactly what is lost.
That case can be rescued with $N = (2q_1\cdots q_k)^{2} + 1$: any prime factor $p$ has $-1$ as a square modulo $p$, so $p \equiv 1 \pmod 4$ by the first supplement. But the rescue uses unit 4 and does not generalise to arbitrary $q$.
A special argument, and the reason Dirichlet needed a general one.
A class can hold more than one prime only if its residue is coprime to $12$.
The necessary condition first.
$\varphi(12) = \varphi(4)\varphi(3) = 2 \cdot 2 = 4$, and the residues coprime to $12$ are $1, 5, 7, 11$.
Count with the totient, then list.
By Dirichlet's theorem all four hold infinitely many, each getting about a quarter of the primes. The other eight classes hold at most one prime each — only $2$ and $3$ in fact.
For each progression, say whether it contains infinitely many primes or at most one.
| infinitely many primes | at most one prime | |
|---|---|---|
| starting at $6$, stepping by $11$ | ||
| starting at $4$, stepping by $6$ | ||
| starting at $7$, stepping by $9$ |
Sorting the integers by their remainder on division by $4$ gives $4$ progressions. How many of them contain infinitely many primes?
Answer:
Does the progression $5, 14, 23, \ldots$ — starting at $5$ and stepping by $9$ — contain infinitely many primes?
The progression starts at $1$ and steps by $7$. Give its first three terms, and then the first prime it contains.
| Value | |
|---|---|
| First term | |
| Second term | |
| Third term | |
| First prime in the progression |
What is the first prime congruent to $9$ modulo $10$?
first prime a
Dirichlet's theorem is out of reach here, but one case of it is not. Build the proof that there are infinitely many primes congruent to $3$ modulo $4$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For each progression, say whether it contains infinitely many primes or at most one.
| infinitely many primes | at most one prime | |
|---|---|---|
| starting at $4$, stepping by $11$ | ||
| starting at $3$, stepping by $9$ | ||
| starting at $3$, stepping by $4$ |
You can say which arithmetic progressions hold infinitely many primes and roughly how the primes are shared between them. Say in your own words why the elementary proof works for three modulo four and not for one modulo four. That is the end of the course: divisibility, congruences, the classical theorems, quadratic reciprocity, Diophantine equations and the distribution of the primes.
9. Your turn: how many residues modulo $12$ can contain infinitely many primes, and which?, step 3