Infinitely many of one kind

Every prime above two is odd, so every prime above two leaves a remainder of one or three on division by four. There are infinitely many primes; therefore at least one of those two classes holds infinitely many. Which one?

The honest answer, from that argument alone, is that nobody can tell. It is the pigeonhole principle applied to two boxes, and it gives no information about either box. To learn something about a class, the argument that produced the primes has to be aimed at it.

This rung is about aiming. Some classes can be reached by rewriting Euclid’s construction; one important class needs a different construction entirely; and the general statement — every class that could hold infinitely many primes does — is a theorem of a different order of difficulty from anything else on this ladder.

One thing to settle first, since it is the reason the question is not empty. Both classes modulo four really do hold infinitely many primes, so nothing here is a story about one class quietly running out. What is at stake is which proofs are available, and the answer differs between two classes that behave identically in every measurement — which is a good demonstration that the difficulty of a theorem is not a property of the objects it is about.

Which classes could hold primes at all #

Fix a modulus $q$ and ask which remainders a prime can leave. If the remainder $a$ shares a factor $d > 1$ with $q$, then every number leaving that remainder is divisible by $d$, so the only prime that can leave it is $d$ itself. Those classes are ruled out by arithmetic before any question of scarcity arises.

The classes that survive are those with no common factor with $q$, and there are $\varphi(q)$ of them. For $q = 4$ that is two classes; for $q = 10$ it is four, which is why every prime past five ends in 1, 3, 7 or 9.

The count $\varphi(q)$ is Euler’s totient, and it is worth recognising here rather than looking up, because it is the same count that appears in every statement below. It is how many numbers below $q$ share no factor with it, and it is multiplicative: $\varphi(10) = \varphi(2)\varphi(5) = 1 \times 4 = 4$, which is the Chinese remainder correspondence in action — a remainder modulo ten is a remainder modulo two together with one modulo five, and it is coprime to ten exactly when both parts are coprime to their own modulus.

Dirichlet’s theorem, 1837. If $a$ and $q$ share no factor, the class of numbers leaving remainder $a$ on division by $q$ contains infinitely many primes.

That is the general statement, and it settles every question this rung asks. It is also, by a wide margin, the hardest thing quoted anywhere on this ladder: the proof introduces characters, builds an $L$-function for each, and turns the infinitude into the non-vanishing of those functions at a point. Nothing about it resembles Euclid.

So the interesting question is not whether the theorem is true. It is how far the elementary method gets before it has to hand over.

Aiming Euclid’s construction #

Take the class $3 \bmod 4$. Suppose the primes in it are $p_1, \ldots, p_k$ and build

$$N = 4 p_1 p_2 \cdots p_k - 1.$$

The argument in three steps. $N$ is odd, so all its prime factors are odd, and each is 1 or 3 mod 4. If every one were 1 mod 4, their product would be 1 mod 4 — because the classes multiply, and one times one is one — but $N$ is 3 mod 4. So some prime factor is 3 mod 4. And no listed prime divides $N$, since each divides $4p_1 \cdots p_k$ and would then have to divide 1.

That is Euclid’s proof with one extra observation inserted: the class of a product is determined by the classes of its factors. Everything else is unchanged, including what the argument does not claim — $N$ itself is usually composite, and here it is.

The same rewriting works for $5 \bmod 6$, and for $q - 1$ modulo any $q$, for exactly the same reason — a class of $-1$ is not a product of classes that are all $1$.

One detail deserves care, because it is where a first attempt at this argument usually goes wrong. The construction has to be started with the correct list. If the primes 3, 7, 11 are all the primes that are 3 mod 4 — the assumption being refuted — then the argument produces a contradiction. If they are merely some of them, as here, the argument produces a prime in the class that is not among them, which is the same conclusion stated without a contradiction. The second reading is the better one and it is available: nothing above assumed the list was complete, and the figure’s list is simply the first three primes of the class.

The class the construction cannot reach #

Now try $1 \bmod 4$ by the same route. Build $4p_1 \cdots p_k + 1$, which is 1 mod 4, and ask what its factors look like.

Nothing follows. A number that is 1 mod 4 can perfectly well be a product of two numbers that are both 3 mod 4, since three times three is nine, which is one. The step that carried the previous argument has no analogue, and the reason is not a gap in ingenuity: the conclusion the step would need is false.

