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).
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.