A lower bound for (N). In this question we will prove that there are infinitely many primes by examining the prime counting function (N), where

(N) = The number of primes between 2 and N

We say that a natural number n 2 is square-free if it is not divisible by a square. For example, 6 is square-free, but 8 is not, since it is divisible by 4 = 22 .

1. Use the fundamental theorem of arithmetic to show that every integer n 2 can be written as a product n = sr 2 , where s, r 1 are integers and s is square-free.

We call this the square-free factorization. 2. For example, the square-free factorization of 8 = 2 (2)2

(s = 2, r = 2) and of

600 = 6 102

(s = 6, r = 10.) Find the square-free factorization of 72 and 2366.

3. Define

S(N) = The number of squares between 1 and N F(N) = The number of square-free numbers between 1 and N What is S(4), S(25) and S(49)? F(6) and F(50)? 4. In part 1, we showed that every positive integer factors uniquely as a product of a square and square-free number. Use this to conclude that N S(N) F(N). In the next parts well overestimate both S(N) and F(N). 5. Show that S(N) N for every N 1.

6. Show that F(N) 2 (N) . (Hint: every square free-number smaller than N of the

form q1 q2 ... qk where the qi are distinct primes smaller than N.) 7. Now using 4, 5, and 6, we have N N 2 (N) . Get (N) by itself on the

right-hand side of this inequality. 8. Take the limit from the solved inequality in 6 to conclude that limN (N) = and hence that there are infinitely many primes. 9. Using part 6, whats the smallest N guaranteed to have 500 primes smaller than it? 10. What additional information does this proof provide that Euclids doesnt? This proof is due to Paul Erdos. There is a good documentary about him available to watch by clicking here. Note that square/square-free numbers appear in the Elements.