April | 2015 | Ceci n'est pas un blog

Archive for April, 2015

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}$ .