In which we study Legendre’s formula and Bertrand’s postulate.
- Proposition 52 (Legendre’s formula): Let be a real number. Then . Moreover, . We saw that this was basically the inclusion-exclusion principle.
- Lemma 53: For any natural number , we have . This came from considering .
- Lemma 54: Let be real. Then . We proved this by induction (having established that it suffices to prove the result for natural numbers ), using the key point that .
- Theorem 55 (Bertrand‘s postulate): Let be a natural number. Then there is a prime with . We started the proof by writing as a product of three things. We can get upper bounds for two of them, and our aim is to show that the third part is greater than . We’ll finish this next time.
Understanding today’s lecture
You could use Legendre’s formula (well, inclusion-exclusion) to practise computing for some small values of .
Can you finish the proof of Theorem 55? You could put together the ingredients we’ve collected so far to see where it gets you.
Erdős and Surányi (Topics in the theory of numbers) discuss Bertrand’s postulate and a number of other interesting results relating to the distribution of the primes. There’s also a proof of Bertrand’s postulate in Hardy and Wright (An Introduction to the Theory of Numbers).
Preparation for Lecture 18
Of course, you should try to finish the proof of Bertrand’s postulate for yourself.
Then next time we’ll have another change of topic. We’re going to think about approximating irrational numbers by rationals (Diophantine approximation). The aim is to get a very good approximation by a rational with very small denominator. How would you go about finding a good rational approximation to or , for example? If you find a good approximation, can you be confident that it’s the best option? (That is, could there be another rational with smaller denominator that gives a better approximation?)