The Prime Number Theorem (up to a constant factor)

It is suprisingly easy and pretty to give an elementary proof that the prime number theorem (that the number of primes less than is asymptotic to ) is true up to a constant factor. (I will address only the part where we show that there are many (i.e. at least ) primes less than .)

Consider a binomial coefficient . Let be a prime. We first want to know what the largest power of is which divides . There is more than one way to express the answer, the most elegant one I know of is as follows:

Add the numbers and in base (by the usual primary school algorithm). Then the number of carries that occur in this addition is equal to the greatest power of dividing .

What is most important for us is the fact that this number is no more than .

We immediately get

which is of course equivalent to

Make a good choice of and we are within a constant factor of the prime number theorem!

Advertisement

The Butterfly Theorem

Let be the midpoint of the chord of a circle. Let and be two other chords of the circle passing through and let and be the intersection points of with and respectively. Then is the midpoint of the segment . Proof: The space of all degree two polynomials vanishing at the four points and is of dimension 2*. Thus it is spanned by the equation of the circle and the equation of the union of the lines and . Choose coordinates such that the line is the -axis and the point is the origin. Then the coefficient of in both our spanning polynomials is equal to zero, hence this coefficient is also zero in the equation of the union of and . Therefore is the midpoint of the segment , as required.

*To see this there is a six dimensional space of degree two polynomials and we are imposing one linear condition each time we require the polynomial to vanish at a point. These four conditions are linearly independent since it is easy to find degree two curves passing through three of these points and not the fourth (e.g. a union of two lines).