The construction that works squares instead of multiplying, and the reason it works is a theorem about squares rather than about products.

Let $p$ be an odd prime factor of $m^2 + 1$. Then $m^2 \equiv -1 \pmod p$, so $-1$ is a square modulo $p$. And $-1$ is a square modulo an odd prime exactly when that prime is 1 mod 4 — which is the first supplement to quadratic reciprocity, and is proved by pairing the numbers below $p$ off into inverse pairs and counting.

So every prime factor of $m^2 + 1$ is 1 mod 4, without exception. Take $m = 2p_1 \cdots p_k$ and the factors are all in the class, none of them is on the list, and the class holds a prime the list did not.

Three details of that construction are load-bearing and none is decoration. The factor of two in $m = 2p_1 \cdots p_k$ makes $m^2 + 1$ odd, which is what lets the supplement apply to every one of its factors. The listed primes cannot divide $m^2 + 1$, since each divides $m$ and would then have to divide 1. And the conclusion is about every factor rather than some factor, which is stronger than the previous construction managed and is why the figure can shade the whole column.

The two classes therefore need different theorems. One needs only that classes multiply; the other needs a fact about which numbers are squares modulo a prime. That asymmetry is real and it runs through the whole subject: which primes a quadratic form represents is a question about residues, and the primes that are sums of two squares are exactly the ones this construction produces.

How far the elementary method reaches #

There is a pattern to which classes admit an argument of this kind, and it is known exactly.

An elementary Euclid-style proof exists for the class $a \bmod q$ when $a^2 \equiv 1 \pmod q$ — that is, when $a$ is its own inverse. The classes $-1$, $+1$ and their relatives satisfy it; most classes do not.

The reason is the same in every case. A construction of this type produces a number whose class is forced, and concludes that some factor lies in the target class. That conclusion needs the target class to be un-avoidable by products of other classes, and the classes that are their own inverses are exactly the ones with that property. For $q = 8$, the classes 1, 3, 5, 7 all square to 1, and all four are reachable. For $q = 7$, the class 3 does not square to 1, and no such construction is known — nor can one exist in the restricted sense the theorem covers.

Worked through for a small modulus, the condition is easy to apply. Modulo twelve the live classes are 1, 5, 7 and 11, and every one of them squares to 1 — $5^2 = 25$, $7^2 = 49$, $11^2 = 121$, each one more than a multiple of twelve. So all four admit elementary arguments, and twelve joins 1, 2, 3, 4, 6, 8, 12 and 24 on the short list of moduli where the method covers every class. Modulo seven the live classes are 1 through 6, and only 1 and 6 square to 1; the other four are out of reach, and the primes 3 mod 7 are known to be infinite only by Dirichlet’s theorem.

That the list of fully covered moduli is finite — eight of them, and the largest is 24 — is the sharpest way to state where the elementary method stands. It is not a method with a few awkward cases left over. It is a method that handles all classes for eight moduli and some classes for the rest.

That is a satisfying place for a method to stop, because it stops at a stated condition rather than at the edge of what anybody has tried. It also explains why Dirichlet’s proof needs machinery: it must handle classes for which no purely multiplicative bookkeeping can work.

What Dirichlet does instead #

The elementary constructions above pick out a class by an arithmetic accident — the class of $-1$, or the class where $-1$ is a square. Dirichlet’s proof picks out a class deliberately, and the way it does so is worth a paragraph even though the rest is out of reach here.

The device is a filter. To count only the primes in the class $a \bmod q$, take a collection of functions $\chi$ on the remainders, each turning multiplication into multiplication and each sending remainders to roots of unity. Averaging them against $\chi(a)^{-1}$ gives a function that is 1 on the class and 0 everywhere else, so a sum over all primes, weighted by that average, becomes a sum over the primes in the class alone. The class has been isolated by a sum, rather than by a construction.

The work then moves to each $\chi$ separately, in the shape of a product over primes of the same kind Euler wrote for the ordinary primes. The whole proof reduces to showing that none of these products vanishes at a particular point, and for one troublesome kind of $\chi$ that non-vanishing is genuinely hard.

