The fact that there are infinitely many prime numbers was a previous theorem of the week. This week, I’d like to pursue the idea a bit further.

Let’s think about the primes when we divide them by 2. What do we get? Well, the first prime (2) is even, but then all the others are odd. Why is that? An even number has a factor of 2, so the only way in which an even number can be prime is if it is itself 2.

Now let’s think about the primes when we divide them by 4. What do we get? Here are the first few primes:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

And here are the remainders when we divide those by 4:

2, 3, 1, 3, 3, 1, 1, 3, 3, 1, 3, 1, 1, 3, 3, 1, 3, 1, 3, 3, 1, 3, 3, 1, 1.

What can we notice about those remainders? Perhaps the most obvious thing is that apart from the initial 2, all the remainders are 1 and 3. The 1s and 3s don’t seem to have a clear pattern that I can see (they don’t alternate, for example), but the numbers of them are pretty similar (11 1s and 13 3s). Can we make any guesses about what happens after the first 25 primes? Is the remainder ever anything other than 1 or 3 (except for that initial 2)? Are there infinitely many 1s and 3s, or will the sequence eventually settle on one? If it doesn’t settle on one, are there the same numbers of 1s and 3s?

It’s reasonably easy to see that the remainder when we divide a prime by 4 must be 1 or 3 (unless the prime is 2). Perhaps you’ve already worked that out. Apart from 2, every prime number is odd (as we saw above). And numbers that leave remainder 0 or 2 when divided by 4 are even. So prime numbers (apart from 2) leave remainder 1 or 3 when divided by 4. That’s that settled.

So, to the next questions. Are there infinitely many primes that leave remainder 1 when divided by 4? Are there infinitely many primes that leave remainder 3 when divided by 4? These are not as easy as the last question, but are not too hard. It turns out that the answer is “Yes” to both questions. I think I’ll let you find a proof for yourself, as it’s a nice exercise, but I’ll give you a couple of hints. I described Euclid’s proof that there are infinitely many primes. Suitable variants of that will give proofs that there are infinitely many primes leaving remainder 1 when divided by 4 and infinitely many primes leaving remainder 3 when divided by 4.

Are there the same numbers of primes leaving remainder 1 and remainder 3 when divided by 4? It turns out that the answer is yes (when the question is interpreted carefully), but that’s harder to prove, so I’ll leave it for now.

What would happen if we replaced 4 by 6, for example? Here are the remainders when the first few primes are divided by 6:

2, 3, 5, 1, 5, 1, 5, 1, 5, 5, 1, 1, 5, 1, 5, 5, 5, 1, 1, 5, 1, 1, 5, 5, 1.

Hopefully you will be able to convince yourself that apart from 2 and 3, every prime leaves remainder 1 or 5 when divided by 6. But are there infinitely many of each sort? Notice that this time there are 11 primes leaving remainder 1 when divided by 6 and 12 leaving remainder 5 — again, the numbers are very close.

It starts getting a bit harder to prove that there are infinitely many primes leaving remainder 1 when divided by 6, and infinitely many leaving remainder 5 when divided by 6. And anyway, we’re mathematicians, so we’d like a more general strategy.

What would a more general strategy mean? Suppose I fix some number q, and we think about the remainders when we divide the primes by q. If a and q have a common factor greater than 1, then we’re not going to get many primes with remainder a when divided by q (either no primes at all, or just one). Remember that there was only one prime with remainder 2 when divided by 6, and none at all with remainder 4 when divided by 6. So those are the boring cases that we can eliminate immediately. But what if a and q have no common factor greater than 1: what if a and q are coprime? Then we have no obvious reason why there shouldn’t be infinitely many primes leaving remainder a when divided by q, and our earlier examples suggest that perhaps there are indeed infinitely many such primes. But that’s just a guess — perhaps there’s some more subtle problem for some q. It turns out to be correct, though, and that’s this week’s theorem, due to Dirichlet.

Theorem (Dirichlet’s theorem)Let a and q be coprime natural numbers (positive whole numbers with highest common factor 1). Then there are infinitely many primes that leave remainder a when divided by q.Putting it another way, there are infinitely many primes in the arithmetic progression a, a+q, a+2q, a+3q, ….

Informally, if there isn’t an obvious reason why there can’t be infinitely primes leaving remainder a when divided by q, then there are infinitely many such primes.

Now, how does one go about proving something like this? I’m not going to go into details, because it gets a bit technical and fiddly. But the first key idea is that instead of trying to mimic Euclid’s proof that there are infinitely many primes, one should instead try to mimic Euler’s proof, which I also mentioned previously. So we should think about the sum

.

That is, we take the sum of 1/p as p ranges over all primes that leave remainder a when divided by q. If we can show that this sum diverges, then, just as before, we’ll see that there are infinitely many primes of this kind. Now I stopped describing the proof at this point last time, and I’m going to do the same here! Suggestions for further reading below.

It turns out that the primes are (approximately) evenly divided amongst the various possible remainders, just as they were when we divided by 4. There’s a result called the Siegel-Walfisz theorem, closely related to the prime number theorem for arithmetic progressions. But this is harder, and in fact there are conjectures in the area that mathematicians haven’t yet been able to prove (such as the Elliott-Halberstam conjecture).

### Further reading

This sort of material comes up in books on analytic number theory, such as Davenport’s *Multiplicative Number Theory*, and *Analytic Number Theory* by Iwaniec and Kowalski, and many more.

February 25, 2010 at 11:20 am

It turns out that there is a good reason to side with Euler rather than Euclid. Decades after Dirichlet proved his theorem, Ram Murty showed that Euclid’s proof generalizes only to congruence classes of a very special form.

November 7, 2011 at 12:50 pm

[…] Theorem 43 (Dirichlet): Let be an integer greater than 1, and let be coprime to . Then there are infinitely many primes congruent to modulo . We did not prove this! But we saw a small hint of how one can prove it. […]

February 13, 2012 at 11:20 pm

[…] It’s a bit more complex than what I put here, and if you want to see some crazy math behind it, I would love to direct you to the blog Theorem of the Week. […]

November 11, 2013 at 12:09 pm

[…] Theorem 42 (Dirichlet‘s theorem on primes in arithmetic progression): Let be an integer greater than , and let be a natural number coprime to . Then there are infinitely many primes congruent to modulo . That is, there are infinitely many primes in the arithmetic progression , , , , …. We are not going to see a proof of this result in this course (but see below in the Further reading section for places to look). […]