Posts Tagged ‘number-theory’

The Prime Number Theorem (up to a constant factor)

April 14, 2015

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

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

Add the numbers k and n-k in base p (by the usual primary school algorithm). Then the number of carries that occur in this addition is equal to the greatest power of p dividing {n \choose k}.

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

We immediately get

\displaystyle \prod_{p\leq n}p^{\log_pn}\geq {n\choose k}

which is of course equivalent to

\displaystyle n^{\pi(n)}\geq {n\choose k}.

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