Two things follow from that shape and both matter to this rung. The proof gives every coprime class at once, with no case analysis and no cleverness per class — which is exactly what the elementary method could not do. And it gives the density as well as the infinitude, because the sums it manipulates carry sizes and not merely non-emptiness.

The counts are almost equal, and that is a separate theorem #

Look again at the numbers in the figures. Modulo four: 4,783 and 4,808. Modulo six: 4,784 and 4,806. Modulo ten: four counts between 2,387 and 2,411.

Dirichlet’s theorem says each class is infinite. It does not say they are equally full — that is the stronger statement, proved later, that each class coprime to $q$ receives a fraction $1/\varphi(q)$ of all primes. The figures measure that fraction and find it holding to within half a percent at a hundred thousand.

They also show something the theorem does not predict, and it is worth not smoothing over. In every one of the pictures, the class of $-1$ leads: 4,808 against 4,783 modulo four, 4,806 against 4,784 modulo six. That lead is real, it persists over enormous ranges, and it has a name — Chebyshev’s bias. It is not a violation of equidistribution, since the ratio still goes to one; it is a persistent asymmetry in a race whose two runners finish level. A conditional theorem explains it: the classes containing squares are slightly behind, because the squares of primes accumulate in them and are counted by the smoothed version of the tally.

The measured shares are worth writing out, because they say how good the approximation is at a scale a reader can hold. Modulo ten the four live classes hold 2,387, 2,402, 2,411 and 2,390 primes, against 2,398 for a perfectly even split — a spread of about one percent across the four. Modulo four the spread is half a percent. The equidistribution is not asymptotic hand-waving at these sizes; it is already visible in the third significant figure.

The measurement is the reason to mention it. A figure that showed idealised equal bars would be quoting the theorem; these bars are counted off the sieve, so the small asymmetry is there whether or not anyone points at it, and pointing at it costs a sentence.

What the aiming does not buy #

Comparing the aimed constructions with the original shows what the extra work bought, and it is less than it looks.

It does not give a formula. Neither construction produces primes on demand; both produce a number with an unlisted prime factor somewhere in it. The factorisation still has to be found, and for large lists it cannot be.

It does not give the first prime in the class. The construction on the list 3, 7, 11 produced 71, which is the eleventh prime of the class rather than the fourth. Nothing orders the primes it finds, and running the construction repeatedly does not enumerate the class — it jumps about inside it, revisiting nothing and skipping most of it.

It does not give a rate. Euclid’s argument squeezed for a bound gives a count growing like the logarithm of a logarithm, and aiming it does not improve that. The true density of each class — a fraction $1/\varphi(q)$ of the primes, which is nearly all of them — is invisible to these methods entirely.

And it does not extend to conditions that are not congruences. Primes one more than a square, primes of the form $2^n - 1$, primes separated by two: none of these is a class modulo anything, and no rearrangement of this argument reaches them. That is the boundary the next rung is about, and it is where the pattern of ask, aim, prove stops working.

What this rung settles #

Three statements, of three different characters.

Some restricted infinitudes are as elementary as the unrestricted one. The class $-1 \bmod q$ takes six lines and one observation about products.

Some need a genuine theorem from elsewhere. The class $1 \bmod 4$ needs the fact that $-1$ is a square modulo exactly the primes of that class, which is a result about residues and not about infinitude at all.

And the general case needs analysis. Dirichlet’s proof is not an elaboration of Euclid’s; it is a different subject applied to the same question, and the fact that the answer is uniform across all $\varphi(q)$ classes is invisible from the elementary side, where each class needs its own trick or has none.

There is one more asymmetry worth recording, because it cuts the other way. The elementary arguments are constructive in a sense Dirichlet’s is not: run the construction and a number appears with an unlisted prime factor of the required class inside it, and for small lists that factor can be found. The analytic proof produces no number at all. So on this ladder the weaker method is the one that hands over an object, and the stronger one is the one that only counts — which is the same trade the density arguments make everywhere in this subject.

Which is the useful lesson about proofs of infinitude: the difficulty is not in producing infinitely many objects, it is in producing them where they are asked for. Euclid’s construction was never short of primes; it was short of control over which primes it found. Everything on this rung is the price of that control.